-1
A
回答
0
分而治之貢獻了log(n)因子。您將數組分成半個log(n)次,每次執行時,對於每個段,必須在兩個已排序的數組上進行合併。合併兩個排序的數組是O(n)。該算法只是走上兩個陣列,然後走上滯後的那個陣列。
+0
謝謝!我的無論如何,它都會分而治之。我不知道我會得到多少(如果有的話)分。 – juice 2013-05-10 05:24:10
0
你得到的遞歸是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個比較。
相關問題
- 1. 我們可以做快速排序與n logn最壞情況的複雜性?
- 2. 什麼是合併的關鍵比較的最壞情況數量?
- 3. 爲什麼合併排序最差情況運行時間O(n log n)?
- 4. 特殊情況下插入排序的最壞情況比較
- 5. Redis:它是否仍然O(logN)從排序集中獲得最高分?
- 6. 爲什麼合併排序被認爲是最好的
- 7. 在合併排序算法的分析中,'6n'(6n(logn + 1)= 6nlogn + 6n)是什麼?
- 8. 快速排序最糟糕的情況是什麼?
- 9. 這種情況下最好的排序算法是什麼?
- 10. KMP字符串搜索算法的最壞情況是什麼?
- 11. 斯坦因算法的最壞情況輸入是什麼?
- 12. 什麼是隨機搜索的最壞情況
- 13. 當epmd端口打開時最壞的情況是什麼?
- 14. 最壞的情況會是什麼時間複雜度?
- 15. 什麼是最壞的情況大哦使用list.retainAll
- 16. A *搜索算法的最壞情況是什麼?
- 17. QuickHull最壞情況
- 18. 冒泡排序最壞的情況下,最好的情況下和平均情況下的複雜性
- 19. 有人可以向我解釋爲什麼插入排序的最壞情況是O(n^2)?
- 20. 爲什麼在合併排序中合併操作是O(n)?
- 21. 爲什麼插入排序的最佳情況是O(n)&not O(n^2)?
- 22. 最壞情況下運行時間爲O,Ω爲最佳情況,但爲什麼有時在最壞情況下使用Ω?
- 23. 最壞的情況快速排序二叉樹
- 24. Generete本地插入排序的最壞情況?
- 25. Map reduce:最壞的情況
- 26. 爲什麼listbox2仍然是空的?
- 27. 爲什麼仍然是空的數據
- 28. 爲什麼這仍然是可選的?
- 29. 爲什麼沒有衝突的git合併仍然會產生合併提交?
- 30. Splay樹:最壞情況序列
從反向列表開始,手動運行算法。計算你的操作次數。 – 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