爲什麼合併排序的最壞情況仍然是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？

回答

相關問題