[理工] 資結 quicksort joey11121 PTT批踢踢實業坊

[理工] 資結 quicksort

作者: joey11121 (KRjoyz) 2019-11-20 20:13:33

https://i.imgur.com/QxyShok.jpg
想請問各位為什麼筆記上面計算quicksort的Best 和worst時間複雜度的遞迴關係式中，都需要把c*n加在最後呢？
我知道Best case是剛好對半分所以前面要寫2*T(n/2)，然後worst case是每次剛好切到最大或最小，
所以需要T(n-1)，麻煩各位解答。

作者: mi981027 (呱呱竹) 2019-11-20 20:15:00

c*n表示的是1,2步所花的時間是O(n)

作者: zuchang (chang) 2019-11-20 20:16:00

因為第一輪的排序也要時間

繼續閱讀

[理工] 計組數字表達問題 p.237 第27題ching4562 [理工] 線代 3-55 範例8jean20157 [理工] 線代算子houallan5478 [理工] 計組關於 gate delayching4562 [理工] 線代 traceAdonisLam [理工] 台大電機 97資結 11 15題 tree rotationdsa66253 [理工] 作業系統 deadlocklucy35 [理工] 張凡計組第六章習題Justapig ［理工］線代維度與onto問題yibalababa [理工] 線代矩陣運算 1-40u0424064