$fib()$递归
$fib(n)=fib(n-1)+fib(n-2): {0, 1, 1, 2, 3, 5, 8, ……}$
复杂度计算
$T(0)=T(1)=1; T(n)=T(n-1)+T(n-2)+1, n>1$
令$S(n)=\frac{[T(n)+1]}{2}$//这是要去掉递归式里的常数
则$S(0)=1=fib(1), S(1)=1=fib(2)$
故$S(n)=S(n-1)+S(n-2)=fib(n+1) //\Phi=\frac{1+\sqrt{5}}{2}=1.61803……$
$T(n)=2*S(n)-1=2*fib(n+1)-1=O(fib(n+1))=O(\Phi ^n)=O(2^n)$
标签：fib,Phi,frac,斐波,那契,数据结构 From： https://www.cnblogs.com/asandstar/p/16893667.html