学算法这么多年我一直觉得“时间复杂度”是最容易被低估的一个概念。很多人以为它只是面试前背的那几个符号O(1)、O(n)、O(n²)张口就来可真拿到一道题却说不清为什么这个循环是 O(log n)、那个递归是 O(2^n)。我自己也是被现实狠狠教育过一回才真正重视起来的做那道经典的“最大子数组和”时暴力解直接超时改成 O(n) 的写法瞬间通过同样一个问题效率和写法之间差出了几个数量级。从那天起我才明白时间复杂度不是考试用的抽象理论它是判断代码优劣的第一把尺子是所有算法题的“底层裁判”。这篇文章我想把时间复杂度这件事从头掰开讲透从大O符号的基本含义到递归、均摊这类进阶分析手段再用三道高频算法题做完整实战演示最后把我自己分析复杂度时踩过的坑全部整理出来。不管你是刚要入门算法的新手还是准备笔试面试、想系统梳理一遍的选手看完这篇文章之后你应该能独立分析任意一段代码的复杂度也能在做题时第一时间判断出该用什么量级的算法才不会超时。1. 时间复杂度到底是什么——从“数次数”到“看趋势”1.1 最容易踩的误区它不是“跑得快慢”很多初学者会下意识地把时间复杂度和程序的运行时长画等号觉得“我这个程序跑了 0.3 秒所以复杂度就是 0.3”。这个理解大错特错。我同样一段排序代码在一台老笔记本上和一台新发布的旗舰机上运行秒数可能差出去好几倍但这段代码的时间复杂度结论完全不变。原因在于时间复杂度衡量的不是“物理时间”而是“基本操作的次数”。你可以把“基本操作”理解成加法、比较、赋值、数组访问这类最底层的动作。一个程序需要执行多少次基本操作取决于输入数据的规模 n。关键是我们不看 n100 时具体执行了多少次而是看当 n 从 100 变成 1000、变成 10000 时操作次数会以什么“趋势”增长。用一个生活化的例子来说。你搬家时要把一堆书搬进新家如果一本一本亲自搬书从 100 本变成 1000 本你要跑的次数也差不多翻 10 倍这是“线性增长”。但如果你找了个大纸箱一箱能装 50 本那么装书和搬箱子的总工作量虽然也会随书本数量增长却不再是简单的一对一翻倍增长节奏完全不一样。时间复杂度研究的就是这个“增长节奏”而不是某一次搬了 5 分钟还是 8 分钟。1.2 把代码翻译成“次数公式”一眼看懂大O直觉要真正理解复杂度先要学会把一段代码“翻译”成操作次数的表达式。看一个最简单的求和函数def sum_list(arr): total 0 for i in range(len(arr)): total arr[i] return total我们逐行数一下初始化 total 执行 1 次循环体里的加法执行 n 次循环变量 i 的自增和与 n 的比较加起来大约是 n 次最后的 return 是 1 次。总次数大概是 2n2 左右。当 n 很大时那些常数项 2 和常数系数 2 根本不重要我们只关心它跟着 n 线性增长于是记作 O(n)。再看一个双重循环def count_pairs(arr): n len(arr) count 0 for i in range(n): for j in range(n): if arr[i] arr[j]: count 1 return count外层循环跑 n 次每跑一次内层循环又要跑 n 次所以“判断 arr[i] arr[j]”这个核心操作会执行 n × n n² 次。这就是 O(n²) 的由来。你不需要真的去数每一行代码只需要盯住“最深层循环体执行了多少次”这个次数就是复杂度的主角。有个判断技巧特别好用一段代码里如果看到一层循环那基本就是 O(n)看到两层嵌套循环就是 O(n²)三层嵌套就是 O(n³)。当然前提是循环变量都老老实实每次加 1。如果循环变量不是线性变化那就得多个心眼这类情况我放到下一节重点讲。2. 常见复杂度的“脾性”与辨认技巧2.1 七个最常出场的复杂度量级与它们的“性子”我在做题和面试中接触到的代码复杂度几乎都落在下面这七个档位里。把它们放在一张表里对比一眼就能看出差别大O记号俗称典型代码增长感觉O(1)常数时间数组按下标访问、哈希表查找无论 n 多大次数基本不变O(log n)对数时间二分查找、平衡树操作n 翻倍时次数只增加一点点O(n)线性时间单层循环扫描数组n 翻倍次数也翻倍O(n log n)线性对数时间归并排序、快速排序比线性稍快但可接受O(n²)平方时间双重嵌套循环n 一变大次数暴涨O(2^n)指数时间朴素递归枚举所有子集n 超过 20 基本没法跑O(n!)阶乘时间枚举全排列n 超过 10 就非常吃力光是看这张表可能还不够直观我给几个具体数字感受一下。假设 n1000O(1) 永远是 1 次O(log n) 大约 10 次O(n) 是 1000 次O(n log n) 是 10000 次上下O(n²) 是 100 万次。如果 n 涨到 100000O(n²) 就变成 100 亿次哪怕一台每秒能跑 1 亿次基本操作的电脑也要 100 秒才能跑完这在算法竞赛和面试笔试里已经属于彻底超时的级别。所以复杂度不是“锦上添花”的概念它直接决定了一个程序在真实世界里能不能用。2.2 循环、递归、嵌套一套“一眼看穿”的快速口诀很多人拿到复杂度不会分析是因为只会背结论不会判断新代码。我总结了一套自己的口诀循环看嵌套递归看分支变量看步长。先说循环。一重循环而且变量每次加 1就是 O(n)两重嵌套就是 O(n²)三重嵌套就是 O(n³)这个前面已经说过。但要注意一种特例——循环变量不是“每次加 1”而是每次翻倍或者每次减半i 1 while i n: i i * 2这段代码的执行次数不是 n而是 log₂(n) 左右。因为 i 的增长是 1、2、4、8、16要乘上大约 log₂(n) 次才能超过 n。这就是 O(log n) 的经典来源。反过来如果从 i n 开始每次除以 2道理完全一样也是 O(log n)。再说递归。递归的复杂度适合用“递归树”来看先看层数递归深度再看每一层有多少个分支两者相乘就是总次数。比如二分查找每次都只走一个分支递归深度是 log n每层只做常数操作所以是 O(log n)。而归并排序每一层分成两个子问题层数还是 log n但每一层合并要扫描 n 个元素所以是 O(n log n)。最坏的情况是朴素斐波那契那样每个节点分裂成两个递归深度 n总共产生大约 2^n 个节点复杂度就是指数级。我自己在做题时有个习惯看完一段递归代码先画三层递归树再观察分支数和层数比对着公式硬套要可靠得多。递归树画熟练之后很多所谓“很难”的复杂度题其实一眼就能看出答案。3. 复杂度分析的三种实用工具3.1 大O的“丢常数、留主项”为什么O(3n²5n1)就是O(n²)新手常犯的一个错误是把复杂度精确到每一项比如写出“O(3n²5n1)”。这种写法不能说错但没有意义。大O表示法的核心思想是“渐进分析”也就是只看 n 趋向无穷大时的主导项。这个取主项的过程可以总结成两条规则去掉低阶项去掉常数系数。为什么能去掉因为当 n 足够大时n² 和 3n² 的差距只是一个常数倍而常数倍不会改变“增长趋势”的本质。n² 永远不会被 5n 追上不管前面的系数是 3 还是 300。这就像你开车从北京到上海决定耗时量级的是两地之间那 1000 多公里的路程而不是你多踩了几脚刹车——那点微调不改变“这是一次长途驾驶”的本质。这个思想在你写代码的时候特别有用。遇到一段复杂逻辑不用一上来就精确计算每个操作先问自己三个问题最内层循环的规模是多少有没有嵌套有没有递归分支答案出来复杂度基本就定了。剩下的常数项优化比如用位运算代替乘法、减少不必要的函数调用可以放到后面再做但大方向上千万别搞错否则优化得再细也白搭。3.2 递归分析利器简化版主定理递归函数的复杂度计算最让人头疼。网上有很多严格的数学推导但绝大多数时候你只需要一个工具——主定理Master Theorem的简化版。你只需要把递归式写成标准形式T(n) aT(n/b) f(n)其中 a 是子问题个数n/b 是每个子问题的规模f(n) 是“分解和合并”所需的时间。然后比较两个量n^(log_b a) 和 f(n)。如果前者大答案是 O(n^(log_b a))如果后者大答案是 O(f(n))如果两者相等答案要在中间乘一个 log n也就是 O(f(n) log n)。举两个最典型的例子。二分查找的递归式是 T(n) T(n/2) O(1)这里 a1b2n^(log_2 1) n^0 1和 f(n)1 相等所以结果是 O(1 × log n) O(log n)。归并排序的递归式是 T(n) 2T(n/2) O(n)这里 a2b2n^(log_2 2) n和 f(n)n 相等所以结果是 O(n log n)。要提醒一点主定理只适用于“规整”的递归式也就是子问题规模均匀缩小、且合并开销符合多项式形式的情况。如果遇到一个递归里同时调用了多个不同规模的子问题比如 T(n) T(n/2) T(n/3) O(n)主定理就帮不上忙了这时候老老实实画递归树更靠谱。3.3 均摊分析像“记账本预算”一样看复杂度还有一个很多人没听过、但实际代码里处处都在用的分析工具叫均摊分析。它的意思很简单某一次操作可能很贵但如果把成本摊到一整段操作序列上平均每次的成本其实很低。最典型的例子是 Python 列表的 append 操作。Python 的 list 底层是动态数组容量不够时要扩容扩容就要把旧元素复制到新数组这一次操作是 O(n) 的。如果只看这一次你会以为 append 是 O(n)但实际上 append 的平均复杂度是 O(1)。因为扩容采用的策略通常是“容量翻倍”假设数组从 1 扩到 2、2 扩到 4、4 扩到 8一共扩容 O(log n) 次每次复制的总成本加起来也就 O(n)摊到 n 次 append 上每次就是 O(1)。我建议你把均摊分析理解成家庭记账某个月的房贷还款特别高但那是因为把一整年的预算集中到一个月还了按年度看每个月的平均支出并没那么夸张。很多数据结构题里一个看起来很昂贵的操作比如删除后重新平衡、哈希表扩容摊还后复杂度都会降下来。做题时如果遇到“单次操作 O(n)但整体摊还 O(1)”的结论先别急着怀疑自己这大概率就是均摊分析的功劳。4. 相关题目实战三道高频题把复杂度落实到代码4.1 题型一最大子数组和——暴力O(n²)到动态规划O(n)理论讲再多不如拿题目走一遍。我选的第一道题是 LeetCode 53 最大子数组和也是我当年被“复杂度教育”的同一道题。暴力想法很自然枚举所有子数组算每个子数组的和并取最大值。子数组的起点有 n 种、终点有 n 种再分别求和总复杂度是 O(n³)稍微优化一下固定起点后边移动终点边累加可以把求和那层嵌套去掉降到 O(n²)。但 n 到 10 万级别时O(n²) 根本跑不动。正确的 O(n) 解法核心是状态转移设 cur 表示“以当前位置结尾的最大子数组和”那么 cur max(x, cur x)。翻译成人话要么把当前元素加到之前的子数组上要么干脆从当前元素重新开始一个新的子数组。整个过程只需要一重循环def max_subarray(nums): best nums[0] cur 0 for x in nums: cur max(x, cur x) best max(best, cur) return best为什么能从 O(n²) 降到 O(n)因为原来的暴力解法把“以 i 结尾的所有子数组”从头算了一遍存在大量重复计算而动态规划只保留了一个滚动变量 cur把过去的信息浓缩成了一个值。这就是复杂度的意义所在同样的结果换个记录信息的方式复杂度能降一个甚至几个量级。4.2 题型二滑动窗口——为什么总次数是2n而不是n²第二道题是“无重复字符的最长子串”。题目给定一个字符串 s要求找出不含重复字符的最长子串长度。暴力解法是枚举所有子串用集合判断子串内是否有重复字符复杂度高达 O(n³)即使优化到从每个起点直接扩展最坏也有 O(n²)。正确的做法是用双指针维护一个滑动窗口右指针不断向右扩展把字符加进集合如果发现重复就移动左指针把左边字符移出集合直到窗口重新合法。def length_of_longest_substring(s: str) - int: window set() left 0 ans 0 for right in range(len(s)): while s[right] in window: window.remove(s[left]) left 1 window.add(s[right]) ans max(ans, right - left 1) return ans我当时第一次看这个解法时最困惑的问题是内层还有个 while那它不可能是 O(n²) 吗答案是否定的原因是左指针和右指针各自都最多从头移动到尾。右指针总共移动 n 次左指针也只移动 n 次两个指针加起来一共移动 2n 次所以总复杂度是 O(n)不是 O(n²)。这个“两个指针各走一遍”的思路正是均摊分析最直观的应用场景。以后判断双指针复杂度时别只看循环嵌套层数先看指针是否会在整个过程中“来回反复走动”。4.3 题型三二分答案——把O(n)的搜索空间压成O(log n)第三道题是最经典的“猜数字大小”。系统会随机选中一个 1 到 n 之间的数字你每次猜一个数系统告诉你猜大了、猜小了还是猜中要求用最少次数猜出来。最笨的方法是线性扫描从 1 试到 n最坏要猜 n 次O(n)。但这个问题有一个非常强的特征——单调性如果 mid 猜小了答案一定在右边如果猜大了答案一定在左边。每次猜测都能排除掉一半的区间于是整个搜索空间每次折半复杂度就是 O(log n)。n 就算到 10 亿也只需要猜大约 30 次。def guess_number(n: int) - int: low, high 1, n while low high: mid (low high) // 2 res guess(mid) if res 0: return mid elif res 0: high mid - 1 else: low mid 1 return -1这类“二分答案”的问题非常值得练因为判断一个题目能不能用二分根本依据就是“单调性”。你可以把二分的搜索空间想象成一根滑轨答案在某个位置左边都满足一种条件右边都满足另一种条件。只要你的问题满足这个性质就可以放心地把 O(n) 的线性枚举压成 O(log n)。在很多算法题里这一步优化是能不能通过的关键分水岭。5. 常见问题与排查技巧实录5.1 面试吐槽我的O(n²)为什么比O(n)还快我在实际教学和带人的过程中几乎每个新手都会问一个问题“我写的暴力 O(n²)怎么测出来比同学写的 O(n) 还快是不是复杂度理论有问题”答案很简单复杂度描述的是“渐进趋势”但它不决定“小规模下的绝对速度”。如果你的 n 只有几十或者几百那 O(n²) 和 O(n) 的运行时间可能都在毫秒级此时常数的影响反而更大。比如一个 O(n) 的算法内部做了大量复杂的对象创建和函数调用而一个 O(n²) 的算法内部只是简单的数值比较前者在小数据下完全可能跑得更慢。写代码时既要有复杂度的大局观也不能忽略常数优化。我自己的习惯是先保证复杂度量级正确再针对最热的执行路径做微优化顺序千万别反过来。5.2 递归复杂度总算错漏算“每一层的开销”分析递归复杂度时最常见的错误是只看层数不看每层做了什么。比如 T(n) T(n/2) O(n)有人一看递归深度是 log n直接写成 O(log n)大错特错。正确的分析是每一层合并或处理都要花 O(n)、O(n/2)、O(n/4) 的时间把这些加起来是 n n/2 n/4 …这是一个收敛的等比级数结果约等于 2n所以总复杂度是 O(n)不是 O(log n)。你可以这样理解层数只有 log n 层没错但最上面那一层就要处理 n 个元素光这一层的开销就压过了下面所有层。分析递归时不要只数层数还要把每一层的总工作量加起来看否则很容易得出一个过于乐观的错误结论。5.3 复杂度对了却仍然超时先看数据规模再动手最后一个我特别想强调的经验拿到题目第一件事永远是看数据范围而不是急着写代码。数据范围直接告诉你需要什么量级的算法选错量级后面优化细节都白费。我自己常用的一个粗略对照表如下输入规模 n建议复杂度上界说明n ≤ 20O(2^n) 或更高可以枚举子集、状态压缩n ≤ 1000O(n²)双重循环勉强能过n ≤ 10^5O(n log n)排序级别需要优化n ≤ 10^6O(n)线性扫描n ≥ 10^9O(log n) 或 O(√n)只能用二分、数学公式等这个表的基准是我常用的评测环境大约 1 秒内能执行约 1 亿次简单操作。如果 n 是 10^5你一个 O(n²) 就有 10^10 次操作等 10 秒都不奇怪而一个 O(n log n) 的算法只要几十毫秒。养成“看数据范围定算法”的习惯之后你基本能告别“提交前心里没底”的状态。我写代码前喜欢先心算一遍“最坏情况的 n 代入我的主循环体大概执行多少次”超过千万级别就要停下来想想有没有更优的解法。5.4 一个安利了无数次的提交前自检习惯最后分享一个我坚持了很久的小习惯写完代码、提交之前花二十秒做一个“复杂度自检”。数一遍主循环的嵌套层数确认每个循环变量的变化方式是线性还是倍增看一眼递归函数的递归树分支数和深度最后把题目给的最大 n 代入自己估计的复杂度公式看操作次数是否是千万到亿级别以内。如果超了赶紧回头找优化空间。这个方法救过我很多次也帮我在面试时能提前预判自己写的是不是最优解。复杂度分析不是“算”出来的它更像一种肌肉记忆练习得越多看到代码时就越能条件反射地给出量级判断。