面试聊到算法十次有八次会绕到时间复杂度上。我带过几个新人也做过几轮技术面试最常见的画面是这样候选人刷刷写完两数之和我问一句你这个解法的时间复杂度是多少对方愣一下然后说差不多是 O(n) 吧。再追一句那 T(n) 是多少这个 O(n) 又是怎么推出来的基本就卡住了。很多人能背出二分查找是 O(log n)、冒泡排序是 O(n²)但真让他从代码一行一行数出 T(n)再一步步化简成渐进时间复杂度 O(n)中间那套逻辑其实是断的。这篇东西就是来补这段逻辑的。我会从最原始的问题讲起——T(n) 是什么、渐进时间复杂度 O(n) 是什么、两者什么关系然后拿几段真实代码手把手数操作次数再把推导过程完整走一遍最后聊聊怎么在真实项目里用它们做决策以及我这些年踩过的坑。不管你是刚开始学数据结构的学生还是工作几年想把基础捡回来的开发看完应该都能自己动手推一遍。1. 先把 T(n) 和 O(n) 的分工理清楚1.1 一段真实代码引出的困惑先看一段再普通不过的代码就是数组求和int sum(int a[], int n) { int s 0; for (int i 0; i n; i) { s a[i]; } return s; }有人会说这是 O(n)。对但为什么是 O(n) 而不是 O(3n5) 或者 O(2n)这个问题看着无聊其实是理解整件事的入口。因为这段代码实际执行的机器指令数量跟 n 之间就是一个线性关系——n 翻一倍执行的指令数量大致也翻一倍。至于前面挂的那个系数是三还是五在 n 变成一百万的时候根本不重要重要的是那条直线的形状。我们平时说的这段代码的时间复杂度是 O(n)其实包含了两层信息第一层是T(n)也就是这段代码在输入规模为 n 时实际执行了多少次基本操作它是一个带常数项和系数的具体函数第二层是渐进时间复杂度 O(n)也就是把 T(n) 里那些低阶项和常数系数全扔掉之后剩下的那个描述增长趋势的量级记号。前者是账本后者是账本记账趋势的抽象。搞混这两层后面的推导就会全是玄学。1.2 T(n)把代码的执行代价翻译成函数T(n) 的定义很朴素算法执行的基本操作次数关于输入规模 n 的函数。关键词是基本操作和输入规模。输入规模 n 在不同的题目里含义不一样。数组类题目里 n 通常就是元素个数字符串题目里 n 可能是字符长度图论里可能是顶点数 V 或者边数 E甚至同时是两者矩阵相关的问题n 可能是矩阵的边长那总元素数就是 n²。这个必须先定清楚定错了后面全白算。基本操作的定义则要看你关心什么代价。如果关心的是比较次数那基本操作就是一次比较关心的是一般运算量可以粗略把一次赋值、一次算术运算、一次数组访问都算作一个单位。学术上严格定义的时候会固定一种单位代价的 RAM 模型让每条简单指令耗费常数时间——这也就是为什么 T(n) 里可以出现 3n5 这种写法因为每条指令的代价都归一化了。举个具体的例子把上面那段求和代码拆开数int sum(int a[], int n) { int s 0; // 赋值 1 次 for (int i 0; i n; i) { // i 0 执行 1 次 // 比较 i n 执行 n 1 次 // i 执行 n 次 s a[i]; // 每次循环体一次数组访问 一次加法 一次赋值 } return s; // 返回 1 次 }把它加起来初始化 1 次比较 n1 次自增 n 次循环体被执行 n 次每次按 3 个单位算就是 3n 次最后返回 1 次。合起来 T(n) 1 (n1) n 3n 1 5n 3。这个 5 和 3 取决于你把哪些操作算作基本操作不同的人数出来可能是 4n2也可能是 6n5。这没关系因为后面化简成 O(n) 之后这些差异全都会消失。T(n) 的意义不在于精确到个位数而在于把运行时间这个物理量翻译成了一个可以推理的数学对象。那么哪些情况 T(n) 不是 n 的简单函数取决于输入形态的时候。比如在一堆数里找 target最好情况第一个就是T(n)1最坏情况跑到末尾T(n)n平均情况假设等概率期望比较次数是 (n1)/2也就是约 n/2。所以讨论 T(n) 的时候务必同时说清楚是最好、最坏还是平均这三个函数长得完全不一样。工程上我通常只关心最坏情况因为它给出了一个不会被打脸的承诺。1.3 O(n)只管趋势不管零头现在到了渐进时间复杂度。它的核心思想一句话就能讲完当 n 足够大的时候T(n) 的增长速度由哪一项主导。回到 5n3。n 取 10 的时候是 53n 取 1000 的时候是 5003n 取一百万的时候是 5000003。你会发现随着 n 变大那个 3 的存在感越来越低最后几乎可以忽略。同时那个系数 5 也只是让整条曲线整体抬高一点不改变它是直线的这件事。所以 5n3、100n、0.01n999 这些函数虽然绝对值差很多但形状是同一类——都随 n 线性增长于是它们统统归入 O(n)。同理3n² 100n 7 归入 O(n²)因为 n 很大时 n² 项把 n 项按在地上摩擦。2^n n^100 归入 O(2^n)因为指数增长最终会碾压任何多项式。这个谁主导的判断就是渐进分析的全部精髓。正式一点的写法是如果存在正常数 c 和 n₀使得对所有 n ≥ n₀都有 0 ≤ T(n) ≤ c·g(n)就记作 T(n) O(g(n))。拿 5n3 举例取 c 6、n₀ 3验证一下n ≥ 3 时5n3 ≤ 6n 显然成立因为 3 ≤ n。所以 5n3 O(n) 得证。取 c 100、n₀ 1 也可以这个不等式对一整族 (c, n₀) 都成立我们只需要找到任意一组就够了。这里有个容易误解的点O 给出的是上界不是紧确界。5n3 既是 O(n)也是 O(n²)还是 O(n³)因为 n² 确实能盖住它取 c1, n₀6 即可。但习惯上我们说它的复杂度是 O(n)是在给一个尽量紧的上界。学术写作里如果要强调紧确会用 Θ 记号这个下面单独说。1.4 大 O、大 Ω、大 Θ 三兄弟到底怎么分这三个记号经常被混着用但分工明确记号含义直觉理解例对 5n3 而言O渐进上界不会比这个更慢O(n)、O(n²) 都成立Ω渐进下界不会比这个更快Ω(n)、Ω(1) 都成立Θ渐进紧确界上下界同阶不多不少Θ(n) 成立Θ(n²) 不成立工程实践中大家张口就来的时间复杂度八成指的是 O。但你要知道说快速排序的时间复杂度是 O(n log n)严格来讲是不严谨的因为快排最坏情况会退化到 O(n²)。更准确的说法是快排平均时间复杂度 Θ(n log n)最坏 O(n²)。面试时如果被追问这一点能把最坏和平均分开讲加分不少。还有一个反直觉的坑O 记号写等号是不对称的。我们可以写 5n3 O(n)但不能写 O(n) 5n3。更严格的说法是 5n3 ∈ O(n)把 O(n) 理解成一个函数集合。有些教材里会出现 O(n) O(n²) 这种写法意思是前者是后者的子集方向不能反过来。这个细节在写论文或者做严格推导的时候必须注意平时沟通倒无所谓。2. 从代码到 T(n)手把手数清楚每一行2.1 基本操作的认定标准与计数规则要把代码变成 T(n)第一步是选定计数口径。我的习惯是遵循三条规则简单但够用第一条划定输入规模。写清楚 n 指的是什么有没有第二个规模参数比如矩阵乘法的 m、n、p。第二条只数随 n 变化的操作。常量级别的初始化、函数调用入口开销可以统一打包成一个常数项最后反正会被扔掉。第三条循环看层数和执行次数。单层循环跑 n 次就是 n双层嵌套各跑 n 次就是 n²但如果是那种内层依赖外层的三角形循环总次数是 n(n1)/2仍然是 O(n²)只不过常数系数减半。第三条里有个特别容易错的点判断内层循环跑多少次要看内层变量的增量方式。看这段for (int i 1; i n; i * 2) { printf(%d, i); }这不是 O(n)是 O(log n)。因为 i 每次翻倍从 1 涨到 n 需要 log₂n 次。再比如for (int i 0; i n; i) { for (int j i; j n; j) { swap(a[i], a[j]); } }内层次数分别是 n、n-1、n-2……1合计 n(n1)/2T(n) n²/2 n/2化简还是 O(n²)。这种半个 n²在数据量大的时候能实打实省一半时间所以有时候 O 相同的两个算法性能差异会很大这是后话。2.2 顺序、分支、循环三种结构的合成规则有了单条语句的计数结构化的代码就可以按规则合成 T(n)顺序结构T T₁ T₂ ... Tₖ直接相加。分支结构T 最坏那条分支的代价取 max如果要算平均就按分支概率加权求和。循环结构T 循环体代价 × 迭代次数 每次判断的代价。嵌套循环就是乘法。拿一个真实点的例子——在一维数组里找最大值和最小值void findMinMax(int a[], int n, int *mn, int *mx) { *mn *mx a[0]; for (int i 1; i n; i) { if (a[i] *mn) *mn a[i]; if (a[i] *mx) *mx a[i]; } }初始化占常数 1循环跑 n-1 次每次最多两次比较加最多两次赋值取最坏情况是 4 个单位。所以 T(n) 1 4(n-1) 4n - 3渐进复杂度 O(n)。这也说明一件事同时找最大最小只需要一遍扫描不需要像新手那样排个序再取首尾——排序是 O(n log n)白花了好几倍的时间。这种用复杂度算账的能力在写业务代码时比背题有用得多。2.3 递归代码怎么列方程递归没法直接数循环次数需要列递推式。做法是把递归调用当作已知代价写出 T(n) 和 T(更小规模) 的关系。二分查找的递归版本是个经典def bsearch(a, lo, hi, target): if lo hi: return -1 mid (lo hi) // 2 if a[mid] target: return mid if a[mid] target: return bsearch(a, mid 1, hi, target) return bsearch(a, lo, mid - 1, target)每次只走一边规模从 n 变成 n/2前面的比较和取中间值花常数时间 c于是 T(n) T(n/2) c基准情况 T(1) 1。展开T(n) c T(n/2) 2c T(n/4) ... c·log₂n T(1)。所以 T(n) Θ(log n)。再看归并排序def merge_sort(a): if len(a) 1: return a mid len(a) // 2 left merge_sort(a[:mid]) right merge_sort(a[mid:]) return merge(left, right)两路递归每路规模减半合并这一步要线性扫一遍两个子数组代价 cn。于是 T(n) 2T(n/2) cn。展开一层是 2T(n/2) cn两层是 4T(n/4) 2cn第 k 层是 2^k·T(n/2^k) k·cn。当 n/2^k 1 也就是 k log₂n 时触底总代价是 n·T(1) cn·log₂n即 Θ(n log n)。我把这两类递归的对比列一下方便记递归形态递推式结果典型算法单路折半T(n) T(n/2) cΘ(log n)二分查找、快速幂双路折半 线性合并T(n) 2T(n/2) cnΘ(n log n)归并排序、快排平均双路折半 常数T(n) 2T(n/2) cΘ(n)二叉树遍历单路减一 线性T(n) T(n-1) cnΘ(n²)冒泡、插入排序最坏双路减一T(n) T(n-1) T(n-2) cΘ(2ⁿ)朴素斐波那契递归注意递归的时间复杂度和空间复杂度要分开算。时间看调用次数空间看递归栈的最大深度。二分查找时间 O(log n)空间也是 O(log n)归并排序时间 O(n log n)空间 O(n)额外数组加 O(log n)栈深。很多人只算时间忘了空间在内存吃紧的嵌入式环境里会吃亏。3. 从 T(n) 化简到 O(n) 的完整推导3.1 渐进上界的形式定义与 c、n₀ 的取法前面给了定义这里再说一遍并强调它怎么用T(n) O(g(n)) 当且仅当存在正常数 c 和 n₀使得对一切 n ≥ n₀ 都有 0 ≤ T(n) ≤ c·g(n)。证明某个函数是 O(g(n))本质是在做一道不等式题找到一组 (c, n₀)。实操套路是把 T(n) 往 g(n) 上靠凑出一个常数倍。举三个例子练手。例一T(n) 3n² 20n 5证明它是 O(n²)。当 n ≥ 1 时20n ≤ 20n²5 ≤ 5n²所以 T(n) ≤ 3n² 20n² 5n² 28n²。取 c 28、n₀ 1 即可。例二T(n) 2ⁿ n¹⁰⁰证明它是 O(2ⁿ)。当 n ≥ 1000 左右时n¹⁰⁰ 会被 2ⁿ 远超取 c 2、n₀ 取一个足够大的值比如 3000就能成立。考试里常要求给出具体 n₀一般用对数估算或者直接给一个宽松的整数就行。例三T(n) log₂n 5证明 O(log n)。取 c 6、n₀ 2n ≥ 2 时 log₂n ≥ 1所以 log₂n 5 ≤ 6log₂n。成立。你会发现这里的 c 和 n₀ 完全不需要最优只要存在就行。这是渐进分析最宽容的地方也是它最实用的地方——你不必精确知道机器跑一条指令要几纳秒就能比较两个算法的优劣。3.2 化简四步法任何人拿到 T(n) 都能推我总结了一套四步化简流程用熟了基本是条件反射展开把循环、递归全部展开成关于 n 的和式或递推式。忽略低阶项只留增长最快的那一项。n² n log n 留 n²n log n n 留 n log n。去掉常数系数3n² 变成 n²0.001n 变成 n。系数只在同阶比较时才有意义。归一化为标准记号写成一个常见的复杂度表达式。拿一个稍复杂的例子走一遍。假设某段代码的代价是 T(n) n²/2 100n log₂n 5000。第一步已经展开了。第二步比较 n²/2 和 100n log₂n当 n 200 log₂n 时前者更大n 从 2000 左右开始就满足了所以保留 n² 项。第三步扔掉 1/2。第四步得到 O(n²)。注意 log 的底数渐进分析里对数底数全部可以忽略因为 log_a n log_b n / log_b a换底只是多了个常数因子。所以 O(log₂n)、O(log₁₀n)、O(ln n) 在渐进意义上是一回事统一写 O(log n)。这一点在工程里意义很大——你用什么底数都不影响量级判断别在这上面较真。3.3 主定理速查与它的适用边界主定理Master Theorem是处理分治递归式最省事的工具。对于形如 T(n) aT(n/b) f(n) 的递推式a ≥ 1b 1令临界函数为 n^(log_b a)然后比大小情况条件结论情况一f(n) 比 n^(log_b a) 小一个多项式量级即 f(n) O(n^(log_b a − ε))ε 0T(n) Θ(n^(log_b a))情况二f(n) 与 n^(log_b a) 同阶即 f(n) Θ(n^(log_b a) log^k n)k ≥ 0T(n) Θ(n^(log_b a) log^(k1) n)情况三f(n) 比 n^(log_b a) 大一个多项式量级且满足正则条件 a·f(n/b) ≤ c·f(n)c 1T(n) Θ(f(n))用归并排序验证a 2b 2n^(log₂2) nf(n) cn Θ(n)属于情况二且 k 0结论 Θ(n log n)。和手工展开的结果一致。用二分查找验证a 1b 2n^(log₂1) n⁰ 1f(n) c Θ(1)属于情况二且 k 0结论 Θ(log n)。也对。再看一个情况三的例子T(n) 2T(n/2) n²。n^(log₂2) nf(n) n² 比 n 大一个多项式量级检查正则条件2·(n/2)² n²/2 ≤ c·n²取 c 1/2 成立所以 T(n) Θ(n²)。注意主定理的边界三种情况之间有缝隙。比如 f(n) n log n 配 n^(log_b a) n属于情况二但如果 f(n) n·log n 而临界函数是 n²那就三种情况都不满足差距不是多项式级别的主定理失效得用 Akra–Bazzi 或者直接递归树硬算。另外 a 或 b 不是常数、或者递推式形状不是 aT(n/b) f(n) 的主定理也不管用。我见过太多人拿它硬套导致结论错误的案例套之前先看清楚形状。3.4 常见量级增长对照表与排序把常见复杂度按增速排个队这是做技术选型时最有用的直觉来源复杂度n10n100n1000n10⁶典型场景O(1)1111哈希表查询、数组下标访问O(log n)3.36.61020二分查找、平衡树操作O(√n)3.210321000试除法判素数、分块算法O(n)10100100010⁶线性扫描、前缀和O(n log n)3366410⁴2×10⁷归并排序、堆排序O(n²)10010⁴10⁶10¹²冒泡、插入、朴素两两比较O(n³)100010⁶10⁹10¹⁸朴素矩阵乘法O(2ⁿ)10241.3×10³⁰天文数字天文数字子集枚举O(n!)3.6×10⁶天文数字天文数字天文数字全排列枚举拿这张表算笔账假设机器每秒能做 10⁸ 次基本操作n 10⁶ 时O(n log n) 要 0.2 秒能接受O(n²) 要 10⁴ 秒接近三小时直接判死刑。这就是为什么在处理百万级数据的时候你必须把 O(n²) 的写法改成 O(n log n) 或者 O(n)否则不是慢一点是根本跑不完。还有个小技巧知道 log₂10⁶ ≈ 20 这个数很有用很多地方要心算。因为 2¹⁰ 1024 ≈ 10³所以 2²⁰ ≈ 10⁶。同理 2³⁰ ≈ 10⁹。这种估算在做容量规划的时候特别顺手。4. 两个堆求中位数一次完整的复杂度分析实战4.1 为什么要在两个堆上做文章数据流中位数是个非常经典的题数据一个一个来随时要能回答当前所有数的中位数是多少。朴素做法是每次来新数都插进数组然后排序插入 O(1) 但每次查询要 O(n log n)如果查询频繁就很亏。另一种是插的时候保持有序比如插入排序的思路插入 O(n)查询 O(1)。两种都不理想。于是有了这个常被称作两个堆的方案**用一个最大堆存较小的一半数用一个最小堆存较大的一半数两边数量差不超过 1。**这样最大堆的堆顶就是较小那半里最大的最小堆的堆顶是较大那半里最小的中位数只可能从这两个堆顶产生。这个设计的精妙之处在于它把一个全局有序的需求拆成了局部有序——你不需要知道所有数字的完整顺序只需要知道中间那道分界线两侧最靠近的两个数。堆结构恰好能在这个弱化了的约束下给出更低的维护代价。4.2 插入操作 O(log n) 的逐行分析与代码先把实现写出来import heapq class MedianFinder: def __init__(self): self.small [] # 最大堆用负数模拟存较小的一半 self.large [] # 最小堆存较大的一半 def add(self, num): # 第一步决定进哪个堆 if not self.small or num -self.small[0]: heapq.heappush(self.small, -num) else: heapq.heappush(self.large, num) # 第二步恢复平衡保证 len(small) - len(large) 属于 {0, 1} if len(self.small) len(self.large) 1: heapq.heappush(self.large, -heapq.heappop(self.small)) elif len(self.large) len(self.small): heapq.heappush(self.small, -heapq.heappop(self.large)) def median(self): if len(self.small) len(self.large): return (-self.small[0] self.large[0]) / 2 return float(-self.small[0])逐行数代价。第一步只有常数次比较和一次 heappush。第二步最多执行一次堆之间的搬运每次搬运是一次 pop 加一次 push。堆的 push 和 pop 都是 O(log n)因为要沿着树高向上或向下调整而完全二叉树的高度是 ⌊log₂n⌋。所以第一步O(log n)第二步最多 2 次堆操作仍是 O(log n)合计 T(n) O(log n) O(log n) O(log n)查询中位数更简单只看两个堆顶O(1)。空间上所有元素各存一份总空间 O(n)。这里有个细节值得说一说为什么插入是 O(log n) 而不是 O(n)。关键在于这个方案从来不搬动整个数组只做堆内的一条路径调整。堆调整的路径长度就是树高 log n而不是元素个数 n。这是数据结构设计带来的红利——同样是维护顺序用数组插入要挪一堆元素用堆只要在一条路径上交换。顺便对比一下三种方案的复杂度方案插入查询中位数空间说明无脑追加 每次排序O(1)O(n log n)O(n)查询贵适合查询极少有序数组 二分插入O(n)O(1)O(n)插入贵适合数据量小两个堆O(log n)O(1)O(n)综合最优工程首选这张表本身就说明了复杂度分析的价值没有哪一行是绝对最优的选哪个取决于你的读写比例。查询多就往后两行选插入多就用第一行。脱离使用场景谈复杂度最优是新手最容易犯的错。4.3 摊还分析与常见误判动态数组的 push说到平均代价就得提摊还分析。很多人把摊还和平均混为一谈其实完全是两码事。以动态数组Python 的 list、C 的 vector的 append 为例。大多数时候append 就是把元素放到末尾的空位O(1)。但偶尔数组满了需要申请一块更大的内存、把旧元素全部搬过去这一次的操作是 O(n)。于是有人会说append 最坏 O(n)没错但如果说append 平均 O(n)那就大错特错了。正确的分析是这样的假设容量从 1 开始每次满了就翻倍。那么在第 1、2、4、8、...、2^k 次插入时会触发扩容搬移的元素个数分别是 1、2、4、...、2^k。n 次 append 总的搬移量是 1 2 4 ... 2^k 2n其中 2^k ≤ n。再加上 n 次放入元素本身总代价小于 3n均摊到每次插入就是 O(1)。这就是摊还分析它给的是一个确定性结论——任意长度为 n 的操作序列总代价不超过 O(n)而不是对输入分布的期望。而平均情况分析则是假设输入服从某种分布求期望代价。前者是坏账被前面的好账平摊了后者是平均来看会怎样。面试里被问动态数组 append 的复杂度标准答案是单次最坏 O(n)n 次连续操作的摊还代价 O(1)。同样的思路可以用来分析并查集的路径压缩摊还 O(α(n))α 是反阿克曼函数增长极慢、单调栈、哈希表的扩容等等。掌握摊还这个概念你对复杂度的理解就从单个操作升维到操作序列了。5. 实测验证复杂度到底怎么量出来5.1 计时脚本怎么写才靠谱理论上推完了怎么验证最直接的办法是跑一遍测时间。但计时这件事坑特别多我先给一个我常用的模板import time import statistics def bench(fn, *args, repeat7, warmup2): # 预热让解释器、缓存进入稳定状态 for _ in range(warmup): fn(*args) samples [] for _ in range(repeat): t0 time.perf_counter() fn(*args) samples.append(time.perf_counter() - t0) # 取最小值而不是平均值 return min(samples), statistics.median(samples)几个要点必须强调用 perf_counter 而不是 time.time。前者是单调时钟精度到纳秒级不会被系统时间调整影响后者分辨率低还可能因为校时而跳变。一定要预热。Python 这类语言有字节码缓存、类型反馈优化JIT 类的运行时更明显。第一次跑和第十次跑的耗时可能差好几倍不预热的话测出来的全是噪声。取多次的最小值不要取平均。因为干扰GC、操作系统调度、其他进程只会让耗时变长不会让它变短。最小值最接近算法的真实代价平均值反而被噪声污染。当然如果你关心的是用户感知的 P99 延迟那就得看分布而不是最小值这属于另一个话题。留出足够的规模梯度。只测一个 n 是看不出趋势的至少测四到五个数量级比如 n 取 1000、2000、4000、8000、16000然后看耗时怎么涨。5.2 用增长曲线反推复杂度拿到数据之后怎么判断是哪一档我的方法是算倍率每次把 n 翻倍看耗时涨了多少倍。n 翻倍时耗时倍率推断复杂度约 1 倍O(1) 或极度不敏感增加一个常量如 1O(log n)约 2 倍O(n)约 2.2~2.5 倍2·log 的贡献O(n log n)约 4 倍O(n²)约 8 倍O(n³)远超 8 倍、迅速爆炸指数级再举个实际经验如果 n 从 1000 到 2000耗时从 1 毫秒涨到 2.2 毫秒那就是典型的 O(n log n)因为 log₂(2000)/log₂(1000) ≈ 11/10 1.12 × 1.1 2.2。这个 2.2 的倍率我实测过很多次比想象的准。注意小规模数据上的实测结论非常不可靠。n 10 的时候一个 O(n²) 的算法完全可能比 O(n log n) 的跑得快因为前者的常数系数小得多。只有在 n 足够大、常数项被淹没之后渐进分析才和实测对上。这也是渐进分析的适用边界——它是为大 n 准备的。6. 常见问题与避坑心得6.1 问题速查表现象可能原因排查方向推出来的结果和实测对不上n 太小常数项主导把 n 放大 10 倍再测同一个算法两次测得差异很大没预热、GC 抖动、有并发干扰预热 取最小值 隔离环境内层循环次数估错循环变量不是线性增长检查 i 2、i k、i ii 这类写法递归复杂度算错只算了单路的规模缩减数清递归了几个分支空间复杂度漏算忘了递归栈和临时数组时间空间分开列逐个来源核对摊还分析当成了平均分析概念混淆摊还看最坏操作序列平均看输入分布主定理套不上三个情况之间有缝隙换递归树展开或者 Akra–Bazzi说排序是 O(n)概念偷换比较排序下界是 Ω(n log n)除非计数排序这类非比较排序计数排序那一条值得展开说它不是比较排序靠的是键值范围有限这个前提复杂度 O(n k)k 是取值范围。当 k 远大于 n 的时候它反而不如 O(n log n) 的比较排序。所以看到O(n) 的排序先别激动问清楚前提条件。6.2 几条踩出来的经验第一条内置函数永远比手写快哪怕渐进复杂度一样。Python 的sorted()是 TimsortC 实现、经过高度优化你自己手写个快排同样 O(n log n)实测可能慢十倍。同样的sum()、min()、max()都是 C 层面的循环比 Python 的 for 循环快一个数量级。渐进复杂度一样不代表性能一样常数因子在工程里经常比量级还重要——只有当 n 大到让量级差距超过常数差距时量级才说了算。第二条警惕那些藏在函数调用里的 O(n)。我在 code review 里见过太多次这类问题。比如在一个循环里反复调用len(lst)在 Python 里这是 O(1) 还好但在某些语言里String.length()可能要遍历一遍那就把 O(n) 的循环变成了 O(n²)。再比如list.insert(0, x)和list.pop(0)在 Python 里都是 O(n)因为它要挪动后面所有元素正确做法是用collections.deque的appendleft和popleft那是 O(1)。还有字符串在循环里做s x某些实现下每次都重新分配内存整体退化成 O(n²)应该先收集到列表再.join()。第三条字典和集合的 O(1) 是有前提的。哈希表的平均查找是 O(1)但最坏情况是 O(n)——所有键都冲突到同一个桶里。正常情况下哈希函数足够好你不用担心但如果你的键是精心构造的对抗性输入就可能被打到最坏。安全领域里针对哈希碰撞的拒绝服务攻击就是利用这一点。写业务代码时不用过度担心但心里要有个数O(1) 说的是期望值不是保证值。第四条最好把数据规模上限当成设计的第一约束。拿到需求先问一句数据量级大概多少。如果 n 不超过 1000你写个 O(n²) 的清晰代码完全没问题别为了炫技搞一堆复杂数据结构可读性反而更差。但如果 n 是百万级、还要高频调用那就必须认真推复杂度。我见过为了性能把一段 n50 的代码优化得面目全非的纯属自找麻烦。复杂度分析是决策工具不是炫技工具。第五条推不出来的时候先画递归树或者列个表格。递归树把每一层的代价写清楚层数就是树高总代价就是各层相加很多时候画着画着答案就出来了比硬套公式靠谱。我处理那些形状奇怪的递推式时基本都是先画三层看看规律。最后分享一个我自己一直在用的练习方法随便找一段自己写过的业务代码从最外层函数开始逐行标注复杂度然后在旁边写上这段能不能降到更低。坚持一段时间之后你写代码的时候会下意识地避开那些会退化成 O(n²) 的写法这种直觉比背多少公式都管用。