作者joey11121 (KRjoyz)
看板Grad-ProbAsk
标题[理工] 资结 quicksort
时间Wed Nov 20 20:13:33 2019
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1574252016.A.5E0.html
1F：→ mi981027: c*n表示的是1,2步所花的时间是O(n) 11/20 20:15
2F：推 zuchang: 因为第一轮的排序也要时间 11/20 20:16
3F：推 mistel: 不是第一轮 是每一层子问题 02/02 18:49