斐波那契数列 logn

分析

  我们都知道常规解法这个数列存在这个等式 , F(n) = F(n-1) + F(n-2) , 我们通过递归的时间复杂度是 2的n 次方，通过迭代时间复杂度是 O(n)。
  可是这个菲薄那切数列里面还有一个数学规律，应用这个规律我们可以把时间复杂度降到 logn 。

做法

  F(n) = F(n-1) + F(n-2) 可以看出这个是一个递推数列，通过这个递推数列，我们必定可以用矩阵把这个递推式表示出来:

  如上面的计算过程这个n-2次方的矩阵，是可以以log2n解出来的，这个就跟快速幂一个道理了。

扩展

如果不是 F(n) = F(n-1) + F(n-2) , 是其他的递推式怎么计算状态矩阵呢?假设是下面这个递推式：

  根据上面，俩个列子，大家可以看出来状态矩阵其实，可以很快的一眼看出来，第一列就对应的 F(N) 的递推式的系数，如 F(n) = F(n-1) + F(n-3) , 可以得知 a=1,d=0,g=1。第二列对应的是F(n-1)的递推式，那么F(n-1)就等于F(n-1),那么答案就是b=1,e=0,h=0。 第三列对应的是F(n-2)的递推式，那么c=0,f=1,i=0。
  有一个快速算出状态矩阵的方法，根据上面这个矩阵，其实右边等式每一列的都是F(n-1),F(n-2),F(n-3)乘以相应的系数然后对应左边的一个值。这样很快的就可以算出状态矩阵进而算出最终答案。

矩阵得菲波那切结果

  若 F(n) = F(n-1) + ..+F(n-i)，根据状态矩阵的n-i次方算出，最终矩阵结果后，最终答案F(n)就等于F(i),F(i-1),F(i-2)与最终的矩阵的第一列的相应元素乘积的和。
  如上面 斐波那契F(n) = F(n-1)+ F(n-2)
result = F(2)*matrix[0][0]+F(1)*matrix[0][1]

矩阵乘法

  正常的一个n阶的矩阵，它的乘法时间复杂度是O(n^3) , 但是在本题中，矩阵都是一个常数，所以每次对其的乘法计算都可以看成是O(1) ， 所以主要的时间复杂度来自于它的幂次方这个函数，这个函数我们使用了特殊的技巧，做到了log^n , 所以整体的时间复杂度效率是 log^n 。

代码

 vector<vector<int>> multMatrix(vector<vector<int>> &left ,vector<vector<int>>&right)
 {
      vector<vector<int>> ret(left.size());
       for(auto & i: ret)
       {
           i.resize(right[0].size());
       }
       for(int i = 0;i<ret.size();++i)  //ret的行号
       {
           for(int j=0;j < ret[0].size();++j) // ret 的列号
           {
               for(int k=0;k<right.size();++k)
              {
                  ret[i][j]+=left[i][k] * right[k][j];   // result的第i 行 就是 left 的第i行 ， result的第j列就是right的第j列
              }
          }
      }
      return ret;
}
vector<vector<int>> multMatrix(vector<vector<int>>&left, vector<vector<int>> &right)
 {
      vector<vector<int>> ret(left.size());
       for(auto & i: ret)
       {
           i.resize(right[0].size());
       }
       int r = 0;
       int Row = ret.size();
       int Col = ret[0].size();
       int rightsize = right.size();
       for(int i = 0;i<Row;++i)  //ret的行号
       {
           for(int j=0;j < Col ;++j) // ret 的列号
           {
               r = left [i][j];
               for(int k=0;k<rightsize;++k)
              {
                  ret[i][k]+=right[i][k] * r;   
              }
          }
      }
      return ret;
}
再次优化了: 矩阵的乘法， 优化技巧有1代码移动  2 空间局部性和时间局部性优化
 vector<vector<int>> matric(vector<vector<int>>&p, int m)
 {
     assert(m >= 0);
     vector<vector<int>> ret(p.size());
     for (int i = 0; i<p.size(); ++i)
     {
         ret[i].resize(p[0].size());   //单位矩阵乘以矩阵等于矩阵本身
         ret[i][i] = 1;//我们第一次乘的时候不能直接拿矩阵相乘，这里的单位矩阵就
     }                 // 相等于快速幂中的 常量1 
     vector<vector<int>> next(p);
     for (; m != 0; m >>= 1)
     {
         if (m & 1)
         {
             ret = multMatrix(ret, next);
         }
         next = multMatrix(next, next);
     }
     return ret;
 }
 int Fib(int n)
 {
     if (n < 3)
         return n;
     vector<vector<int>> v = { { 1, 1 }, { 1, 0 } };
     v = matric(v, n - 2);
     return 1 * v[0][0] + 1 * v[1][0];
 }