最差情况 求解递推方程 T(n-1)=7(n-2)+c(n-1) T(n)=T()+T(n-1-1)+cn T(n-2)=T(n-3)+C(n-2) T(2)=T(1)+c(2) 总的时间代价为 7(n)=7(1)+C∑i=m2) 举位▲张倍墙写 北大单张铭写 叔新有,命邮 最佳情况 T(m)=2T(m/2)+cm logn次分割 7(m)7(1) +clos T(n)=cnlogn+n=O(nlog n) 北真大脆张写 版叔斯有就即究 真大影张帖写 叔新有,量究 假设在每次分割时,轴值处于最 ■T()和T(n-1-i的平均值均为 终排序好的数组中位置的概率是 样的 7()=7(n-1-1)=∑T(k) ■也就是说,轴值将数组分成长度 为0和n-1,1和n-2,…的子序列的 r(0=n+1)(r(+m-1-k)=am+2r(k 概率是相等的,都为1/n 北真大学张铭编写 聊张帖写 权新有,究13 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 73 „ 求解递推方程 T n T i T n i cn ( ) () ( 1 ) = + −− + 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 74 最差情况 „ 总的时间代价为： ( ) ( 1) ( 1) ( 2) ( 1) ( 2) ( 3) ( 2) (2) (1) (2) T n T n cn Tn Tn cn Tn Tn cn T Tc = − + − = −+ − − = −+ − = + # 2 2 ( ) (1) ( ) n i Tn T c i n = = + =Θ ∑ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 75 最佳情况 ( ) 2 ( / 2) ( ) ( / 2) / 2 ( / 2) ( / 4) /2 /4 ( / 4) ( / 8) /4 /8 (2) (1) 2 1 T n T n cn Tn Tn c n n Tn Tn c n n Tn Tn c n n T T c = + = + = + = + = + # 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 76 „ log n次分割 ( ) (1) log 1 ( ) log ( log ) Tn T c n n T n cn n n n n = + = + =Θ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 77 „ 假设在每次分割时，轴值处于最 终排序好的数组中位置的概率是 一样的 „ 也就是说，轴值将数组分成长度 为0和n-1，1和n-2，…的子序列的 概率是相等的，都为1/n 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 78 „ T(i)和T(n-1-i)的平均值均为 1 0 1 () ( 1 ) ( ) n k Ti Tn i Tk n − = = −− = ∑ 1 1 0 0 1 2 ( ) ( ( ) ( 1 )) ( ) n n k k T n cn T k T n k cn T k n n − − = = = + + −− = + ∑ ∑