时间复杂度分析(递归求斐波那契)
使用递归树进行分析
1.斐波那契的递推式是:
f(n)=f(n-1)+f(n-2)
其中:f(1)=1,f(2)=1
2.用java代码实现:
public int getResult(int n){
if(n == 1 || n == 2) return 1;
return getResult(n-1)+getResult(n-2);
}
3.时间复杂度分析(递归树)
递归树如下:
树的叶子为f(1)或者f(2),值都是1,其中最长的高度为每次n-1，高度为k，k为n，最短的高度为每次n-2，k为n/2。
看前面的代码，getResult(n-1)+getResult(n-2)，每一次的分解都需要一次求和的操作，记为1，第一层需要1次求和，
第二层需要2^1=2次求和，第三层需要2^2=4次求和，第k层需要2^(k-1)次求和操作。
时间复杂度就是每一层的求和次数加和:
1+2+4+8+2^(k-1)
等比数列求和：
和为:2^(k-1) -1，其中k为n。
当步长为2的时候，和为2^(n/2-1) -1
用大O表示法表示
该代码的时间复杂度为O（2^(n/2)）到O（2^n）之间。