如何以最有效的方式将两个未排序的数组合并为一个已排序的数组？

Question

假设我们有两个数组：

A[] = {7, 15, 2};     //*Size: n* 

B[] = {5, 96, 15};    //*Size: m*

我们想要得到 c[] = {2, 5, 7, 15, 15, 96}.

我有一个天真的方法：首先对数组 A 和 B 进行排序，然后合并它们以获得 c.

时间复杂度：O (nlogn + mlogm + (n + m))

Space 复杂度 : O ( (n + m) )

但是有什么有效的方法吗？？

Answer 1

不，不能做得更好，因为对于一般情况排序，这意味着排序比 O(nlogn) 更快。（在渐近时间复杂度方面）

首先，请注意，O(nlogn + mlogm) = O((n+m)log(n+m)

不失一般性，n <= m（否则只需切换数组）。

nlogn + mlogm <= (n+m)log(n+m) + (n+m)log(n+m) = 2(n+m)log(n+m)
which is in O((n+m)log(n+m))
(n+m)log(n+m) <= 2n*log(2n) <= 2n*log(2n) + 2m*log(2m) <= 2(nlog(n) +mlog(m) + nlog(2) + mlog(2))
which is in O(nlogn + mlogm)

这意味着，就渐近时间复杂度而言，建议的方法并不比完成后组合数组和排序更好。

现在，假设这可以在 O(f(n,m)) 中完成，其中 f(n) 在 o((n+m)log(n+m)) 中（此处使用小符号）。这意味着，对于任何给定的数组 - 您可以将其拆分为两个数组，并且运行建议的算法。这与排序是 Omega(nlogn) 问题的事实相矛盾。

如何以最有效的方式将两个未排序的数组合并为一个已排序的数组？

How to merge two unsorted array into a sorted one in the most efficient way?

algorithm

big-o