空闲的时候问问题，看了极其古老的斐波那契数列的合计，想起校队的时候华为面试官给我发的就是这个。 当时要求在10分钟内写出递归和非递归的解法。 然后，我大致听完了递归解法的坏处(堆栈溢出)。 在那之后也一直被当作简单的问题来处理。 当然，我一直认为其最高的时间复杂度是o(n )。 直到有一天，意外地接触到了应该很快的概念
什么是整数的幂？ 以整数为例，求an时，通常的想法是使a疲劳n次，时间的复杂度为o(n )； 另一方面，在快速乘方算法中，将an分解为am1(a2 ) m2 ) a4 ) m3 ) a8 ) m4……即将n用2进制数进行阶段性计算，从而将时间复杂度降低到o ) O(logN )。
举几个直观的例子：
a15=a*a2*a4*a8
本来累得要骑15次，使用快速乘方后累得骑7次就可以了。 其中，A、a2、a4、a8加倍后通过疲劳乘坐使用了4次，但他们之间又使用了3次。
A8=(A2 )2) 2
本来应该累坐8次，使用快速乘方是加倍累坐3次就能得出结果。
如果您仍然不太清楚为什么可以实现o(logn )的时间复杂性，请看看代码：
用/*移位方式进行二进制分解，用2^n倍进行底数*/publicintquickpow(int num，intn ) ) {int sum=1； while(n！=0) if((n1)！=0) {sum *=num； (n=1； num *=num； }return sum； ) ok，至此，基本上明白了整数的快速乘方的概念。 接下来讨论矩阵的快速幂。
假设构造矩阵的快速幂矩阵a。 根据线性代数，矩阵乘法满足耦合律。 这意味着：
A8=(A2 ) A2 ) A2 ) A2 )=) A2 ) 2
由此可见，快速乘方的概念也适用于矩阵乘法，但实现略有不同，且要求原始矩阵为方阵(保证可以多次自乘)。
我们直接写实现
//矩阵快速幂public int [ ] [ ] quick pow (int [ ] metrix，int n ) [ ] result={ 1，0 }，{ 0，1 }； //单位矩阵while(n！=0) if () n1 )==1) result=metrixmul ) result，metrix )； (n=1； metrix=metrixmul(metrix，metrix )； } return result； //矩阵乘法使用公共int [ ] [ ] metrix mul (int [ ] [ ] metrix 1，int [ ] [ ] metrix2) { int length=metrix1. length； int [ ] [ ] result=new int [ length ] [ length ]； for(intI=0； i length； I ) for(intj=0； j length； j({result[I][j]=0； for(intk=0； k length； k ) { result [ I ] [ j ]=metrix1[ I ] [ k ] * metrix2[ k ] [ j ]； } }返回结果； ) ok，到目前为止，我介绍了我们需要的快速乘方的基础知识。 那么，我用两个公式来展示它如何应用于斐波那契数列。
矩阵的快速幂和斐波那契数列把斐波那契数列的递推公式写成矩阵乘法
再推到第0项和第1项，就有了
到此为止，我想你已经敏锐地注意到了，中间的工具矩阵就是我们使用矩阵快速幂算法的实体。 应用上述工具方法，将最终矩阵的左上角作为返回值即可，但此时的时间复杂度也成功降低到了o(logn )。
请贴上我自己写的实现
类解决方案{ intres [ ] [ ]=new int [2] [2]； //初始矩阵int f1=0，f2=1； intintialmetrix [ ] [ ]={ { F2，0 }，{ f1，0 }； //工具矩阵{f(n )，f(n-1 ) }={ 1，1 }，{ 1，0 } { f (n-1 )，f(n-1 ) }/{ f (n )，f ) ) } t int [ ] [ ] temp metrix=quick pow (tool metrix，n -1 )； RES=metrixmul(tempmetrix，intialMetrix )； return res[0][0]； }