→ mi981027: c*n表示的是1,2步所花的時間是O(n) 11/20 20:15
推 zuchang: 因為第一輪的排序也要時間 11/20 20:16
推 mistel: 不是第一輪 是每一層子問題 02/02 18:49
https://i.imgur.com/QxyShok.jpg
想請問各位為什麼筆記上面計算quicksort的Best 和worst時間複雜度的遞迴關係式中，都需要把c*n加在最後呢？
我知道Best case是剛好對半分所以前面要寫2*T(n/2)，然後worst case是每次剛好切到最大或最小，
所以需要T(n-1)，麻煩各位解答。
-----
Sent from JPTT on my iPad
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.239.155.153 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1574252016.A.5E0.html