面试题库 › 算法 / 大模型 › 斐波那契数列的 O(log n) 解法

斐波那契数列的 O(log n) 解法

难度 ★★☆在 1 场真实面经中被问到 方向:算法 / 大模型考点:数学与智力题

哪些公司问过

商汤科技1

常见岗位:计算机视觉

答案要点

  1. 递推写成矩阵:[F(n+1),F(n)]^T = [[1,1],[1,0]]·[F(n),F(n-1)]^T
  2. M^n = [[F(n+1),F(n)],[F(n),F(n-1)]],取 M^n 的右上角即 F(n)
  3. 快速幂:按 n 的二进制位,低位为 1 则结果乘底数,底数自乘,n 右移
  4. 共 O(log n) 次 2×2 矩阵乘法,时间 O(log n),空间 O(1)
  5. n=0 单独处理;大数需每步对 1e9+7 取模并用 64 位整数存中间乘积

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题