有效地合并两个数组 - 一个排序,另一个未排序

Question

我正在研究一个问题,它有一个由n个元素组成的排序数组,后跟一个未排序的长度数组

1. O(LOGN)
2. O(SQRT(n))的

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

Answer 1

由于将单个元素插入到数组中并保持其排序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).

Answer 2

您可以简单地对未排序的数组进行排序,然后在这两个排序的数组上进行合并(如合并排序算法).