合并两个阵列有效地 - 一个排序，另一个未排序

我在具有n个元素，随后长度合并两个阵列有效地 - 一个排序，另一个未排序

O（logn）时间
O（SQRT的一个未排序的阵列的排序后的数组中的问题的工作（n））

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

来源

2012-12-13 Neel

我们可以在第一种情况下使用信息O（logn）吗？我们可以使用任何数据结构并更有效地进行分类吗？ – Neel

由于在数组中插入单个元素并保持排序为O(n)，所以您无法做得更好。

因此，对于这两种情况 - 排序较小的阵列，然后使用merge(part1,part2)将为O(n)，因此在渐近复杂性方面是最优的。

排序较小的数组：O(logn*loglog(n))或O(sqrt(n)*log(sqrt(n))分别的情况。
merge(part1,part2)：O(n+logn)或O(n+sqrt(n))，也就是O(n) 无论如何。

所以，这两种情况下总的复杂性是O(n)，这是最适合这个问题。

（1），因为，log(n)^k是渐近较小然后n^m每个k>0,m>0，并且具体地为k=1, m=1/2这是真的。
证明是基于考虑双方的日志：

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)。

来源

2012-12-13 15:11:40 amit

你的逻辑是正确的，只是它不是很明显，'O（sqrt（N）* log（N）） salva

@salva：我会澄清，但基本上'log（n）^ k对于每个'k，m'，特别是对于'k = 1，m = 1/2'，渐近地小于'n^m'。 – amit

@salva：我加了一个详细的解释，作为这个说法的脚注。 – amit

很简单，对第二部分进行排序并将其与第一部分合并（与合并合并一样）。两个排序子阵列的合并步骤是O（n）。

来源

2012-12-13 15:10:51

您可以简单地对未排序的数组进行排序，然后在这两个排序的数组上执行merge（如merge sort算法）。

来源

2012-12-13 15:11:53

分别假设part1和part2尺寸分别为r O（log n）和O（sqrt（n））。因此，如果您从part2中选择一个元素并通过二进制搜索在log（log n）中找到part1中的位置，并递归执行，直到part2的元素不为空，则总运行时间将变为O（sqrt（n）log （log n））。

来源

2013-09-15 10:54:13

通过二分搜索找到part1中元素的位置（来自part2）将取logn。但是要将元素放置在part1中的正确位置将需要线性时间（O（n））。这里第1部分中的排序数组有n个元素。有两个问题。第一个问题中未排序的数组长度是logn，第二个问题是sqrt（n）。 – Neel

合并两个阵列有效地 - 一个排序，另一个未排序

回答

相关问题