递归算法的复杂度分析方法。
a、分析出复杂度公式（关于n的规模）
b、求解这个公式
1、齐次
例如求fabonaci的第n项，f(n) = f(n-1)+f(n-2)
=> f(n)-f(n-1)-f(n-2)=0
=>特征方程：x^2-x-1=0
=> x1,x2
=> f(n)=a*x1n + b*x2n
2、master method
T(n) = aT(n/b) + f(n)
3、采用分析树的方式
举个例子 f(n) = 2*f(n-1) + 1
1 1 --------------------------------------> 20
f(n-1) f(n-1) ==> 1 1 ----------------------------> 21
…… f(n-2) f(n-2) f(n-2) f(n-2) ---------------------> 22
所以： f(n) = 20 + 21 +22 +…… = 2n - 1