递归方程（续）

1.二分归并排序算法时间复杂度

 

 

注意：对大小为n的数组进行排序，假设要归并的次数为K；则 n属于区间(2^(k-1), 2^k]，因为题目求得是最坏情况，所以n=2^k.

          等比数列求和：

           

 

2.快速排序时间复杂度分析

这里的公式详解：

T(K-1)在1,2,3...n求和累加 与T(n-k)是相同的，都等于

 

 

 

3.递归树模型求解时间复杂度

 

接到13.8例子来介绍：

 

补充下逝去的数学知识，嘿嘿：

 

摘自《离散数学屈婉玲教材》

 

 

来自为知笔记(Wiz)