[理工] 資結 quicksort

看板Grad-ProbAsk作者 (KRjoyz)時間6年前 (2019/11/20 20:13), 編輯推噓2(2推 0噓 1→)
留言3則, 3人參與, 6年前最新討論串1/1
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
→
11/20 20:15, 6年前 , 1F
c*n表示的是1,2步所花的時間是O(n)
11/20 20:15, 1F
推
11/20 20:16, 6年前 , 2F
因為第一輪的排序也要時間
11/20 20:16, 2F
推
02/02 18:49, 6年前 , 3F
不是第一輪 是每一層子問題
02/02 18:49, 3F
‣ 更多 joey11121 的文章
文章代碼(AID): #1TrItmNW (Grad-ProbAsk)