为什么合并排序的最坏情况仍然是logn？

-1

这是我之前拍摄的最后一个问题，我不知道如何回答。为什么合并排序的最坏情况仍然是logn？

那么它是

什么是合并排序的最坏的情况下运行，但更重要的是，为什么呢？

2013-05-10 juice

从反向列表开始，手动运行算法。计算你的操作次数。 – 2013-05-10 04:25:22

这是一个http://stackoverflow.com/questions/7801861/why-is-merge-sort-worst的副本-case-run-time-on-log-n – Bull 2013-05-10 04:35:02

分而治之贡献了log（n）因子。您将数组分成半个log（n）次，每次执行时，对于每个段，必须在两个已排序的数组上进行合并。合并两个排序的数组是O（n）。该算法只是走上两个阵列，然后走上滞后的那个阵列。

来源

2013-05-10 04:26:28 djechlin

谢谢！我的无论如何，它都会分而治之。我不知道我会得到多少（如果有的话）分。 – juice 2013-05-10 05:24:10

你得到的递归是r（n）= O（n）+ r（roundup（n/2））+ r（舍入（n/2）。问题是你不能使用Masters Theorem解决这个问题的原因是因为四舍五入，所以你可以用数学方法或者使用一些类似黑客的解决方案，如果你的输入不是两个数的幂只是“吹起来”，那么你就可以使用r上的主定理（n）= O（n）+ 2r（n/2）。显然这导致O（nlogn）。函数merge（）本身在O（n）中，因为在最坏的情况下你需要n-1个比较。

来源

2016-04-15 13:57:01 hhwwww

为什么合并排序的最坏情况仍然是logn？

回答

相关问题