归并排序运行时间
我知道合并排序的运行时间是 O(n*lg(n)) 并且合并排序是一种比较排序，这也意味着在最坏的情况下需要 Ω(n logn) 对列表进行排序。
因此我是否可以得出归并排序的运行时间为 theta(n*lg n) 的结论？
I know that the running time of merge sort is O(n*lg(n)) and that merge sort is a comparision sort, which also means that it takes Ω(n logn) in the worst case to sort a list.
Can I therefore conclude that the running time of merge sort is theta(n*lg n)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果某物是
O(X)和Omega(X)，则意味着它是Theta(X)。log_b1(...)等于log_b2(...)乘以转换因子常数。你说的是（翻译）：
因此，归并排序的最坏情况行为正是
n log(n)，这是有道理的。当然，这是隐含的假设，即您没有有关序列的信息。
编辑：你也可以从第一原理证明这一点。需要注意的是，您可以在线性 Theta(N1+N2) 时间内合并两个排序数组，同时保持它们合并（通过并行扫描它们）。 （细分数组，无论得到什么序列，总是需要 Theta(log(N)) 时间，这个时间很小，所以我们忽略它。）我们现在注意到每个元素都必须合并 Theta(log(N))次（树的深度，如果你把它画出来）。因此 Theta(N log(N))。
If something is
O(X)andOmega(X), this implies it isTheta(X). Andlog_b1(...)is the same aslog_b2(...)times a conversion factor constant.What you said was (translated):
Thus it makes sense that the worst-case behavior of merge sort is exactly
n log(n).This is of course with the implicit assumption that you have no information about your sequence.
edit: You could also prove it from first principles. The thing to note is that you can merge two sorted arrays in linear Theta(N1+N2) time while keeping them merged (by scanning across them kind of in parallel). (Subdividing the array, nomatter what sequence you get, will always take Theta(log(N)) time, which is small so we just ignore that.) We now note that each element has to be merged Theta(log(N)) times (the depth of the tree, if you draw it out). Thus the Theta(N log(N)).
是的，归并排序的复杂度是theta(n*lgn)。还有另一种方法可以确定这一点。
众所周知，合并排序是一种分而治之的算法。首先，它将大小为 n 的数组分为两个 n/2 部分，然后对这两部分进行递归，最后将结果合并到已排序的数组中。
假设合并排序时间为T(n)。然后：
- 除法运算是常数 theta(1) - 您只需将数组的长度除以 2 即可找到数组的中间元素
- 数组每个部分的递归需要 T(n/2) 时间，这使得它们两个部分都需要 2T(n/2)
- 已知合并操作具有 theta(n) 复杂度
所以最终你得到以下 T(n) = 的递归方程：
西塔(1) |如果 n == 1
2*T(n/2) + θ(n) | 2*T(n/2) + θ(n)如果n> 1
解这个方程，得到 T(n) = theta(nlgn);
更详细的内容可以参考Corman的《算法简介》一书。
Yes, the complexity of merge sort is theta(n*lgn). And there is another way you can get sure about that.
The merge sort is known to be a divide-and-conquer algorithm. First it divides the array of size n in two n/2 parts, then recurses on both of them and finally merges the result into a sorted array.
Let's suppose that the merge sort time is T(n). Then:
- the dividing operation is constant theta(1) - you just need to find the middle element of the array by dividing it's length by 2
- the recursion on each part of the array takes T(n/2) time which makes 2T(n/2) for both of them
- the merge operation is known to have theta(n) complexity
So finally you get the following recurrent equation for T(n) = :
theta(1) | if n == 1
2*T(n/2) + theta(n) | if n > 1
Solving this equation you get T(n) = theta(nlgn);
For more details you can refer to "Introduction to algorithms" book by Corman.