合并两个数组 - 一个排序，另一个未排序 [英] Merge two arrays efficiently - one sorted, another unsorted

问题描述

我正在处理一个问题，其中包含n个元素的排序数组，后跟一个未排序的长度数组

I am working on a problem that has a sorted array of n elements followed by an unsorted array of length

1. O（logn）


2. O（sqrt（n））

如何最有效地排序整个列表？在上述两种情况下我应该使用哪种分类？

How to sort the entire list most efficiently? Which sorting should I use in the above two cases?

推荐答案

由于将单个元素插入到数组中并保持排序，所以 O（n） merge（part1，c $ c），那么您不能再更好了。

Since inserting a single element into array and keeping it sorted is O(n), you cannot get better then that.

将是 O（n），从而在渐近的复杂性方面是最佳的。

Thus, for both cases - sorting the smaller array and then using merge(part1,part2) will be O(n), and thus optimal in terms of asymptotic complexity.

• 排序较小的数组： O（logn * loglog（n））或 O（sqrt ）* log（sqrt（n））


• merge（part1，part2）： O（n + logn）或 O（n + sqrt（n）），这是 O（n） ¹

• sorting the smaller array: O(logn*loglog(n)), or O(sqrt(n)*log(sqrt(n)) respectively of the cases.
• merge(part1,part2): O(n+logn) or O(n+sqrt(n)), which is O(n)¹ anyway.

所以，这两种情况的总体复杂性是 O（n） ，这对于这个问题是最佳的。

So, the total complexity of both cases is O(n), which is optimal for this problem.

（1）这是真的，因为 log（n）^ k 渐​​近小于 n ^ m ，每个 k> 0，m> 0 ，具体为 k = 1，m = 1/2 。

证明是基于双方的日志：

(1) It is true because, log(n)^k is asymptotically smaller then n^m for each k>0,m>0, and specifically for k=1, m=1/2.
Proof is based on taking logs on both sides:

log (log(n)^k) <? log(n^m) <=>
k*log(log(n)) <? m*log(n)

最后一个显然是真的（对于大的 n 和常数 k，m> 0 ），因此权利要求是真实的。

从这里我们可以得出结论， sqrt（n）* log（n） sqrt（n）* n ^ 1/2 = n ，因此确实是 O（n）。

The last is obviously true (for large n and constant k,m>0), and thus the claim is true.
From this we can conclude that sqrt(n)*log(n) < sqrt(n) * n^1/2 = n, and thus it is indeed O(n).

这篇关于合并两个数组 - 一个排序，另一个未排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！