递归算法的复杂度分析方法。

　　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

 

版权声明：本文为informatics原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/informatics/p/5093460.html