图 1：本文封面，矩阵幂把 O(n) 压进 O(log n)。
先说明属性：这是一篇笔试真题复盘，题目出自本地历史笔试资料，与任何公司的当前招聘无关。题面很直接：求斐波那契数列第 N 项，要求时间复杂度优于 O(n)。
为什么 O(n) 还会被嫌弃。
逐项递推 F(n) = F(n-1) + F(n-2)，从 F(0) = 0、F(1) = 1 开始迭代，O(n) 时间、O(1) 空间，这几乎是所有人的第一反应。面试官追问「能不能更快」，真正想考察的不是常数优化，而是一个范式转换：能不能把「一步一步推」变成「一次跳到第 n 步」。答案藏在递推式的线性结构里——常系数线性递推可以改写成矩阵幂，而幂可以用快速幂在 O(log n) 次乘法内算出来。
第一步：把递推改写成状态转移。
单独一个 F(n) 推不出下一步——这个递推需要连续两项。所以把相邻两项打包成一个状态向量（F(n), F(n-1)）。已知上一个状态（F(n-1), F(n-2)），新状态的两个分量分别是 F(n) = F(n-1) + F(n-2) 和 F(n-1) = F(n-1)（原样保留）。两个分量都是旧状态的线性组合，这正是一个矩阵乘法的样子。
第二步：读出转移矩阵。
把系数按行写下来就是转移矩阵 M：第一行对应 F(n) = 1×F(n-1) + 1×F(n-2)，第二行对应 F(n-1) = 1×F(n-1) + 0×F(n-2)，所以 M 是 [[1, 1], [1, 0]]。验证一下：M 乘（F(n-1), F(n-2)）得（F(n-1)+F(n-2), F(n-1)），正是（F(n), F(n-1)）。于是每乘一次 M，状态就向前推进一项；从初始状态（F(1), F(0)）=（1, 0）出发，乘 n 次 M 就得到（F(n+1), F(n)）。问题从「递推 n 步」变成了「求 M 的 n 次幂」。
第三步：快速幂把 n 次乘法砍成 log n 次。
直接连乘 n 次矩阵还是 O(n)，没赚到。快速幂的想法是把指数写成二进制：13 = 1101 = 8 + 4 + 1，所以 M¹³ = M⁸ × M⁴ × M¹。而 M¹、M²、M⁴、M⁸ 之间每一步只是自乘平方：M² = M × M，M⁴ = M² × M²，依此类推。平方只要 log n 次，再按二进制位把选中的幂乘起来，至多再 log n 次，总复杂度 O(log n)。n 越大，和 O(n) 的差距越是数量级的。
用 Node.js 22.15.0 跑一遍，并用朴素递推对拍 n = 0 到 200：
function mul(a, b) {
return [
[a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]],
[a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]],
];
}
function mpow(m, n) {
let r = [[1n, 0n], [0n, 1n]]; // 单位矩阵
let base = m;
while (n > 0) {
if (n & 1) r = mul(r, base); // 二进制位为 1 才乘入
base = mul(base, base); // 每轮平方：M -> M^2 -> M^4 ...
n >>= 1;
}
return r;
}
const M = [[1n, 1n], [1n, 0n]];
function fibFast(n) {
if (n === 0) return 0n;
return mpow(M, n)[0][1]; // (F(n+1), F(n)) = M^n 乘初始状态 (1, 0)
}
对拍与实测输出：
对拍 n=0..200: 全部一致
F(13) = 233n
F(100) = 354224848179261915075n
F(100000) 的十进制位数 = 20899
F(13) = 233，正是把 13 拆成 8 + 4 + 1、用 M⁸·M⁴·M¹ 三个幂相乘的演算结果。n 取到十万，结果是两万多位的大数，快速幂照样瞬间给出——乘法次数只跟 log n 成正比。朴素递推对拍两百项全部一致，说明矩阵化没有改变数列本身，只是换了一条更快的路径。
图 2：三步推导与 n = 13 的快速幂演算。
这套套路不只属于斐波那契。
任何常系数线性递推——比如 F(n) = a×F(n-1) + b×F(n-2) + c×F(n-3)——都能同样打包状态、读出转移矩阵、快速幂加速；工程版本通常还要求对大质数取模，只要在矩阵乘法的每一步顺手取模即可，数值可控。反过来用也一样：看到一个状态的下一步是旧状态的固定系数线性组合，就值得问一句「能不能矩阵化」。
回到笔试现场，建议的答题结构：先承认 O(n) 递推是基线，再给出三步推导——状态打包、转移矩阵、快速幂——并点破复杂度从 O(n) 到 O(log n) 的来源是指数的二进制分解；有富余再补一句「适用于一切常系数线性递推」的泛化。如果要求现场写代码，快速幂写对是及格线，讲清矩阵怎么从递推式里读出来才是加分项。你第一次见矩阵快速幂是在什么场景？欢迎说说当时卡在哪一步。