分析
??我们都知道常规解法这个数列存在这个等式 , 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];}