问题描述
考虑到 n始终大于m ,我只是想知道合并大小为n和m的两个排序数组的时间复杂度是多少?
I was just wondering what is the time complexty of merging two sorted arrays of size n and m, given that n is always greater than m.
我当时在考虑使用合并排序,在这种情况下,我认为它将消耗O(log n + m)。
I was thinking of using merge sort, which I assume in this case will consume O(log n+m).
我对big-oh和其他东西并不满意。请给我建议这个问题的时间复杂度,并让我知道是否有解决问题的最佳方法。
I am not really good with big-oh and stuff. Please suggest me the time complexity for this problem and let me know if there is an even optimized way of solving the problem.
谢谢。
推荐答案
注意!该答案包含错误
存在一种更有效的算法,并在另一个答案中给出。
A more efficient algorithm exists and it is presented in another answer.
复杂度为O(m log n)。
The complexity is O(m log n).
让长数组称为 a
并且短数组为 b
,则您描述的算法可以写为
Let the long array be called a
and the short array be b
then the algorithm you described can be written as
for each x in b
insert x into a
循环有m次迭代。每次插入排序数组都是一个O(log n)操作。因此,总体复杂度为O(m log n)。
There are m iterations of the loop. Each insertion into a sorted array is an O(log n) operation. Therefore the overall complexity is O (m log n).
由于对 b
进行了排序,因此可以得出上述算法
Since b
is sorted the above algorithm can be made more efficient
for q from 1 to m
if q == 1 then insert b[q] into a
else
insert b[q] into a starting from the position of b[q-1]
这可以提供更好的渐近复杂度吗?
Can this give better asymptotic complexity? Not really.
假设 b
中的元素沿 a $ c均匀分布$ c>。然后每个插入将花费
O(log(n / m))
,总体复杂度将是 O(m log(n / m))
。如果存在不依赖 n
或 m的常量
k> 1
code>,这样 n> k * m
然后 O(log(n / m))= O(log(n))
,我们得到与上述相同的渐近复杂度
Suppose elements from b
are evenly spread along a
. Then each insertion will take O(log (n/m))
and the overall complexity will be O(m log(n/m) )
. If there exists a constant k>1
that does not depend on n
or m
such that n > k * m
then O(log(n/m)) = O(log(n))
and we get the same asymptotic complexity as above.
这篇关于合并大小为n和m的两个排序数组的时间复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!