[数据结构与算法]斐波那契数列求第N项的算法时间复杂度

1. 暴力通项递归
   斐波那契数列a1=1;a2=1;a3=a1+a2;......an=an-1+an-2;使用暴力解法的思路如下：

   ---

   

   ---

   #include<iostream>
   #include<vector>
   using namespace std;
   static int count=0;
   /*暴力递归求解斐波那契数列*/
   /*时间复杂度是O（2^n）*/
   int forceFib(int i){
       if(1==i||2==i)return 1;
       count++;
       return forceFib(i-1)+forceFib(i-2);
   }
   
   /*使用带备忘录的递归求解*/
   /*时间复杂度是O（n）*/
   /*1,主调函数中创建并初始化记事本
       2，递归函数接收记事本引用和查询序号
       3，递归结束条件
       4，查询记事本，若查到直接返回
       5，查询不到，进行递归，并将计算结果存到记事本
       6，返回记事本中结果。
   */
   int recursion(int i, vector<int>&checkVec);//函数声明
   
   int backupFib(int i){
       vector<int>backupVec(i+1,0);/*创建记事本并全部初始化为0*/
       return recursion(i,backupVec);/*记事本和查询序号传给递归函数*/
   }
   
   int recursion(int i, vector<int>&checkVec){
       count++;
       if (1==i||2==i)
       {
           return 1;
       }/*基线条件*/
       if (checkVec[i]!=0)/*查询*/
       {
              return checkVec[i];
       }
       /*若没查到，递归计算，并将结果记在记事本*/
       checkVec[i]=recursion(i-1,checkVec)+recursion(i-2,checkVec);
       return checkVec[i];
   }
   
   /*通过首项和递推公式递推求解*/
   int fastFib(int N){
       
       if (1==N||2==N)
       {
           return 1;
       }
       int front=1;
       int rear=1;
       int sum;
       for (int i = 3; i < N+1; i++)
       {
           sum=front+rear;
           front=rear;
           rear=sum;
           count++;
       }
       return sum;
   
   }
   
   
   int main()
   {
       int i=11;
       std::cout<<"fib("<<i<<")="<<fastFib(i)<<std::endl;
   
       std::cout<<"计算次数="<<count<<std::endl;
       return 0;
   }