1. 那次接口从 3ms 变成 40s源头就是一行递归先说结论斐波那契数列的时间复杂度是一道把递归写法和复杂度分析这两个坑一次踩全的经典题。它简单到小学生都能看懂代码又深到能把递归树、特征方程、矩阵快速幂、大数运算代价全串一遍。我最早把它当成一道练习题直到某次给一个数据校验服务做性能排查才发现这东西是真会出事的。那次的情况很典型一个批量校验接口输入是一串自增的序列号代码里有个工具方法用来算某种步长实现是这样的——if (n 2) return n; return f(n-1) f(n-2);。小数据量跑了几周都没问题直到上游把批次从几十条提到几百条n从 30 涨到 40接口响应时间直接从 3ms 跳到几十秒量级。n只加了 10耗时涨了四个数量级这就是指数级时间复杂度的真实手感。很多人对时间复杂度的理解停在背结论朴素递归是 O(2ⁿ)加个缓存是 O(n)矩阵快速幂是 O(log n)。但真要让你解释为什么是 2 的 n 次方而不是别的、为什么主定理在这里不能用、log n 的那个 log 是从哪儿冒出来的能说明白的人不多。这篇就把这条链路从头到尾拆一遍涉及的时间复杂度分析套路、时间复杂度和空间复杂度的取舍、以及怎么把这套方法迁移到排序之类的其他问题上我都会给出可以直接复用的思路。不管你是刚学算法的学生还是工作几年后想回头补一补基础的工程师下面这些内容都能直接用上。2. 递归树与递推式Θ(φⁿ) 是怎么被算出来的2.1 把代码翻译成递推式这一步不能跳分析复杂度的第一步永远是把代码翻译成数学式子。朴素递归的代码只有三行def fib(n): if n 2: return n return fib(n - 1) fib(n - 2)盯住执行次数这个基本操作。设T(n)表示计算fib(n)需要的总调用次数那么n 2时直接返回只算 1 次调用T(0) T(1) 1n ≥ 2时自己算 1 次再分别去算n-1和n-2T(n) T(n-1) T(n-2) 1这就是递推式。注意它是齐次线性递推系数是常数阶数是 2。这类式子在算法分析里非常常见只是大部分人一看到n-1和n-2就下意识觉得跟斐波那契长得一样那复杂度也是指数级吧然后就不往下算了。结论虽然对但过程丢了下次换个式子照样不会。2.2 递归树逐层求和得到 2F(n1) - 1 次调用把fib(5)的调用画成树你会看到每一层都在裂开根节点是fib(5)第二层是fib(4)和fib(3)第三层继续裂。这棵树有个特点——越往右下角越浅因为fib(3)那边的子树比fib(4)那边矮一截。数节点的办法是直接套斐波那契本身。设调用总数C(n)可以验证C(0) 1 C(1) 1 C(n) C(n-1) C(n-2) 1令C(n) 2*F(n1) - 1代进去正好成立F是标准的斐波那契F(0)0, F(1)1。所以n 30总调用2 × F(31) - 1 2,692,537约 269 万次n 40总调用2 × F(41) - 1 331,160,281约 3.3 亿次n 50已经到了 400 亿次量级这解释了我那次线上问题n从 30 到 40调用次数涨了 100 多倍。用 Python 跑fib(40)要几十秒用 C 也要一秒上下而fib(50)基本就没法等了。指数级复杂度最阴险的地方在于前期数据量小你完全感受不到它的存在。2.3 主定理为什么不适用于这个递推式很多人第一反应是套主定理Master Theorem。但主定理处理的是T(n) a·T(n/b) f(n)这种形式子问题规模必须是n的一个固定比例。斐波那契的递推式里子问题规模是n-1和n-2不是n/2也不是n/3比例随n变化所以主定理直接出局。这种减法型递推要用另外两把工具第一把是代入法猜 验证。已知F(n)的渐进值是Θ(φⁿ)其中φ (1√5)/2 ≈ 1.618。那就猜T(n) O(φⁿ)即假设存在常数c使得T(n) ≤ c·φⁿ。代入T(n) T(n-1) T(n-2) 1 ≤ c·φ^(n-1) c·φ^(n-2) 1 c·φ^n · (1/φ 1/φ²) 1关键点来了1/φ 1/φ² 1这是 φ 的定义性质因为φ² φ 1两边除以φ²就得到这个等式。所以右边化简成c·φⁿ 1。只要c取得足够大就能把1吞掉归纳假设成立。下界同理可证T(n) Ω(φⁿ)。合起来T(n) Θ(φⁿ)。现实中更常用的说法是等价于 O(2ⁿ)因为φⁿ 1.618ⁿ比2ⁿ小O(φⁿ)是更紧的上界。面试里说O(2ⁿ)通常不算错但能把它精确到Θ(1.618ⁿ)的人面试官会记住你。第二把是特征方程。忽略那个1它只影响常数项不影响渐进阶把T(n) T(n-1) T(n-2)写成特征方程x² x 1即x² - x - 1 0。解得两个根x₁ (1 √5)/2 ≈ 1.618 x₂ (1 - √5)/2 ≈ -0.618通解是T(n) A·x₁ⁿ B·x₂ⁿ。因为|x₂| 1它的 n 次方会迅速衰减到 0剩下的主导项就是A·x₁ⁿ即Θ(φⁿ)。这个方法比代入法更快也更适合面试现场口算。2.4 空间这一侧递归栈深度也是 n讨论时间复杂度和空间复杂度时最容易漏掉的是递归栈。朴素递归的额外空间不是 O(1)而是 O(n)——因为整棵树中最深的一条路径是fib(n) → fib(n-1) → fib(n-2) → ... → fib(0)长度正好是n。每一层都要保存当前帧的局部变量和返回地址。这意味着就算你把时间问题解决了空间上也扛不住大 nPython 默认递归深度限制是 1000n ≥ 1000直接抛RecursionErrorC 默认线程栈 1MB 左右递归太深会栈溢出崩溃。所以任何递归解法在工程里都必须先问一句这个递归深度我敢让它跑多大3. 从指数级降到对数级四种写法的复杂度对照3.1 备忘录递归用空间把重复子问题合并朴素递归慢的本质原因不是递归本身而是子问题被反复求解。fib(3)在fib(5)的调用树里会被算好几遍fib(2)更惨被算了上十遍。指数级的爆炸就是这种重复带来的。治它的办法很直接算过一次就记下来下次直接查表。这就是备忘录记忆化搜索from functools import lru_cache lru_cache(maxsizeNone) def fib(n): return n if n 2 else fib(n - 1) fib(n - 2)复杂度立刻从Θ(φⁿ)掉到Θ(n)每个n只会真正进入函数体一次后续都是 O(1) 的哈希查表。代价是空间——缓存表要存 n 个值加上递归栈的 O(n)总计 O(n)。提示lru_cache是个很好用的工具但它挡不住递归深度问题。fib(2000)照样会抛栈溢出因为 Python 的调用栈有上限。缓存解决的是重复计算不解决递归深度。3.2 滚动变量的迭代O(n) 时间O(1) 额外空间既然递推式是F(n) F(n-1) F(n-2)那要算第 n 项其实只需要保留前两项。这是把空间从 O(n) 压到 O(1) 的关键洞察def fib_iter(n): if n 2: return n a, b 0, 1 for _ in range(n - 1): a, b b, a b return b循环执行n-1次每次做一次加法和一次元组赋值时间复杂度Θ(n)变量只有a、b和循环计数器额外空间Θ(1)。n 多大都能跑唯一的限制是大整数本身的位数涨得快后面会讲。这种滚动数组手法特别通用动态规划里那些看起来要开二维表的题只要状态只依赖前几行就能压成一维甚至几个变量。斐波那契是最好的入门例子。3.3 矩阵快速幂与快速倍增把 log n 那一段拿到手Θ(n)在n 10时就是一秒钟的事但在n 10¹⁸比如某些数列取模的竞赛题时就彻底没戏了。这时候需要O(log n)级别的解法靠的是幂运算的二进制分解。矩阵形式的思路很干净。定义矩阵M [[1,1],[1,0]]那么Mⁿ [[F(n1), F(n)], [F(n), F(n-1)]]要求F(n)就是算Mⁿ然后取右上角。而算幂可以用二进制快速幂把指数n看成二进制从低位到高位每遇到一位就平方一次当前底数遇到 1 就把结果乘进去。指数的二进制位数是⌊log₂n⌋ 1所以只需要约log₂n次平方和最多log₂n次乘法。矩阵快速幂的代码量不小而且每次 2×2 矩阵相乘要做 8 次整数乘法和 4 次加法常数偏大。工程里更常用的是快速倍增法fast doubling本质上是把矩阵幂的对称性利用到极致只用两个恒等式F(2k) F(k) × (2·F(k1) − F(k)) F(2k1) F(k)² F(k1)²递归实现def fib_fast(n): def fd(k): if k 0: return (0, 1) # 返回 (F(k), F(k1)) a, b fd(k 1) # a F(m), b F(m1), m k // 2 c a * ((b 1) - a) # F(2m) d a * a b * b # F(2m1) return (d, c d) if (k 1) else (c, d) return fd(n)[0]每次递归把k折半深度是log₂n每层只做 2 到 3 次大整数乘法。常数比矩阵法小一大截。3.4 五种写法的横向对照写法时间复杂度额外空间n 40n 10⁵n 10¹⁸朴素递归Θ(φⁿ)O(n) 栈几十秒不可行不可行带缓存递归Θ(n)O(n)毫秒级栈溢出不可行滚动迭代Θ(n)O(1)微秒级可行不可行矩阵快速幂O(log n) 次乘法O(1)微秒级微秒级可行快速倍增O(log n) 次乘法O(log n) 栈微秒级微秒级可行这张表我最想让你记住的不是最后一列而是第三列在n 40这个日常规模下五种写法的差距其实只有毫秒和几十秒的区别很多人压根不会去优化。真正决定你要不要上O(log n)的是n的量级而不是算法本身的高级程度。4. 快速幂的 log 究竟藏在哪里以及它要付什么代价4.1 矩阵形式为什么成立先验证再相信Mⁿ的结论不是拍脑袋来的。先算M¹ [[1,1],[1,0]]右上角是F(1) 1左下角是F(0) 0成立。假设Mⁿ对n成立那么M^(n1) Mⁿ · M[[F(n1), F(n)], [[1, 1], [F(n), F(n-1)]] × [1, 0]] [[F(n1)F(n), F(n1)], [F(n)F(n-1), F(n)]] [[F(n2), F(n1)], [F(n1), F(n)]]右上角变成F(n1)正好符合M^(n1)的目标形式归纳成立。这个推导只有两步乘法值得在纸上自己写一遍——很多人用了一辈子矩阵快速幂却从没验证过它为什么对。4.2 二进制分解log n 的真正来源快速幂的核心洞察是幂运算满足结合律所以可以把指数拆成二进制位分别处理。比如要算M¹³把 13 拆成二进制1101 8 4 1于是M¹³ M⁸ · M⁴ · M¹。怎么高效得到M⁸一路平方M¹ → M² → M⁴ → M⁸三步就够了。而 13 的二进制只有 4 位log₂13 ≈ 3.7恰好对应这个步数。所以log n的来源非常具体它就是 n 的二进制位数。指数每翻一倍工作量的增量只有 1。这就是为什么n 10¹⁸时快速幂只需要约 60 步——因为 10¹⁸ 的二进制约 60 位。4.3 把乘法次数逐项数清楚抽象说O(log n) 次乘法容易糊弄过去具体数一下才踏实。快速倍增每层递归做的事情是一次折半递归调用计算c F(2m)一次减法、一次乘 2左移、一次乘法共 1 次大整数乘法计算d F(2m1)两次平方加一次加法共 2 次大整数乘法奇数分支多一次加法c d所以每层最多 3 次乘法深度log₂n总乘法次数约3·log₂n。对n 10¹⁸来说就是 180 次左右的乘法在现代 CPU 上基本是瞬间。矩阵快速幂那边每层一次矩阵平方8 次乘法 可能一次结果矩阵乘8 次乘法总数是8·log₂n到16·log₂n。快速倍增的常数大概是它的四分之一到五分之一这就是它更受欢迎的原因。4.4 递归深度只有 log n但大数本身要算账n 10¹⁸时递归深度只有 60栈完全不是问题这是快速倍增相对O(n)迭代的另一个优势。但这里有个容易被忽略的坑我们一直假设乘法是 O(1)可当结果超出机器字长时这个假设就崩了。F(n)的位数大约是0.694n个二进制位。算F(10⁶)就要处理约 69 万位的整数一次乘法的代价远超常数级。用最朴素的竖式乘法两个b位整数相乘是O(b²)而算法库里通常会换用 Karatsuba 或者 FFT 类方法把单次乘法压到O(b^1.585)甚至O(b log b)。把乘法代价代进去快速倍增的真实复杂度是O(M(n) · log n)其中M(n)是大整数乘法代价不是O(log n)。这个细节在面试里说出来会非常加分因为它说明你区分了**算术运算次数和位运算代价**这两个层次。在 n 不超过 64 位整数的范围里也就是n ≤ 93这个差异完全无所谓一旦上到大数它就成了主导项。5. 纸面复杂度之外的三个真实陷阱5.1 Binet 闭式公式的精度悬崖学过一点数学的人都知道斐波那契有通项公式Binet 公式F(n) (φⁿ − ψⁿ) / √5 其中 ψ (1−√5)/2 ≈ −0.618看起来很美好——一次幂运算就能出结果复杂度像是O(log n)甚至O(1)。但这条路在工程里基本是条死路。原因是浮点数的有效位数。双精度浮点double能精确表示所有不超过2⁵³ ≈ 9.0×10¹⁵的整数而F(79) 14472334024676221已经超过了这个范围。从n 79附近开始Binet 公式用 double 算出来的结果就会开始出现误差n再大一点就直接变成完全错误的数值。而且√5本身是无理数φ也只能用浮点近似表示误差会随φⁿ一起放大越算越离谱。我踩过这个坑早年在做一个小工具时用 Binet 公式算前 100 项前 78 项全对之后开始零星出偏差一直没找到原因最后才发现是浮点精度问题。凡是要求精确整数结果的场景浮点公式一律不能用。真要用闭式解只能上高精度有理数或符号计算库那还不如老老实实写快速倍增。5.2 整数溢出32 位在 n 47 就缴械了另一个极常见的坑是整型溢出。F(46) 1836311903还在 32 位有符号整数最大值 2147483647范围内F(47) 2971215073已经超了。所以用 Java 的int或者 C 的int32_t写循环n 47开始结果就是错的而且是那种不报错、直接给你一个负数的静默错误。换成 64 位无符号可以撑到F(93) 12200160415121876738F(94) 19740274219868223167超过2⁶⁴ − 1同样是溢出。选型上建议这样处理语言推荐做法安全上界Python直接用内置int任意精度无上限但大数运算会变慢Java用BigInteger别用longlong到 n 92C用boost::multiprecision或手写大数unsigned long long到 n 93JavaScript用BigInt注意后缀nNumber只到 n 78Go用math/big.Intuint64到 n 93注意 JavaScript 的Number是双精度浮点精确整数范围只到2⁵³所以F(79)就已经不可靠了——这和前面 Binet 公式踩的是同一个坑本质是同一个精度限制。5.3 小 n 下闭式解反而更慢常数因子的威力我在本地做过简单对比n在 100 以内时O(n)的滚动循环反而比快速倍增快原因就是常数因子循环里只是几个加法和赋值一次大整数乘法的成本要高出好几倍。快速倍增的优势要到n 10⁴以上才明显拉开。这个现象在很多算法里都存在渐进复杂度描述的是趋势不是绝对值。工程选型的正确姿势是先用复杂度筛掉不可行的方案比如Θ(φⁿ)直接出局剩下的候选里按实际数据规模做基准测试。n只有几十的时候上矩阵快速幂纯属自我感动。6. 把这套分析套路迁移到别的问题上6.1 分析时间复杂度通用四步斐波那契这套流程可以抽象成通用方法遇到任何算法都能照着走第一步确定基本操作。是加法比较还是乘法这个选择直接决定后面数什么。斐波那契里选的是函数调用次数换成排序就是元素比较和移动次数。第二步写递推式或求和式。递归结构写递推式循环结构写求和式。这一步不写出来后面全是空谈。第三步选工具求解。分治型子问题规模成比例用主定理减法型n-1、n-2用特征方程或代入法简单的求和直接算级数。判断依据就是子问题规模是不是 n 的固定比例。第四步别忘边界和空间。递归深度、缓存表大小、大数位数这些都是容易被漏掉的真实成本。再补一条经验务必区分最好、最坏和平均情况。斐波那契这里三种情况是一样的输入只有 n 一个维度但换成排序就完全不同了——快排平均O(n log n)、最坏O(n²)插入排序最好O(n)、坏起来也是O(n²)。分析的时候不说明是哪种情况等于没说。6.2 排序法的时间复杂度是怎么算出来的既然聊到排序就顺便把排序法时间复杂度怎么算这件事讲透因为它跟斐波那契是同一套方法的另一面。冒泡排序。双重循环外层走n-1趟内层最多比较n-1次所以总比较次数是n²/2量级即O(n²)。如果加一个本趟有没有交换的标志位已经有序的数组第一趟就能提前退出最好情况降到O(n)。空间上只用了交换用的临时变量O(1)。归并排序。递推式是T(n) 2T(n/2) O(n)子问题规模是n/2标准分治主定理第二种情况直接给出O(n log n)。log n的来源是递归树的高度——每层折半n折到 1 需要log₂n层每层合并的总代价是O(n)乘起来就是O(n log n)。空间上合并需要辅助数组O(n)。快速排序。平均情况下每次分区把数组切成两半递推式同样是T(n) 2T(n/2) O(n)得到O(n log n)。但最坏情况是每次分区都切出0和n-1递推式退化成T(n) T(n-1) O(n)求和得到O(n²)。这就是随机化选主元存在的意义——它不改变最坏情况但把最坏情况出现的概率压到极低。计数排序。它不比较元素而是开一个大小为k的计数数组k是值域遍历一次原数组统计、遍历一次计数数组输出总计O(n k)。空间也是O(k)。所以它只在k和n同量级时才有优势值域一大就退化。这里有个特别值得记住的结论基于比较的排序下界是Ω(n log n)。证明思路是决策树——n个元素的排列有n!种每次比较只能给出两种结果所以决策树至少有n!个叶子节点树高至少是log₂(n!)用 Stirling 近似展开log₂(n!) ≈ n log₂n − 1.44n即Ω(n log n)。计数排序之所以能突破这个下界是因为它压根没走比较这条路绕开了前提条件。把这套方法跟前面的斐波那契对照着看你会发现复杂度分析的核心动作始终是同一个把算法结构翻译成数学式子再用合适的工具求渐进阶。差别只在工具的选择上。6.3 时间换空间还是空间换时间给两条实战建议回到时间复杂度和空间复杂度的取舍我在实际项目里总结了两条经验。第一条约束先看输入规模的上限。别急着上高级算法。如果业务上n永远不超过 50那O(φⁿ)的朴素递归其实也能跑虽然丑但不会出事。先确认规模天花板再决定要不要优化——我见过太多为了理论上更快引入矩阵快速幂结果代码可读性暴跌、维护成本上升而实际数据规模压根用不上。第二条递归一定要设防。不管逻辑多清晰只要有递归就问自己三件事最大深度是多少会不会栈溢出能不能改成迭代斐波那契的三种解法里滚动的迭代版本永远是工程里的第一选择——O(n)时间、O(1)空间、不会爆栈、代码五行。快速倍增留给真正需要的大n和取模场景。最后分享一个我常用的验证技巧写完任何快速幂类的算法一定要跟前 50 项暴力结果逐项对拍。矩阵快速幂和快速倍增的索引极易写错比如F(n)和F(n1)搞混、奇偶分支写反而这类错误的典型特征是从某个位置开始整体偏移或者每隔几位错一个肉眼很难发现。拿一个O(n)的暴力版本做基准跑一遍全对再去测大数心里才踏实。我自己的快速倍增实现里那道if (k 1)的分支就写反过两次全靠对拍抓出来的。