斐波那契数列的 O(log n) 解法
哪些公司问过
商汤科技1
答案要点
- 递推写成矩阵:[F(n+1),F(n)]^T = [[1,1],[1,0]]·[F(n),F(n-1)]^T
- M^n = [[F(n+1),F(n)],[F(n),F(n-1)]],取 M^n 的右上角即 F(n)
- 快速幂:按 n 的二进制位,低位为 1 则结果乘底数,底数自乘,n 右移
- 共 O(log n) 次 2×2 矩阵乘法,时间 O(log n),空间 O(1)
- n=0 单独处理;大数需每步对 1e9+7 取模并用 64 位整数存中间乘积
易错点
- 转移矩阵或取值位置写错,导致结果偏移一项
- 大数场景下乘法前没取模或用 32 位整数,导致溢出
- 把 n 次方和 n-1 次方混淆,边界 n=0、n=1 出错
面试官常见追问
- 还有别的 O(log n) 方法吗?
- 能用通项公式 O(1) 算吗?
- 这个方法能推广到什么问题?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。