合并排序运行时间 [英] Merge sort running time

问题描述

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

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.

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

Can I therefore conclude that the running time of merge sort is theta(n*lg n)?

推荐答案

如果O(X)和Omega(X)为某内容，则表示它为Theta(X).并且log_b1(...)与log_b2(...)相同，乘以转换因子常数.

If something is O(X) and Omega(X), this implies it is Theta(X). And log_b1(...) is the same as log_b2(...) times a conversion factor constant.

你说的是(翻译的):

我知道在最坏的情况下，合并排序的运行时间不会比n log(n)差. [您通过数学以某种方式得出了这个结论.]但是在最坏的情况下，比较排序至少需要n log(n).

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).

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:您还可以从第一原理中证明这一点.需要注意的是，您可以在线性Theta(N1 + N2)时间中合并两个排序的数组，同时保持它们合并(通过并行扫描它们). (将数组细分为多少，得到的序列将始终花费Theta(log(N))时间，该时间很小，因此我们可以忽略它.)现在我们注意到每个元素都必须合并Theta(log(N))次(树的深度，如果您将其绘制出来).因此，Theta(N log(N)).

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)).

这篇关于合并排序运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！