big-o - 归并排序运行时间

Question

我知道归并排序的运行时间是 O(n*lg(n)) 并且归并排序是一种比较排序，这也意味着在最坏的情况下它需要 Ω(n logn) 来对列表进行排序。

因此，我可以得出结论，归并排序的运行时间是 theta(n*lg n) 吗？

Answer 1

如果某事是 O(X)和 Omega(X) ，这意味着它是 Theta(X) .和 log_b1(...)与 log_b2(...) 相同乘以转换因子常数。

你说的是(翻译):

I know that the running time of merge sort is, in the worst case, no worse than n log(n). [You arrived at this conclusion somehow with math.] But comparison sorts take at least n log(n) in the worst case.

因此，归并排序的最坏情况行为恰好是 n log(n) 是有道理的。 .

这当然是隐含的假设，即您没有关于您的序列的信息。

编辑:你也可以从第一性原理来证明。需要注意的是，您可以在线性 Theta(N1+N2) 时间内合并两个已排序的数组，同时保持它们合并(通过并行扫描它们)。 (分割数组，无论你得到什么序列，总是需要 Theta(log(N)) 时间，这是很小的所以我们忽略它。)我们现在注意到每个元素都必须合并 Theta(log(N))次(树的深度，如果你把它画出来)。因此 Theta(N log(N))。