Fibonacci提出的问题如下：在一年开始时把一对兔子放入围场中，雌兔每月产雌雄各一的一对新兔子。第二个月开始，每对新兔子也是每月产一对兔子。在一年后围场中有多少对兔子？

在第一个月中，所给的一对兔子要产一对新兔子，因而在第一个月结束时，围场中有两对兔子。在第二个月里只有原来的一对兔子产一对新兔子，于是在第二个月结束时将有3对兔子。在第三个月里，原来的一对兔子和在第一个月里生的一对兔子都要产崽，所以在第三个月结束时，围场中将有2+3=5对兔子。对于每个n=1,2,……，令f(n)是第n个月开始时(等价于第n-1个月结束)围场中兔子的对数。我们已计算了f(1)=1,f(2)=2,f(3)=3和f(4)=5，故有递推关系f(n)=f(n-1)+f(n-2) (n=3,4,……)，这就是著名的Fibonacci数列。

可以用C语言简单的描述该递归算法：

int Fibonacci(int n){
                int s;
                if(n==0) return 0;
                if(n==1) return 1;
                sum=Fibonacci(n-1)+Fibonacci(n-1);
                return s;
        }

对于Fibonacci数列可以采用母函数的方法来计算Fibonacci数列的时间复杂度：

对于序列a_0 a_1 a_2构造一函数

称函数G(x)是序列a_0 a_1 a_2的母函数

由于f(n)=f(n-1)+f(n-2);且f(0)=f(1)=1.

故可设G（x）=f(1)x+f(2)x^2+……

可得出G（x）-x^2-x=x(G(x)-x)+ x^2G(x)
        =>(1-x-x^2)G(x)=x
        =>G(x)=x/(1-x-x^2)
                =x/((1-((1-√5)x)/2)(1-((1+√5)x)/2))
                =A/(1-((1+√5)x)/2)+B/(1-((1-√5)x)/2)

解之得A=1/√5,B=-1/√5
        故G(x)= (1/√5 ) (1/(1-((1+√5)x)/2)+1/(1-((1-√5)x)/2)))
        令G(x)= 1/√5((α-β)x+(α^2 −β^2) x^2+……)
        =>f(n)= (α^n−β^n)/ √5

其中：

        α=（1+√5 )/2 β=（1−√5 )/2

故 f(n)= (1/ √5) 〖(（1+√5)/2 )〗^n

由此可得Fibonacci数列的时间复杂度为:

        T（n）=o(〖(（1+√5)/2 )〗^n)

本文主要参考网络相关文章以及组合数学相关书籍，由于无法考证其原出处，在此表示感谢。