斐波那契数列Fn定义如下：F0=0,F1=1,F2=1,F3=2,.,Fn=Fn-1+Fn+2（n=2,3...）问：如果用大O表斐波那契数列Fn定义如下：F0=0,F1=1,F2=1,F3=2,.,Fn=Fn-1+Fn+2（n=2,3...）问：如果用大O表示Fn时递归函数的时间复杂度

Question

斐波那契数列Fn定义如下：F0=0,F1=1,F2=1,F3=2,.,Fn=Fn-1+Fn+2（n=2,3...） 问：如果用大O表
斐波那契数列Fn定义如下：F0=0,F1=1,F2=1,F3=2,.,Fn=Fn-1+Fn+2（n=2,3...）
问：如果用大O表示Fn时递归函数的时间复杂度是多少?
解析：
令G（x）=F0*x+F1*x^2+...+Fnx^n+1+...
其中
F2=F1+F0 ,F3=F2+F1 ,F4=F3+F2 ,...,Fn=Fn-1+Fn-2 ,...,F1=1 ,F0=0
于是
G（x）-x-x^2=F2*x^3+F4*x^5+...+Fn*x^n+1+...
=(F1+F0)*x^3+(F2+F1)*x^4+(F3+F2)*x5+(F4+F3)*x^6+...+(Fn-1+Fn-2)*x^n+1+...
=(F0*x^3+F1*x^4+...+Fn+1*x^n+1+...)+(F1*x^3+F2*x^4+...+Fn-1*x^n+1+...)
=x*2*G(x)+x*[G(x)-x]
则（1-x-x^2）*G(x)=x,有
G（x）=x / (1-x-x^2)=x/{ [1-(1+√5)/2*x)] *[1-(1-√5)/2*x)] }
设 α=（1+√5)/2,β=（1-√5)/2,利用待定系数法将上式分解为
G（x）=1/√5*[ 1/(1-α*x)-1/(1-β*x) ]=1/√5*[ (α-β)*x+(α^2-β^2)*x+...+...] ---->此处为何这样推导不解?请明解.
于是,Fn=1/√5*(α^n-β^n)≈ =1/ √5*[（1+√5)/2]^n
因此,根据大O表示法,递归计算Fn时递归函数的时间复杂度为
O{ [（1+√5)/2]^n }

Answer 1

G（x）=1/√5*[ 1/(1-α*x)-1/(1-β*x) ]=1/√5*[ (α-β)*x+(α^2-β^2)*x+...+...] 原因：
1/(1-t)=1+t+t^2+t^3.
将t分别替换成α*x和β*x,对应项合并,就可推导出