最近菜鸡作者苦于解递归方程求解时间复杂度的一些问题
整理一下思路
递归算法的运行时间常用递归表达式表示。
本文主要讲解如何从递归表达式求解出时间复杂度。
万变不离其宗，总结以下四种形式。
例一：
T(n) = T(n-1)+1
解：T(n) = T(n-1)+1 = [T(n-2)+1]+1 = T(n-2)+2 = T(n-3)+3 = ... = T(n-n)+n = n
故 O(n) = n
例二：
T(n) = T(n-1)+n-1
解：T(n) = T(n-1)+n-1 = T(n-2)+(n-2)+(n-1) = T(n-3)+(n-3)+(n-2)+(n-1) = ...
= T(n-(n-1))+n-(n-1)+...+(n-2)+(n-1) = 0+1+2+3+4+...+(n-1) = n(n-1)/2
故 O(n) = n^2
例三：
T(n) = 2T(n-1)+1
解：T(n) = 2T(n-1)+1 = 2( 2T(n-2)+1)+1 = 4T(n-2)+2+1 = ...
= 2(n-1)T(n-(n-1))+2(n-2)+...2^2+2+1 = 2(n-1)+2(n-2)+...22+2+1=2n-1
故O(n) = 2^n
例四：
T(n) = 2T(n/2)+n-1
解： T(n) = 2T(n/2)+n-1 = T(n) = 2(T(n) = 2T(n/4)+n/2-1)+n-1 = 4T(n/4)+2n-2-1 = 4(2T(n/8)+n/4-1)+2n-2-1
= 8T(n/8)+3n-4-2-1 = 2k(T(n/(2k)))+kn-2^(k-1)-...-4-2-1
令n=2^k
代入得：T(n) = (2k)T(1)+k(2k)-(2^(k-1)+...+4+2+1) = （k+1）(2k)-((2k)-1) = n(logn)+1
故 O(n)= n(logn)
