矩阵n次方的时间复杂度
哪些公司问过
答案要点
- 一次m×m朴素矩阵乘法为O(m³)
- 朴素连乘k次方需k-1次乘法,总复杂度O(k·m³)
- 快速幂按k的二进制反复平方,最多约2·log₂k次乘法,总复杂度O(m³·log k)
- 若矩阵为n×n且求n次方,复杂度为O(n³·log n)
- 应用:线性递推如斐波那契,2×2矩阵快速幂可在O(log n)求第n项
易错点
- 把矩阵规模和幂次混为一个n,复杂度写成O(n³)或O(log n)
- 忘记单次矩阵乘法本身是O(m³),只答O(log k)
- 快速幂结果初值写成0矩阵而不是单位矩阵
面试官常见追问
- 斐波那契数列怎么用矩阵快速幂求?
- 快速幂的迭代写法关键步骤是什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。