尧图网站建设 到O(log n)的五种写法)
斐波那契数列大概是每个写代码的人都绕不开的一道坎。它形式简单到一行就能写出来但围绕它的时间复杂度分析几乎把算法分析里最核心的几套工具全用了一遍递归树、主定理、特征方程、记忆化、动态规划、矩阵快速幂、倍增。我面过不少人也被人面过只要问到「斐波那契数列的时间复杂度是多少」能答出 O(2^n) 的一抓一大把但能说清为什么不是严格的 O(2^n)、为什么同一个数列能有从 O(φ^n) 到 O(log n) 的五种复杂度、以及在什么场景该用哪一种的就不多了。这篇文章我想把这条线从头到尾捋一遍不光是给结论更重要的是把每一个「为什么这么选」讲透。不管你是刚开始刷算法题的新手还是想把复杂度分析这块补扎实的老手看完应该都能自己动手把这几种写法复现出来并且知道在工程里该挑哪一个。全文的分析套路不止适用于斐波那契最后我会把它迁移到排序算法上聊聊排序法时间复杂度怎么算这件事。1. 先搞清楚一个问题为什么会有五种复杂度1.1 斐波那契的四种经典写法与对应复杂度很多人对斐波那契时间复杂度的第一印象就是「递归是 O(2^n)加个数组优化成 O(n)」。这个印象不算错但它只覆盖了这条路上的前两站。完整地看同一个 F(n) 至少有四种主流写法复杂度跨度大到离谱写法时间复杂度空间复杂度n100 可行否朴素递归O(φ^n)常被粗略说成 O(2^n)O(n) 递归栈不可行记忆化搜索O(n)O(n)可行自底向上迭代O(n)O(1)可行矩阵快速幂O(log n)O(1)可行倍增法fast doublingO(log n)O(log n) 栈 / O(1) 迭代版可行我第一次把这五种写法摆在一起对比的时候心里其实有点震撼一个连小学生都能理解的递推关系居然能从指数级一路压到对数级。这中间的每一步优化都不是靠「换个语言」或者「调个参数」实现的而是靠对问题结构的重新理解。朴素递归是把问题当成一棵树在展开记忆化是发现这棵树里有大量重复节点迭代是发现根本不需要树、顺着推就行矩阵快速幂则是发现递推本质是一个线性变换而线性变换可以快速幂。每一次复杂度的下降背后都是一次视角的升级。这里有个细节值得单独拎出来说复杂度不是一个问题的固有属性而是「算法 问题」这一对的属性。同一个斐波那契数列问「它的时间复杂度是多少」本身就是个不严谨的问法正确的问法是「用某某算法求斐波那契第 n 项时间复杂度是多少」。我在代码评审里见过太多次因为混淆这两件事而吵起来的场面本质上就是没说清楚在讨论哪种实现。提示以后凡是听到「XX 的时间复杂度」先在心里补一句「用什么方法算」。这个习惯能帮你避免一大半的无谓争论。1.2 复杂度分析的三把尺子递归树、主定理、特征方程分析递归算法的时间复杂度我习惯准备三把尺子按精度从低到高排是递归树、主定理、特征方程。斐波那契恰好是那种三把尺子都能用、但结论精度不同的典型案例。递归树最直观也最适合用来跟别人解释。把 fib(n) 画成一棵树根节点是 fib(n)左右子节点分别是 fib(n-1) 和 fib(n-2)一直展开到 fib(0) 和 fib(1)。这棵树有多少个节点就代表做了多少次函数调用。粗看每一层的节点数最多翻倍树高是 n所以上界是 O(2^n)。这个结论好记但它是松的——因为树的左右两边并不对称fib(n-2) 那一侧会先触底整棵树并不是满二叉树。主定理是处理 T(n) aT(n/b) f(n) 这种标准分治形式的。斐波那契的递归式 T(n) T(n-1) T(n-2) O(1) 里子问题规模是 n-1 和 n-2而不是 n/b所以严格来说主定理在这里并不适用。我见过不少题解硬套主定理得出 O(n^2) 或者 O(n^log2) 之类的奇怪结论就是栽在这一点上。主定理的适用前提是子问题规模等比例缩小这里只是常数级缩小条件不满足。特征方程才是这个问题的正解。把 T(n) T(n-1) T(n-2) 当成一个二阶线性齐次递推来处理设 T(n) x^n代入得 x^n x^(n-1) x^(n-2)两边除以 x^(n-2) 得到 x² x 1解出 x (1 ± √5) / 2。取主导的正根 φ (1 √5) / 2 ≈ 1.618于是 T(n) Θ(φ^n)。这就是那个常被误写成 O(2^n) 的真实答案。三把尺子给出的结论分别是 O(2^n)、不适用、Θ(1.618^n)。所以你在面试里回答「O(2^n)」不算错但如果能补一句「严格上界是 Θ(φ^n)O(2^n) 只是它的一个宽松上界」效果完全不一样。这句话我用了很多次每次都能把面试官的兴趣勾起来。2. 暴力递归的 O(2^n) 到底是怎么来的2.1 递归树展开与调用次数的精确推导先把朴素递归的代码摆出来就这么四行def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)现在来数这棵树到底有多少个节点。设 C(n) 为计算 fib(n) 需要执行的函数调用总次数。当 n ≤ 1 时只调用一次所以 C(0) C(1) 1当 n ≥ 2 时一次调用自身加上两个子调用的开销得到C(n) C(n-1) C(n-2) 1这个递推式和斐波那契本身长得几乎一样只多了一个常数项。多出来的常数项在渐进分析里不影响量级所以 C(n) Θ(φ^n)。如果想要求精确值可以解出闭式C(n) 2·F(n1) - 1。拿 n5 验一下F(6) 82×8-1 15实际数一遍确实是 15 次调用对得上。这个精确式子比 Θ(φ^n) 更有用因为它能直接估算耗时。我实测过几组数据Python 3.11单核不同机器会有差异量级参考即可n调用次数 C(n)Python 实测耗时说明20约 1.4 万约 2 ms无感25约 24 万约 30 ms无感30约 270 万约 0.3 s开始有感35约 3000 万约 3.5 s明显卡顿40约 3.3 亿约 40 s不可接受45约 36.7 亿约 7 min生产事故级别n 从 35 涨到 45只多了 10调用次数却涨了一百多倍。这就是指数爆炸的手感——参数线性增长耗时指数增长。我第一次看到 n45 把进程卡死七分钟的时候是真的盯着屏幕发了会儿呆。注意C(n) 2·F(n1) - 1 这个式子里 n 是入参F 是斐波那契函数本身。写文档的时候千万别写成 2·F(n)-1差一项就差一个 φ 倍估算耗时会偏。2.2 用特征方程把 2^n 修正到 φ^n很多人会问既然 Θ(φ^n) 才是紧的为什么教材和题解里到处都在写 O(2^n)我理解有三个原因说清楚了你就不会再纠结。第一个原因是教学上的便利。φ 是个无理数写起来丑而 2^n 好记、好比较对初学者建立「递归会爆炸」的直觉足够用。第二个原因是大 O 只要求上界O(2^n) 确实是 T(n) 的一个合法上界数学上没错只是不紧。第三个原因是面试沟通效率。你说 O(2^n)对方一秒就懂你说 Θ(1.618^n)对方可能还要在脑子里算一下。但如果你要真正做性能预估就必须用 φ^n。举个具体的例子假设我有一台机器每秒能跑 5000 万次递归调用想知道 n 最大能取多少才能在一秒内跑完。用 φ^n 估算C(n) ≈ 2φ^(n1)/√5令它等于 5×10^7解出 n ≈ log(5×10^7 × √5 / 2) / log(1.618) ≈ 38。而如果用 2^n 估算会得到 n ≈ 25.6也就是 n25 左右这个结论悲观了太多白白浪费了一半的性能空间。这个差异在真实工程里是会出事的。我曾经在一个配置热更新模块里见过用递归算斐波那契风格的分支数本来按 O(2^n) 估算觉得 n30 就够呛结果实际压测发现 n38 才到瓶颈白白多写了一套缓存层。后来把模型换成 φ^n 重新估才发现原来的担心是多余的。所以我的建议是面试可以答 O(2^n)但落到代码和容量规划一定用 φ^n。顺便说一个容易踩的坑。φ ≈ 1.618 这个数与斐波那契的通项是对应的F(n) ≈ φ^n / √5。有些同学会把这个式子和 T(n) Θ(φ^n) 混为一谈认为递归的时间复杂度就是 F(n)。严格说只差一个常数因子 2/√5 和一个线性项渐进意义下确实等价但写公式的时候最好把常数带上否则算具体耗时会有两倍左右的误差。2.3 实测数据背后的硬件常识上表里的耗时是我在本地测的换台机器数字会变但比例关系不变。这里有几个经验值值得记住方便你以后心算一次 Python 函数调用的开销大约在 50100 纳秒这个量级算上加法、比较、栈帧管理整体算下来每秒钟大概能跑 1000 万到 2000 万次简单的递归调用。C/C 里同样的递归每秒能跑 3 亿到 10 亿次比 Python 快 3050 倍。换成 Go 或者 Java大致在每秒 1 亿到 3 亿次这个区间。这意味着同样一份朴素递归代码在 Python 里 n40 就要跑 40 秒在 C 里可能 1 秒就出来了。我见过有人拿 Python 里 n35 卡顿的经历去否定整个递归写法这就有点冤枉了——在 C 里 n40 都能接受。判断一种写法能不能用一定要带上语言和执行环境这两个前提。再补一个冷知识递归版的空间复杂度是 O(n)指的是递归调用栈的最大深度也就是 n 层。很多人分析时间的时候很熟一被问到空间就懵。记住一点就行递归的空间开销等于栈的最大深度不是调用总次数。fib(n) 的调用树有 φ^n 个节点但任意时刻栈上最多只有 n1 层因为每次都是先一路往左走到 fib(0)回来再走右边。3. 记忆化与迭代把 O(φ^n) 压到 O(n)3.1 记忆化搜索的三行改造朴素递归慢在哪慢在重复计算。fib(3) 在整棵树里被算了几百万次每次结果都一样白白浪费。记忆化的思路很朴素算过一次就记下来第二次直接查表。在 Python 里改造量小到只需要一个装饰器from functools import lru_cache lru_cache(maxsizeNone) def fib_memo(n): if n 2: return n return fib_memo(n - 1) fib_memo(n - 2)加上lru_cache之后n1000 也就是毫秒级的事儿。复杂度分析也很直接每个 n 值对应的子问题只会被真正计算一次其余的调用都是 O(1) 的字典查询所以总共 n1 个子问题每个内部做一次加法和两次查表时间复杂度 O(n)。空间上缓存表存了 n1 项加上递归栈 O(n)总空间 O(n)。不过lru_cache不是万能的有几个坑得提前说清楚。第一Python 默认的递归深度限制是 1000 层n 超过 990 左右就会抛RecursionError得手动sys.setrecursionlimit。但把限制调得太高又有栈溢出的风险所以 n 很大时别硬用递归。第二lru_cache是有锁的多线程场景下有额外开销如果只是单线程计算用functools.cachePython 3.9会更轻量。第三缓存会一直占着内存不释放如果是在长驻服务里做频繁的小规模计算反而可能被这个缓存拖累。我在 Go 里也写过类似的记忆化通常就是开一个map[int]int或者[]int切片自己判空。Go 里我更推荐用切片而不是 map因为下标连续、缓存友好实测在 n10000 这个量级能快个两三倍。3.2 自底向上迭代与滚动变量记忆化是「自顶向下 查表」它的对称写法是「自底向上 递推」。既然 F(n) 只依赖前两项那我从 0 开始往上推就行了def fib_iter(n): a, b 0, 1 for _ in range(n): a, b b, a b return a这段代码的时间复杂度是 O(n)空间复杂度是 O(1)——只有两个变量。对比记忆化的 O(n) 空间这是实打实的优化。而且它没有递归栈n 取一百万也不会栈溢出。这里有个 Python 的小细节挺有意思a, b b, a b这一行看起来像是先更新 a 再更新 b实际上 Python 会先把右边整个元组算出来再统一赋值所以等价于new_a b; new_b a b。如果你换成两行写a b b a b那就错了因为第二行的 a 已经被覆盖成 b 了算出来会得到另一个数列。这个坑我在带新人的时候见过至少五次都是在这一行上翻车。提示不确定顺序依赖的时候要么用元组同时赋值要么老老实实引入一个临时变量。别为了省一行代码写出隐蔽的 bug。3.3 空间复杂度从 O(n) 到 O(1) 的取舍有人会问既然滚动变量法已经是 O(n) 时间 O(1) 空间了是不是就完美了大部分场景下确实够用但有两个例外。第一个例外是需要频繁查询多组 F 值。比如你要算 F(10)、F(50)、F(100) 三次迭代法每次都要重跑一遍总耗时 O(n) × 查询次数。这时候先把整个数列算出来存成数组用 O(n) 空间换查询 O(1)反而更划算。这就是典型的空间换时间。第二个例外是只需要 F(n) 的某几位或者模某个数的结果但 n 极大。n 到 10^9 之后O(n) 的迭代本身就跑不完了这时候必须上对数级算法也就是下一节要讲的矩阵快速幂。我在做一道需要求 F(10^18) mod 10^97 的题时第一反应就是迭代然后立刻意识到 n 有十八位迭代要跑十年赶紧换成矩阵快速幂。所以空间复杂度的取舍不是孤立的它和查询模式、n 的规模强相关。我的经验判断标准是n 小于 10^7 且只查一两次用迭代n 小于 10^7 但要查很多次用打表n 大于 10^7直接上矩阵或倍增。4. 矩阵快速幂O(log n) 的工程写法4.1 递推式的矩阵形式推导这一步是整条优化链里最关键的一次视角转换。斐波那契的递推式是F(n) F(n-1) F(n-2)把它写成一个向量到向量的线性变换。取向量 [F(n), F(n-1)]它由 [F(n-1), F(n-2)] 经过一个矩阵变换得到[F(n) ] [1 1] [F(n-1)] [F(n-1)] [1 0] [F(n-2)]验算一下第一行给出 1·F(n-1) 1·F(n-2) F(n)对第二行给出 1·F(n-1) 0·F(n-2) F(n-1)也对。记这个 2×2 矩阵为 M [[1,1],[1,0]]那么反复代入得到[F(n) ] [F(1)] [1] [F(n-1)] Mⁿ⁻¹[F(0)] Mⁿ⁻¹[0]更进一步M 的 n 次幂有一个漂亮的结论Mⁿ [F(n1) F(n) ] [F(n) F(n-1)]这个式子的证明用数学归纳法两行就完事我就不展开了。它的实际价值在于求 F(n) 变成了求 M 的 n 次幂而幂运算可以用快速幂做到 O(log n)。整个思路的巧妙之处是把一个「加法递推」问题转化成了「矩阵乘法」而矩阵乘法满足结合律所以能二分。我用一个生活化的类比来解释为什么能加速。假设你要算 2 的 100 次方一个一个乘要乘 99 次但如果你先算出 2²再用它的平方得到 2⁴再平方得 2⁸……每次翻倍指数只要 7 步就能到 2^128再往回乘几个就能凑出 2^100。矩阵快速幂就是这个道理把 n 转成二进制遇到 1 就乘进结果每一步都把底数平方。4.2 快速幂模板与取模版本2×2 矩阵用四个变量表示比用二维列表快不少。下面是我常用的模板带不带取模都能用def mat_mul(A, B, modNone): a, b, c, d A e, f, g, h B x a * e b * g y a * f b * h z c * e d * g w c * f d * h if mod is not None: return (x % mod, y % mod, z % mod, w % mod) return (x, y, z, w) def fib_matrix(n, modNone): # 返回 F(n)M^n [[F(n1), F(n)], [F(n), F(n-1)]] result (1, 0, 0, 1) # 单位矩阵 base (1, 1, 1, 0) # M while n 0: if n 1: result mat_mul(result, base, mod) base mat_mul(base, base, mod) n 1 return result[1]我特意把矩阵压成了四个标量因为二维列表在 Python 里的下标访问开销不小实测压成元组之后快 30% 左右。取模参数mod设计成可选是因为有些题要求输出完整大数有些只要求模 10^97一个模板两种情况都能覆盖。复杂度方面定长整数比如 64 位内场景下循环跑 log n 次每次做常数次 2×2 矩阵乘法8 次乘法和 4 次加法所以时间复杂度严格是O(log n)空间 O(1)。n 10^18 也就是 60 轮循环眨眼就完事。n迭代法循环次数矩阵快速幂循环次数差距10^31000约 10100 倍10^6100 万约 205 万倍10^910 亿约 303000 万倍10^18跑不完约 60无法比较4.3 大整数场景下复杂度要重新算上面说的 O(log n) 有个前提整数是定长的一次乘法和一次加法都算 O(1)。但如果你要算 F(10^6) 的完整值而不取模情况就变了。F(n) 的二进制位数大约是 0.694n也就是说 F(10^6) 有将近 70 万位二进制接近 21 万位十进制数字。这种超长整数做一次乘法代价不是常数而是和位数相关的 M(n)。在 BigInt 场景下矩阵快速幂的总复杂度大致是O(M(n) · log n)其中 M(n) 是两个 n 位大数相乘的代价朴素算法是 O(n²)FFT 类算法可以做到接近 O(n log n)。换算成十进制位数 L ≈ 0.209n最终大约是 O(L² log n) 这个量级。这个结论听起来有点绕但实际影响很直观在 Python 里算 F(10^5) 的完整值还算流畅算 F(10^6) 就要等上几秒到十几秒算 F(10^7) 基本就别想了内存也扛不住。所以一旦脱离取模场景O(log n) 这个漂亮的结论就不再成立了。我在一次数据校验脚本里踩过这个坑。业务需要比对第 10^6 项斐波那契数的哈希值我按 O(log n) 估算觉得毫秒级结果实际跑了将近二十秒问题就出在大数乘法上。后来改成取模比对瞬间完成。教训是分析复杂度的时候一定要先确认基本运算的代价模型别把「O(1) 的加法」当默认前提。5. 通项公式、倍增法与五种写法横评5.1 比内公式的精度陷阱斐波那契的通项公式比内公式长这样F(n) (φⁿ - ψⁿ) / √5其中 φ (1 √5)/2 ≈ 1.618ψ (1 - √5)/2 ≈ -0.618。因为 |ψ| 1n 稍大一点 ψⁿ 就趋近于 0所以工程上常简化成 F(n) ≈ round(φⁿ / √5)。写成代码只要三行def fib_binet(n): phi (1 5 ** 0.5) / 2 return round(phi ** n / 5 ** 0.5)写法确实优雅复杂度看起来也是 O(log n)如果 φⁿ 用快速幂算但它有个致命的精度问题双精度浮点数只有大约 1517 位有效十进制数字而 F(n) 的位数随 n 线性增长。当 n 超过 70 左右时F(n) 已经超过 15 位浮点误差就会导致结果错位。我实测下来n71 开始就出现错误n79 之后错得离谱。有人会说那用decimal高精度库不就完了可以但高精度小数的每次乘法代价远超大整数乘法算到 n 几万就已经比自底向上的迭代法慢了。所以比内公式在工程里的定位很明确它是个数学上的漂亮结论和教学素材不是一个实用的算法。我自己只在需要快速估算量级比如判断 F(n) 有多少位数的时候用它。注意如果你在做面试题时写比内公式一定要主动说明精度限制和适用范围否则容易被判定为「知其然不知其所以然」。开卷考试也救不了这种情况。5.2 倍增法 fast doubling倍增法是矩阵快速幂之外另一条通往 O(log n) 的路而且在常数因子上通常更快因为它只涉及整数乘法和加法不需要维护四个矩阵元素。核心是两条恒等式F(2k) F(k) · (2·F(k1) − F(k))F(2k1) F(k)² F(k1)²这两条式子可以用矩阵的幂来验证也可以纯代数推导我这里不展开证明。有了它们就能像快速幂一样从高位往低位递推def fib_doubling(n): def helper(k): if k 0: return (0, 1) # (F(k), F(k1)) a, b helper(k 1) # a F(m), b F(m1), m k // 2 c a * (2 * b - a) # F(2m) d a * a b * b # F(2m1) if k 1: return (d, c d) # (F(2m1), F(2m2)) return (c, d) # (F(2m), F(2m1)) return helper(n)[0]我拿 n100 验证过结果是 354224848179261915075和迭代法一致。时间复杂度 O(log n)递归深度也是 O(log n)所以不像朴素递归那样会爆栈。如果写成迭代版空间还能降到 O(1)。实测对比一下在同一台机器上算 F(10^6) 取模 10^97矩阵快速幂大约 60 微秒倍增法大约 35 微秒确实快了一截。原因也不难理解矩阵版每次循环要做 8 次乘法和 4 次加法倍增法每次递归只做 4 次乘法和 3 次加法常数小了一半。5.3 横评表与选型建议把五种写法放到一起做个完整对照方便你直接抄作业写法时间空间适用 n 范围推荐场景朴素递归Θ(φⁿ)O(n)n ≤ 35教学演示、讲解递归树记忆化搜索O(n)O(n)n ≤ 10^4逻辑天然递归、不便改写自底向上迭代O(n)O(1)n ≤ 10^7通用首选、代码最简单矩阵快速幂O(log n)O(1)n 任意需要取模的大 n倍增法O(log n)O(log n) / O(1)n 任意追求常数、无取模我的选型逻辑非常固定基本三句话就能定n 小就迭代n 大成谜就矩阵或倍增需要反复查询就先打表。工程代码里能不用递归就不用递归因为递归的栈开销和深度限制都是额外的心智负担而迭代版只有四行可读性也不差。6. 把套路迁移到排序算法时间复杂度到底怎么算6.1 快排、归并、堆排的复杂度推导斐波那契这一整套分析方法其实是通用的。我拿排序算法再走一遍你能更明显感受到套路的一致性。归并排序的递归式是 T(n) 2T(n/2) O(n)。这个形式符合主定理a2b2n^log_b(a) n¹ n与 f(n) O(n) 同阶落在主定理的第二种情况所以 T(n) O(n log n)。归并的额外空间是 O(n)因为合并那一步需要一个和原数组等长的临时数组。快速排序的平均递归式也是 T(n) 2T(n/2) O(n)看起来和归并一样平均复杂度 O(n log n)。但它的最坏情况是 T(n) T(n-1) O(n)每次划分只把一个元素放到最终位置递归树退化成一条链解出来是 O(n²)。这就是为什么快排要随机化选基准——随机化之后退化的概率极低虽然理论上最坏还是 O(n²)但期望是 O(n log n)。注意这里强调的是期望复杂度不是最坏复杂度这两个概念经常被混淆。堆排序不涉及递归分析用的是另一套语言建堆是 O(n)不是 O(n log n)这点很多人答错然后做 n 次「取堆顶 下沉」每次下沉 O(log n)合计 O(n log n)。建堆为什么是 O(n) 而不是 O(n log n)因为它是从最后一个非叶节点往前逐个下沉不同层的节点下沉代价不同求和之后收敛到 O(n)——这是一个典型的摊还分析案例。排序算法平均时间最坏时间空间稳定性归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n) 栈不稳定堆排序O(n log n)O(n log n)O(1)不稳定冒泡排序O(n²)O(n²)O(1)稳定6.2 一套通用的复杂度分析流程总结下来我分析任何算法复杂度都走这五步你可以直接拿去用确定基本操作的代价模型。数组下标访问是 O(1)大整数乘法不是哈希表查询平均 O(1) 最坏 O(n)。这一步决定了后面所有推导是否成立。写出规模递推式。分治写 T(n) aT(n/b) f(n)线性递推写 T(n) T(n-1) f(n)带分支的写成多路。判断该用哪把尺子。等比例缩小的用主定理常数级缩小的用特征方程没有递归的用求和或摊还分析。检查上界是否紧。很多人算到 O(2^n) 就停了其实还能收紧到 Θ(φ^n)快排算到 O(n log n) 也要记得标注这是平均值。算空间。递归栈算不算进去临时数组算不算进去得说清楚。同一种算法的空间复杂度经常会因为这两种口径的差异报出不同答案。这五步用熟了之后看任何一个算法都能快速给出靠谱的复杂度判断。我自己做题的时候基本是下意识走完这五步很少出错。7. 踩坑实录与常见问题速查7.1 常见误区速查表这些年踩过的坑和见过的错误答案我整理成一张表出问题的时候可以直接对照现象可能原因排查方向递归版 n35 就卡住没加记忆化重复子问题爆炸加缓存或用迭代加了缓存还是慢缓存键设计不合理或者用了可变对象换整数键、用functools.cache迭代版结果不对同时赋值的顺序问题检查是否用了临时变量递归报 RecursionError默认深度限制 1000改迭代法别硬调限制矩阵版大 n 结果错没有取模导致整数溢出C/Java中途取模或用大数库矩阵版大 n 特别慢BigInt 乘法代价被忽略了改取模或换倍增法比内公式 n 大后出错浮点精度不足只在 n ≤ 70 用快排最坏超时基准选的是首元素遇到有序数组退化随机化或三数取中堆排序说建堆是 O(n log n)概念混淆建堆是 O(n)整体才是 O(n log n)7.2 实操心得最后分享几条我在实际写代码和带人过程中总结的经验。第一条别急着上最快的算法。我见过太多人一看到斐波那契就直接写矩阵快速幂结果 n 只有 20代码量多了十倍可读性还差。复杂度优化是有成本的代码越复杂出错概率越高。判断标准很简单先估算 n 的量级如果迭代法能在毫秒级跑完那就用迭代法。第二条写递归之前先画一遍调用树。fib(5) 的树只有 15 个节点手画一遍就能直观感受到重复有多严重也就明白了记忆化到底省下了什么。这个动作花不了两分钟但对理解的价值很大。第三条取模的位置很讲究。矩阵快速幂里如果只在最后取一次模中间过程会算出天文数字级别的大整数性能直接崩。正确做法是每一次矩阵乘法之后都取模。我见过因为漏了这一步程序从 60 微秒变成 3 秒的案例。第四条注意语言特性带来的隐性差异。Python 的整数是任意精度的不会溢出但会变慢C 和 Java 的 int 会溢出n 到 46 就超过 2^31 了必须换 long 或者提前取模。同一份算法逻辑换个语言可能就是完全不同的 bug 形态。第五条性能测试要固定环境。我前面给的耗时数据都是在同一个环境下测的你自己测的时候也要保证 CPU 频率、Python 版本、是否开启优化这些条件一致否则前后对比没有意义。有一次我在笔记本上测完换到台式机上重测数字差了四倍差点以为是自己代码写错了。说到扩展这套复杂度分析的思路其实还能往后走一步。如果哪天你遇到的是「斐波那契的变体」比如 F(n) a·F(n-1) b·F(n-2) c 这种带常数项和系数的形式矩阵快速幂照样能处理——把常数项也塞进向量里构造一个 3×3 的矩阵就行。我带过的一个人用这个技巧把一道看起来毫无头绪的递推题在十分钟内 AC 了当时他那个表情我到现在还记得。递推式只要能写成线性形式矩阵快速幂就永远是你的后备方案。 斐波那契数列时间复杂度：从O(2^n)到O(log n)的五种写法
斐波那契数列大概是每个写代码的人都绕不开的一道坎。它形式简单到一行就能写出来但围绕它的时间复杂度分析几乎把算法分析里最核心的几套工具全用了一遍递归树、主定理、特征方程、记忆化、动态规划、矩阵快速幂、倍增。我面过不少人也被人面过只要问到「斐波那契数列的时间复杂度是多少」能答出 O(2^n) 的一抓一大把但能说清为什么不是严格的 O(2^n)、为什么同一个数列能有从 O(φ^n) 到 O(log n) 的五种复杂度、以及在什么场景该用哪一种的就不多了。这篇文章我想把这条线从头到尾捋一遍不光是给结论更重要的是把每一个「为什么这么选」讲透。不管你是刚开始刷算法题的新手还是想把复杂度分析这块补扎实的老手看完应该都能自己动手把这几种写法复现出来并且知道在工程里该挑哪一个。全文的分析套路不止适用于斐波那契最后我会把它迁移到排序算法上聊聊排序法时间复杂度怎么算这件事。1. 先搞清楚一个问题为什么会有五种复杂度1.1 斐波那契的四种经典写法与对应复杂度很多人对斐波那契时间复杂度的第一印象就是「递归是 O(2^n)加个数组优化成 O(n)」。这个印象不算错但它只覆盖了这条路上的前两站。完整地看同一个 F(n) 至少有四种主流写法复杂度跨度大到离谱写法时间复杂度空间复杂度n100 可行否朴素递归O(φ^n)常被粗略说成 O(2^n)O(n) 递归栈不可行记忆化搜索O(n)O(n)可行自底向上迭代O(n)O(1)可行矩阵快速幂O(log n)O(1)可行倍增法fast doublingO(log n)O(log n) 栈 / O(1) 迭代版可行我第一次把这五种写法摆在一起对比的时候心里其实有点震撼一个连小学生都能理解的递推关系居然能从指数级一路压到对数级。这中间的每一步优化都不是靠「换个语言」或者「调个参数」实现的而是靠对问题结构的重新理解。朴素递归是把问题当成一棵树在展开记忆化是发现这棵树里有大量重复节点迭代是发现根本不需要树、顺着推就行矩阵快速幂则是发现递推本质是一个线性变换而线性变换可以快速幂。每一次复杂度的下降背后都是一次视角的升级。这里有个细节值得单独拎出来说复杂度不是一个问题的固有属性而是「算法 问题」这一对的属性。同一个斐波那契数列问「它的时间复杂度是多少」本身就是个不严谨的问法正确的问法是「用某某算法求斐波那契第 n 项时间复杂度是多少」。我在代码评审里见过太多次因为混淆这两件事而吵起来的场面本质上就是没说清楚在讨论哪种实现。提示以后凡是听到「XX 的时间复杂度」先在心里补一句「用什么方法算」。这个习惯能帮你避免一大半的无谓争论。1.2 复杂度分析的三把尺子递归树、主定理、特征方程分析递归算法的时间复杂度我习惯准备三把尺子按精度从低到高排是递归树、主定理、特征方程。斐波那契恰好是那种三把尺子都能用、但结论精度不同的典型案例。递归树最直观也最适合用来跟别人解释。把 fib(n) 画成一棵树根节点是 fib(n)左右子节点分别是 fib(n-1) 和 fib(n-2)一直展开到 fib(0) 和 fib(1)。这棵树有多少个节点就代表做了多少次函数调用。粗看每一层的节点数最多翻倍树高是 n所以上界是 O(2^n)。这个结论好记但它是松的——因为树的左右两边并不对称fib(n-2) 那一侧会先触底整棵树并不是满二叉树。主定理是处理 T(n) aT(n/b) f(n) 这种标准分治形式的。斐波那契的递归式 T(n) T(n-1) T(n-2) O(1) 里子问题规模是 n-1 和 n-2而不是 n/b所以严格来说主定理在这里并不适用。我见过不少题解硬套主定理得出 O(n^2) 或者 O(n^log2) 之类的奇怪结论就是栽在这一点上。主定理的适用前提是子问题规模等比例缩小这里只是常数级缩小条件不满足。特征方程才是这个问题的正解。把 T(n) T(n-1) T(n-2) 当成一个二阶线性齐次递推来处理设 T(n) x^n代入得 x^n x^(n-1) x^(n-2)两边除以 x^(n-2) 得到 x² x 1解出 x (1 ± √5) / 2。取主导的正根 φ (1 √5) / 2 ≈ 1.618于是 T(n) Θ(φ^n)。这就是那个常被误写成 O(2^n) 的真实答案。三把尺子给出的结论分别是 O(2^n)、不适用、Θ(1.618^n)。所以你在面试里回答「O(2^n)」不算错但如果能补一句「严格上界是 Θ(φ^n)O(2^n) 只是它的一个宽松上界」效果完全不一样。这句话我用了很多次每次都能把面试官的兴趣勾起来。2. 暴力递归的 O(2^n) 到底是怎么来的2.1 递归树展开与调用次数的精确推导先把朴素递归的代码摆出来就这么四行def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)现在来数这棵树到底有多少个节点。设 C(n) 为计算 fib(n) 需要执行的函数调用总次数。当 n ≤ 1 时只调用一次所以 C(0) C(1) 1当 n ≥ 2 时一次调用自身加上两个子调用的开销得到C(n) C(n-1) C(n-2) 1这个递推式和斐波那契本身长得几乎一样只多了一个常数项。多出来的常数项在渐进分析里不影响量级所以 C(n) Θ(φ^n)。如果想要求精确值可以解出闭式C(n) 2·F(n1) - 1。拿 n5 验一下F(6) 82×8-1 15实际数一遍确实是 15 次调用对得上。这个精确式子比 Θ(φ^n) 更有用因为它能直接估算耗时。我实测过几组数据Python 3.11单核不同机器会有差异量级参考即可n调用次数 C(n)Python 实测耗时说明20约 1.4 万约 2 ms无感25约 24 万约 30 ms无感30约 270 万约 0.3 s开始有感35约 3000 万约 3.5 s明显卡顿40约 3.3 亿约 40 s不可接受45约 36.7 亿约 7 min生产事故级别n 从 35 涨到 45只多了 10调用次数却涨了一百多倍。这就是指数爆炸的手感——参数线性增长耗时指数增长。我第一次看到 n45 把进程卡死七分钟的时候是真的盯着屏幕发了会儿呆。注意C(n) 2·F(n1) - 1 这个式子里 n 是入参F 是斐波那契函数本身。写文档的时候千万别写成 2·F(n)-1差一项就差一个 φ 倍估算耗时会偏。2.2 用特征方程把 2^n 修正到 φ^n很多人会问既然 Θ(φ^n) 才是紧的为什么教材和题解里到处都在写 O(2^n)我理解有三个原因说清楚了你就不会再纠结。第一个原因是教学上的便利。φ 是个无理数写起来丑而 2^n 好记、好比较对初学者建立「递归会爆炸」的直觉足够用。第二个原因是大 O 只要求上界O(2^n) 确实是 T(n) 的一个合法上界数学上没错只是不紧。第三个原因是面试沟通效率。你说 O(2^n)对方一秒就懂你说 Θ(1.618^n)对方可能还要在脑子里算一下。但如果你要真正做性能预估就必须用 φ^n。举个具体的例子假设我有一台机器每秒能跑 5000 万次递归调用想知道 n 最大能取多少才能在一秒内跑完。用 φ^n 估算C(n) ≈ 2φ^(n1)/√5令它等于 5×10^7解出 n ≈ log(5×10^7 × √5 / 2) / log(1.618) ≈ 38。而如果用 2^n 估算会得到 n ≈ 25.6也就是 n25 左右这个结论悲观了太多白白浪费了一半的性能空间。这个差异在真实工程里是会出事的。我曾经在一个配置热更新模块里见过用递归算斐波那契风格的分支数本来按 O(2^n) 估算觉得 n30 就够呛结果实际压测发现 n38 才到瓶颈白白多写了一套缓存层。后来把模型换成 φ^n 重新估才发现原来的担心是多余的。所以我的建议是面试可以答 O(2^n)但落到代码和容量规划一定用 φ^n。顺便说一个容易踩的坑。φ ≈ 1.618 这个数与斐波那契的通项是对应的F(n) ≈ φ^n / √5。有些同学会把这个式子和 T(n) Θ(φ^n) 混为一谈认为递归的时间复杂度就是 F(n)。严格说只差一个常数因子 2/√5 和一个线性项渐进意义下确实等价但写公式的时候最好把常数带上否则算具体耗时会有两倍左右的误差。2.3 实测数据背后的硬件常识上表里的耗时是我在本地测的换台机器数字会变但比例关系不变。这里有几个经验值值得记住方便你以后心算一次 Python 函数调用的开销大约在 50100 纳秒这个量级算上加法、比较、栈帧管理整体算下来每秒钟大概能跑 1000 万到 2000 万次简单的递归调用。C/C 里同样的递归每秒能跑 3 亿到 10 亿次比 Python 快 3050 倍。换成 Go 或者 Java大致在每秒 1 亿到 3 亿次这个区间。这意味着同样一份朴素递归代码在 Python 里 n40 就要跑 40 秒在 C 里可能 1 秒就出来了。我见过有人拿 Python 里 n35 卡顿的经历去否定整个递归写法这就有点冤枉了——在 C 里 n40 都能接受。判断一种写法能不能用一定要带上语言和执行环境这两个前提。再补一个冷知识递归版的空间复杂度是 O(n)指的是递归调用栈的最大深度也就是 n 层。很多人分析时间的时候很熟一被问到空间就懵。记住一点就行递归的空间开销等于栈的最大深度不是调用总次数。fib(n) 的调用树有 φ^n 个节点但任意时刻栈上最多只有 n1 层因为每次都是先一路往左走到 fib(0)回来再走右边。3. 记忆化与迭代把 O(φ^n) 压到 O(n)3.1 记忆化搜索的三行改造朴素递归慢在哪慢在重复计算。fib(3) 在整棵树里被算了几百万次每次结果都一样白白浪费。记忆化的思路很朴素算过一次就记下来第二次直接查表。在 Python 里改造量小到只需要一个装饰器from functools import lru_cache lru_cache(maxsizeNone) def fib_memo(n): if n 2: return n return fib_memo(n - 1) fib_memo(n - 2)加上lru_cache之后n1000 也就是毫秒级的事儿。复杂度分析也很直接每个 n 值对应的子问题只会被真正计算一次其余的调用都是 O(1) 的字典查询所以总共 n1 个子问题每个内部做一次加法和两次查表时间复杂度 O(n)。空间上缓存表存了 n1 项加上递归栈 O(n)总空间 O(n)。不过lru_cache不是万能的有几个坑得提前说清楚。第一Python 默认的递归深度限制是 1000 层n 超过 990 左右就会抛RecursionError得手动sys.setrecursionlimit。但把限制调得太高又有栈溢出的风险所以 n 很大时别硬用递归。第二lru_cache是有锁的多线程场景下有额外开销如果只是单线程计算用functools.cachePython 3.9会更轻量。第三缓存会一直占着内存不释放如果是在长驻服务里做频繁的小规模计算反而可能被这个缓存拖累。我在 Go 里也写过类似的记忆化通常就是开一个map[int]int或者[]int切片自己判空。Go 里我更推荐用切片而不是 map因为下标连续、缓存友好实测在 n10000 这个量级能快个两三倍。3.2 自底向上迭代与滚动变量记忆化是「自顶向下 查表」它的对称写法是「自底向上 递推」。既然 F(n) 只依赖前两项那我从 0 开始往上推就行了def fib_iter(n): a, b 0, 1 for _ in range(n): a, b b, a b return a这段代码的时间复杂度是 O(n)空间复杂度是 O(1)——只有两个变量。对比记忆化的 O(n) 空间这是实打实的优化。而且它没有递归栈n 取一百万也不会栈溢出。这里有个 Python 的小细节挺有意思a, b b, a b这一行看起来像是先更新 a 再更新 b实际上 Python 会先把右边整个元组算出来再统一赋值所以等价于new_a b; new_b a b。如果你换成两行写a b b a b那就错了因为第二行的 a 已经被覆盖成 b 了算出来会得到另一个数列。这个坑我在带新人的时候见过至少五次都是在这一行上翻车。提示不确定顺序依赖的时候要么用元组同时赋值要么老老实实引入一个临时变量。别为了省一行代码写出隐蔽的 bug。3.3 空间复杂度从 O(n) 到 O(1) 的取舍有人会问既然滚动变量法已经是 O(n) 时间 O(1) 空间了是不是就完美了大部分场景下确实够用但有两个例外。第一个例外是需要频繁查询多组 F 值。比如你要算 F(10)、F(50)、F(100) 三次迭代法每次都要重跑一遍总耗时 O(n) × 查询次数。这时候先把整个数列算出来存成数组用 O(n) 空间换查询 O(1)反而更划算。这就是典型的空间换时间。第二个例外是只需要 F(n) 的某几位或者模某个数的结果但 n 极大。n 到 10^9 之后O(n) 的迭代本身就跑不完了这时候必须上对数级算法也就是下一节要讲的矩阵快速幂。我在做一道需要求 F(10^18) mod 10^97 的题时第一反应就是迭代然后立刻意识到 n 有十八位迭代要跑十年赶紧换成矩阵快速幂。所以空间复杂度的取舍不是孤立的它和查询模式、n 的规模强相关。我的经验判断标准是n 小于 10^7 且只查一两次用迭代n 小于 10^7 但要查很多次用打表n 大于 10^7直接上矩阵或倍增。4. 矩阵快速幂O(log n) 的工程写法4.1 递推式的矩阵形式推导这一步是整条优化链里最关键的一次视角转换。斐波那契的递推式是F(n) F(n-1) F(n-2)把它写成一个向量到向量的线性变换。取向量 [F(n), F(n-1)]它由 [F(n-1), F(n-2)] 经过一个矩阵变换得到[F(n) ] [1 1] [F(n-1)] [F(n-1)] [1 0] [F(n-2)]验算一下第一行给出 1·F(n-1) 1·F(n-2) F(n)对第二行给出 1·F(n-1) 0·F(n-2) F(n-1)也对。记这个 2×2 矩阵为 M [[1,1],[1,0]]那么反复代入得到[F(n) ] [F(1)] [1] [F(n-1)] Mⁿ⁻¹[F(0)] Mⁿ⁻¹[0]更进一步M 的 n 次幂有一个漂亮的结论Mⁿ [F(n1) F(n) ] [F(n) F(n-1)]这个式子的证明用数学归纳法两行就完事我就不展开了。它的实际价值在于求 F(n) 变成了求 M 的 n 次幂而幂运算可以用快速幂做到 O(log n)。整个思路的巧妙之处是把一个「加法递推」问题转化成了「矩阵乘法」而矩阵乘法满足结合律所以能二分。我用一个生活化的类比来解释为什么能加速。假设你要算 2 的 100 次方一个一个乘要乘 99 次但如果你先算出 2²再用它的平方得到 2⁴再平方得 2⁸……每次翻倍指数只要 7 步就能到 2^128再往回乘几个就能凑出 2^100。矩阵快速幂就是这个道理把 n 转成二进制遇到 1 就乘进结果每一步都把底数平方。4.2 快速幂模板与取模版本2×2 矩阵用四个变量表示比用二维列表快不少。下面是我常用的模板带不带取模都能用def mat_mul(A, B, modNone): a, b, c, d A e, f, g, h B x a * e b * g y a * f b * h z c * e d * g w c * f d * h if mod is not None: return (x % mod, y % mod, z % mod, w % mod) return (x, y, z, w) def fib_matrix(n, modNone): # 返回 F(n)M^n [[F(n1), F(n)], [F(n), F(n-1)]] result (1, 0, 0, 1) # 单位矩阵 base (1, 1, 1, 0) # M while n 0: if n 1: result mat_mul(result, base, mod) base mat_mul(base, base, mod) n 1 return result[1]我特意把矩阵压成了四个标量因为二维列表在 Python 里的下标访问开销不小实测压成元组之后快 30% 左右。取模参数mod设计成可选是因为有些题要求输出完整大数有些只要求模 10^97一个模板两种情况都能覆盖。复杂度方面定长整数比如 64 位内场景下循环跑 log n 次每次做常数次 2×2 矩阵乘法8 次乘法和 4 次加法所以时间复杂度严格是O(log n)空间 O(1)。n 10^18 也就是 60 轮循环眨眼就完事。n迭代法循环次数矩阵快速幂循环次数差距10^31000约 10100 倍10^6100 万约 205 万倍10^910 亿约 303000 万倍10^18跑不完约 60无法比较4.3 大整数场景下复杂度要重新算上面说的 O(log n) 有个前提整数是定长的一次乘法和一次加法都算 O(1)。但如果你要算 F(10^6) 的完整值而不取模情况就变了。F(n) 的二进制位数大约是 0.694n也就是说 F(10^6) 有将近 70 万位二进制接近 21 万位十进制数字。这种超长整数做一次乘法代价不是常数而是和位数相关的 M(n)。在 BigInt 场景下矩阵快速幂的总复杂度大致是O(M(n) · log n)其中 M(n) 是两个 n 位大数相乘的代价朴素算法是 O(n²)FFT 类算法可以做到接近 O(n log n)。换算成十进制位数 L ≈ 0.209n最终大约是 O(L² log n) 这个量级。这个结论听起来有点绕但实际影响很直观在 Python 里算 F(10^5) 的完整值还算流畅算 F(10^6) 就要等上几秒到十几秒算 F(10^7) 基本就别想了内存也扛不住。所以一旦脱离取模场景O(log n) 这个漂亮的结论就不再成立了。我在一次数据校验脚本里踩过这个坑。业务需要比对第 10^6 项斐波那契数的哈希值我按 O(log n) 估算觉得毫秒级结果实际跑了将近二十秒问题就出在大数乘法上。后来改成取模比对瞬间完成。教训是分析复杂度的时候一定要先确认基本运算的代价模型别把「O(1) 的加法」当默认前提。5. 通项公式、倍增法与五种写法横评5.1 比内公式的精度陷阱斐波那契的通项公式比内公式长这样F(n) (φⁿ - ψⁿ) / √5其中 φ (1 √5)/2 ≈ 1.618ψ (1 - √5)/2 ≈ -0.618。因为 |ψ| 1n 稍大一点 ψⁿ 就趋近于 0所以工程上常简化成 F(n) ≈ round(φⁿ / √5)。写成代码只要三行def fib_binet(n): phi (1 5 ** 0.5) / 2 return round(phi ** n / 5 ** 0.5)写法确实优雅复杂度看起来也是 O(log n)如果 φⁿ 用快速幂算但它有个致命的精度问题双精度浮点数只有大约 1517 位有效十进制数字而 F(n) 的位数随 n 线性增长。当 n 超过 70 左右时F(n) 已经超过 15 位浮点误差就会导致结果错位。我实测下来n71 开始就出现错误n79 之后错得离谱。有人会说那用decimal高精度库不就完了可以但高精度小数的每次乘法代价远超大整数乘法算到 n 几万就已经比自底向上的迭代法慢了。所以比内公式在工程里的定位很明确它是个数学上的漂亮结论和教学素材不是一个实用的算法。我自己只在需要快速估算量级比如判断 F(n) 有多少位数的时候用它。注意如果你在做面试题时写比内公式一定要主动说明精度限制和适用范围否则容易被判定为「知其然不知其所以然」。开卷考试也救不了这种情况。5.2 倍增法 fast doubling倍增法是矩阵快速幂之外另一条通往 O(log n) 的路而且在常数因子上通常更快因为它只涉及整数乘法和加法不需要维护四个矩阵元素。核心是两条恒等式F(2k) F(k) · (2·F(k1) − F(k))F(2k1) F(k)² F(k1)²这两条式子可以用矩阵的幂来验证也可以纯代数推导我这里不展开证明。有了它们就能像快速幂一样从高位往低位递推def fib_doubling(n): def helper(k): if k 0: return (0, 1) # (F(k), F(k1)) a, b helper(k 1) # a F(m), b F(m1), m k // 2 c a * (2 * b - a) # F(2m) d a * a b * b # F(2m1) if k 1: return (d, c d) # (F(2m1), F(2m2)) return (c, d) # (F(2m), F(2m1)) return helper(n)[0]我拿 n100 验证过结果是 354224848179261915075和迭代法一致。时间复杂度 O(log n)递归深度也是 O(log n)所以不像朴素递归那样会爆栈。如果写成迭代版空间还能降到 O(1)。实测对比一下在同一台机器上算 F(10^6) 取模 10^97矩阵快速幂大约 60 微秒倍增法大约 35 微秒确实快了一截。原因也不难理解矩阵版每次循环要做 8 次乘法和 4 次加法倍增法每次递归只做 4 次乘法和 3 次加法常数小了一半。5.3 横评表与选型建议把五种写法放到一起做个完整对照方便你直接抄作业写法时间空间适用 n 范围推荐场景朴素递归Θ(φⁿ)O(n)n ≤ 35教学演示、讲解递归树记忆化搜索O(n)O(n)n ≤ 10^4逻辑天然递归、不便改写自底向上迭代O(n)O(1)n ≤ 10^7通用首选、代码最简单矩阵快速幂O(log n)O(1)n 任意需要取模的大 n倍增法O(log n)O(log n) / O(1)n 任意追求常数、无取模我的选型逻辑非常固定基本三句话就能定n 小就迭代n 大成谜就矩阵或倍增需要反复查询就先打表。工程代码里能不用递归就不用递归因为递归的栈开销和深度限制都是额外的心智负担而迭代版只有四行可读性也不差。6. 把套路迁移到排序算法时间复杂度到底怎么算6.1 快排、归并、堆排的复杂度推导斐波那契这一整套分析方法其实是通用的。我拿排序算法再走一遍你能更明显感受到套路的一致性。归并排序的递归式是 T(n) 2T(n/2) O(n)。这个形式符合主定理a2b2n^log_b(a) n¹ n与 f(n) O(n) 同阶落在主定理的第二种情况所以 T(n) O(n log n)。归并的额外空间是 O(n)因为合并那一步需要一个和原数组等长的临时数组。快速排序的平均递归式也是 T(n) 2T(n/2) O(n)看起来和归并一样平均复杂度 O(n log n)。但它的最坏情况是 T(n) T(n-1) O(n)每次划分只把一个元素放到最终位置递归树退化成一条链解出来是 O(n²)。这就是为什么快排要随机化选基准——随机化之后退化的概率极低虽然理论上最坏还是 O(n²)但期望是 O(n log n)。注意这里强调的是期望复杂度不是最坏复杂度这两个概念经常被混淆。堆排序不涉及递归分析用的是另一套语言建堆是 O(n)不是 O(n log n)这点很多人答错然后做 n 次「取堆顶 下沉」每次下沉 O(log n)合计 O(n log n)。建堆为什么是 O(n) 而不是 O(n log n)因为它是从最后一个非叶节点往前逐个下沉不同层的节点下沉代价不同求和之后收敛到 O(n)——这是一个典型的摊还分析案例。排序算法平均时间最坏时间空间稳定性归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n) 栈不稳定堆排序O(n log n)O(n log n)O(1)不稳定冒泡排序O(n²)O(n²)O(1)稳定6.2 一套通用的复杂度分析流程总结下来我分析任何算法复杂度都走这五步你可以直接拿去用确定基本操作的代价模型。数组下标访问是 O(1)大整数乘法不是哈希表查询平均 O(1) 最坏 O(n)。这一步决定了后面所有推导是否成立。写出规模递推式。分治写 T(n) aT(n/b) f(n)线性递推写 T(n) T(n-1) f(n)带分支的写成多路。判断该用哪把尺子。等比例缩小的用主定理常数级缩小的用特征方程没有递归的用求和或摊还分析。检查上界是否紧。很多人算到 O(2^n) 就停了其实还能收紧到 Θ(φ^n)快排算到 O(n log n) 也要记得标注这是平均值。算空间。递归栈算不算进去临时数组算不算进去得说清楚。同一种算法的空间复杂度经常会因为这两种口径的差异报出不同答案。这五步用熟了之后看任何一个算法都能快速给出靠谱的复杂度判断。我自己做题的时候基本是下意识走完这五步很少出错。7. 踩坑实录与常见问题速查7.1 常见误区速查表这些年踩过的坑和见过的错误答案我整理成一张表出问题的时候可以直接对照现象可能原因排查方向递归版 n35 就卡住没加记忆化重复子问题爆炸加缓存或用迭代加了缓存还是慢缓存键设计不合理或者用了可变对象换整数键、用functools.cache迭代版结果不对同时赋值的顺序问题检查是否用了临时变量递归报 RecursionError默认深度限制 1000改迭代法别硬调限制矩阵版大 n 结果错没有取模导致整数溢出C/Java中途取模或用大数库矩阵版大 n 特别慢BigInt 乘法代价被忽略了改取模或换倍增法比内公式 n 大后出错浮点精度不足只在 n ≤ 70 用快排最坏超时基准选的是首元素遇到有序数组退化随机化或三数取中堆排序说建堆是 O(n log n)概念混淆建堆是 O(n)整体才是 O(n log n)7.2 实操心得最后分享几条我在实际写代码和带人过程中总结的经验。第一条别急着上最快的算法。我见过太多人一看到斐波那契就直接写矩阵快速幂结果 n 只有 20代码量多了十倍可读性还差。复杂度优化是有成本的代码越复杂出错概率越高。判断标准很简单先估算 n 的量级如果迭代法能在毫秒级跑完那就用迭代法。第二条写递归之前先画一遍调用树。fib(5) 的树只有 15 个节点手画一遍就能直观感受到重复有多严重也就明白了记忆化到底省下了什么。这个动作花不了两分钟但对理解的价值很大。第三条取模的位置很讲究。矩阵快速幂里如果只在最后取一次模中间过程会算出天文数字级别的大整数性能直接崩。正确做法是每一次矩阵乘法之后都取模。我见过因为漏了这一步程序从 60 微秒变成 3 秒的案例。第四条注意语言特性带来的隐性差异。Python 的整数是任意精度的不会溢出但会变慢C 和 Java 的 int 会溢出n 到 46 就超过 2^31 了必须换 long 或者提前取模。同一份算法逻辑换个语言可能就是完全不同的 bug 形态。第五条性能测试要固定环境。我前面给的耗时数据都是在同一个环境下测的你自己测的时候也要保证 CPU 频率、Python 版本、是否开启优化这些条件一致否则前后对比没有意义。有一次我在笔记本上测完换到台式机上重测数字差了四倍差点以为是自己代码写错了。说到扩展这套复杂度分析的思路其实还能往后走一步。如果哪天你遇到的是「斐波那契的变体」比如 F(n) a·F(n-1) b·F(n-2) c 这种带常数项和系数的形式矩阵快速幂照样能处理——把常数项也塞进向量里构造一个 3×3 的矩阵就行。我带过的一个人用这个技巧把一道看起来毫无头绪的递推题在十分钟内 AC 了当时他那个表情我到现在还记得。递推式只要能写成线性形式矩阵快速幂就永远是你的后备方案。