[理工] 资结 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