矩阵快速模幂 + 求斐波那契数列第n项（Fibonacci）

• chenbingjy#p#maych 发布于
• 977 收藏

两矩阵相乘，朴素算法的复杂度是O(N^3)。如果求一次矩阵的M次幂，按朴素的写法就是O(N^3*M)。既然是求幂，不免想到快速幂取模的算法，前面有快速幂取模的介绍，a^b %m 的复杂度可以降到O(logb)。如果矩阵相乘是不是也可以实现O(N^3 * logM)的时间复杂度呢？答案是肯定的。 重载结构体运算符*和^表示矩阵乘法和矩阵求幂，取模的过程在 乘法中实现。 （Fibonacci...