7种方式实现斐波那契数列

gangtie 2021-08-08 原文

一：递归实现
　　在学校里学习递归的时候，老师就喜欢举斐波那契这个例子，看！多简洁清晰。其实这个例子是非常不适合作为递归举例的，
　　原因就是效率太慢，除了最后一个数，每个数都被算了一遍又一遍，时间复杂度差不多是5n^2/3。
二：数组实现
　　空间复杂度和时间复杂度都是0(n)，效率一般，比递归来得快。
三：vector<int>实现
　　时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高，当然vector有自己的属性会占用资源。
四：queue<int>实现
　　当然队列比数组更适合实现斐波那契数列，时间复杂度和空间复杂度和vector<int>一样，但队列太适合这里了，
　　f(n)=f(n-1)+f(n-2)，f(n)只和f(n-1)和f(n-2)有关，前面的数就乖乖的出队列吧。
五：迭代实现
　　迭代实现是最高效的，在学习斐波那契数列时，介绍了这个方法，当时不知道懂了没有，时间复杂度是0(n),时间复杂度是0(1)。
六：最难懂的实现方式
　　说他难懂是因为变量的命名，怎么啊，不行啊，其实就是用迭代实现的，哈哈哈…
七：公式实现
　　我靠！原来斐波那契数列有公式啊，那老师干嘛不直接教我们公式呢，教你公式，当然要告诉你推导啊，我不会，看(百度百科)斐波那契数列.
由于double类型的精度还不够，所以程序算出来的结果有误差，如果把公式展开计算，得出的结果是正确的。

递归实现

 1 递归实现
 2 
 3 int Fib1(int index)
 4         {
 5             if(index<1)
 6             {
 7                 return-1;
 8             }
 9             if(index==1|| index==2)
10             {
11                 return1;
12             }
13             return Fib1(index-1)+Fib1(index-2);
14         }

迭代实现
int Fib5(int index)
        {
            if(index<1)
            {
                return-1;
            }
 
            int a1=1,a2=1,a3=1;
            for(int i=0;i<index-2;i++)
            {
                a3=a1+a2;
                a1=a2;
                a2=a3;
            }
            return a3;
        }