Question

递归方程求时间复杂度

Answer 1

最近菜鸡作者苦于解递归方程求解时间复杂度的一些问题
整理一下思路
递归算法的运行时间常用递归表达式表示。
本文主要讲解如何从递归表达式求解出时间复杂度。
万变不离其宗，总结以下四种形式。

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)+...2 ^2+2+1=2 n-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 = 2 ^k(T(n/(2 k)))+kn-2^(k-1)-...-4-2-1

令n=2^k

代入得：T(n) = (2 ^k)T(1)+k(2 k)-(2^(k-1)+...+4+2+1) = （k+1）(2 ^k)-((2 k)-1) = n(logn)+1

故 O(n)= n(logn)