的斐波那契樹算法的複雜性

Question

我能找到這種算法的複雜性：

if (n=1) 
    T(n)=1 
else if (n=2) 
    T(n)=2 
else 
    T(n)= 1+T(n-1)+2T(n-2) 

這種算法可以像這種形式

T(1)=1 
T(2)=2 
T(n)=1+T(n-1)+2T(n-2) 

我希望能儘快找到答案..

Answer 1

有這樣的標準技術來解決線性復發，但我們也可以使用mathematica：

http://www.wolframalpha.com/input/?i=T%28n%29+%3D+1+%2B+T%28n-1%29+%2B+2+T%28n-2%29+and+T%281%29+%3D+1+and+T%282%29+%3D+2