1. 一段“看起来一样快”的代码为什么换了数据量就趴下线上有个接口本地拿 1000 条测试数据跑20 毫秒出结果加个日志、写个单测一切正常。上线之后真实数据涨到 10 万条同一个接口的耗时变成了 40 分钟。注意这个倍数数据量翻 100 倍耗时翻了 12 万倍。如果你只看本地测试的结论会觉得这代码“没问题”如果你懂时间复杂度和渐进时间复杂度会在一开始就知道这段代码迟早要炸。T(n) 和 O(n) 这一对概念真正的价值不在于面试时能报出几个符号而在于它能让你在写代码的那一刻对“数据量涨上去会怎样”有一个提前的预判。很多人学这块的时候卡在同一个地方书上先讲 T(n)再讲 O(n)两个东西都带个 n看着像双胞胎到底谁是谁、为什么需要两个没人说清楚。我当年也是背了一堆“O(1)、O(log n)、O(n)、O(n log n)、O(n²)”的排序表做题能对但真到了项目里看到一个嵌套循环套着一个列表推导还是判断不出真实开销。后来想明白了T(n) 和 O(n) 分工完全不同一个是“算账”一个是“看趋势”。算账要精确看趋势要模糊。把这两个心态分清楚后面的一切都顺了。这篇内容适合三类人正在准备技术面试、需要把复杂度分析讲明白的人写了几年业务代码、但从来没系统推过一次复杂度的人以及那些被线上性能问题教育过、想搞明白“为什么慢”的人。下面我会从怎么把代码写成 T(n) 这个函数开始一路推到 O(n) 的严格定义、循环和递归的拆解套路、两个堆求中位数这种经典场景的完整复杂度推导最后落到排序算法的全景对比和几个我踩过的坑。所有推导我都会把中间过程写出来你不需要数学很好只需要会数数。1.1 先把最容易混淆的一句话钉死T(n) 是运行时间函数输入规模为 n 时这段代码大概要执行多少条基本操作或者准确地说需要多少时间单位。它是一个具体的表达式比如 T(n) 3n² 5n 7带系数、带低阶项甚至可以带常数 7因为常数项代表了那段跟 n 无关的固定开销。O(n) 是渐进上界它描述的是当 n 趋向无穷大时T(n) 的增长量级被什么东西“罩住”了。3n² 5n 7 的渐进复杂度是 O(n²)因为 n 大了以后n² 这一项说了算。关键区别在这T(n) 关心“现在这段代码具体要花多少”O(n) 关心“数据量涨十倍开销大概涨几倍”。前者是工程上的精确核算后者是架构上的趋势判断。做性能优化两个都要用先用 O(n) 判断这个模块能不能扛住未来的量如果结论是“不能”再用 T(n) 去抠常数、抠那一层循环把实际耗时压下来。1.2 一个反直觉的实测O(n) 更差的算法跑得反而更快这是最容易被忽略的一点我用一个真实经历说明。早期写一个字符串匹配的小工具输入是几万条短文本我一开始用了一个 O(n²) 的朴素双重循环实测 3000 条数据 8 毫秒。后来为了“优化”换成了一个理论上 O(n) 的复杂哈希方案结果同样的数据跑了 45 毫秒。原因很朴素O(n²) 那段的实际操作是数组下标比较两个机器指令O(n) 那个方案每次都要算哈希、处理冲突、访问散列桶单次操作的成本高了二三十倍。在 n 只有几千的时候n² 才几百万次廉价操作而“O(n)”方案是几千次昂贵操作乘以一个巨大的常数。渐进复杂度只在 n 足够大的时候才统治一切。所以你在做技术选型时如果数据规模有明确上界比如“配置表最多 50 条”直接测别迷信大 O如果没有上界老老实实按 O(n) 选。2. T(n) 到底怎么算把代码翻译成一个函数T(n) 的构造过程其实非常机械就是一个“数操作”的过程。你只需要做三件事找到输入规模 n 指的是什么、数出代码执行了多少次基本操作、把这些次数写成 n 的表达式。基本操作的定义很宽松一次赋值、一次比较、一次算术运算、一次数组访问都可以算作一次。选择哪个作为“基本单位”不影响最终结论只要保持一致就行。2.1 从最简单的顺序代码开始看这段代码def add_one(nums): total 0 # 1 次赋值 for x in nums: # 循环 n 次 total x # 每次 1 次加法 1 次赋值 return total # 1 次返回输入规模 n len(nums)。逐行数第 1 行执行 1 次循环变量迭代 n 次每次判断一次是否结束、取一次元素保守算 2 次共 2n循环体里加法加赋值算 2 次共 2n最后 return 1 次。于是T(n) 1 2n 2n 1 4n 2你可能会说循环判断的次数其实是 n1 次最后一次判断失败退出那应该是 3n3 之类的。完全没问题因为这些差异最后都会被 O(n) 吞掉。T(n) 允许你不精确只要量级对、系数别差一个数量级就是一个可用的 T(n)。2.2 嵌套循环乘法关系是怎么来的def count_pairs(nums): cnt 0 for i in range(len(nums)): # 外层 n 次 for j in range(len(nums)): # 内层每次都跑 n 次 if nums[i] nums[j]: cnt 1 return cnt外层每执行一次内层完整跑一遍 n 次所以内层循环体的总执行次数是 n × n。T(n) c₁n² c₂n c₃其中 c₁n² 来自内层比较和自增。这里有一个判断技巧嵌套循环看乘法并列循环看加法。两个 for 是嵌套关系就是乘两个 for 是先后关系就是加。这个规则能覆盖 80% 的业务代码。2.3 常数系数为什么不能丢一个真实的优化案例假设一个接口的 T(n) 1000n 500另一个方案是 T(n) 3n² 10n。单看 O(n)第一个是 O(n)第二个是 O(n²)闭着眼睛选第一个。但如果你告诉我 n 最大只有 20那第一个是 20500第二个是 1400第二个快 14 倍。常数系数在 n 小的区间里就是决定因素。我在做批量数据清洗的时候遇到过一模一样的情况。一个 O(n²) 的两两比较去重n 是每条记录的字段数通常不超过 15而我一开始为了“性能”引入了一个基于哈希表的方案每次要构造元组、算哈希、比对冲突。实测下来字段数 15 以内时双重循环版本稳定快 2 到 3 倍。后来我把阈值写成常量字段数 ≤ 20 走双重循环 20 走哈希。这个“混合策略”在工程里非常常见Python 的 Timsort 内部对小数组用插入排序就是这个思路。真正要用 T(n) 做决策的时候别忘了加上那句灵魂拷问n 的真实上界是多少。如果上界很小常数项才是战场如果上界很大或者不可控那就让 O(n) 说话。3. O(n) 的严格定义三句话说清渐进复杂度渐进复杂度的严谨定义很多教材写得像绕口令我用尽量直白的方式重述一遍然后告诉你工程上怎么用。3.1 上界的定义存在两个常数就够了O(g(n)) 的定义是存在正常数 c 和 n₀使得对所有 n ≥ n₀都有 T(n) ≤ c·g(n)。翻译成人话从某个规模开始T(n) 永远被 g(n) 的某个倍数压住。3n² 5n 7 是 O(n²)取 c 4、n₀ 10 就能验证n ≥ 10 时3n² 5n 7 ≤ 4n²因为 4n² - 3n² - 5n - 7 n² - 5n - 7n10 时是 43 0之后单调递增。你也可以取 c 15、n₀ 1同样成立。常数 c 取多少不重要存在就行这就是“渐进”二字的分量。顺便把两个经常一起出现但很少被讲清的符号带上Ω 是下界意思是“至少这么多”Θ 是紧确界上界下界同阶。说“快排的平均复杂度是 Θ(n log n)”比说 O(n log n) 更准确因为 O 只保证不更差Θ 才说明它就是这样。3.2 化简三规则丢系数、丢低阶、只看最高次从 T(n) 推到 O(n)只有三步第一丢掉所有常数系数。4n 2 变成 n3n² 5n 7 里的 3 丢掉变成 n² n。第二丢掉所有低阶项。n² n 只留 n²因为 n 趋向无穷时 n 的影响可以忽略。你可以验证n 1000 时n² 1,000,000n 1000后者占比 0.1%。第三只保留最高次项写进括号里。结果是 O(n²)。有个小细节值得注意如果 T(n) 里有多个不同底的指数比如 2ⁿ n¹⁰⁰答案是 O(2ⁿ)因为指数增长最终碾压任何多项式。同样地n log n 比 n 高、比 n² 低它不满足任何“只剩一项”的直觉要单独记住。3.3 增长速度对照把抽象函数变成可感知的数字光看符号没有体感把 n 代进去算一遍就清楚了。假设单次基本操作耗时 1 纳秒这是乐观估计实际访问内存大约 100 纳秒量级不同复杂度在不同规模下的耗时大致如下复杂度n 100n 10,000n 1,000,000典型场景O(1)1 ns1 ns1 ns哈希表查找、数组下标O(log n)约 7 ns约 14 ns约 20 ns二分查找、平衡树操作O(n)100 ns10 μs1 ms一次遍历、求和O(n log n)约 700 ns约 140 μs约 20 ms归并排序、堆排序O(n²)10 μs100 ms约 11.6 天双重循环、朴素去重O(2ⁿ)天文数字天文数字天文数字暴力枚举子集最后一行不用算n 60 的时候 2⁶⁰ 就已经超过 10¹⁸ 次操作按每秒十亿次计算也要三十多年。我第一次看到这张表时的震撼在于O(n²) 和 O(n log n) 在 n 100 时只差一个数量级在 n 1,000,000 时差了五个数量级。这解释了为什么“本地跑得挺快”的代码上线就崩——你的测试数据量还没到分水岭。提示记忆这张表的时候抓住三条线就够了——log n 约等于“把 n 反复减半需要几次”n log n 约等于“每个元素都要参与 log n 次操作”n² 是“任意两个元素两两碰面”。4. 代码逐段拆解循环、递归、均摊三种套路有了前面的规则接下来是实操。大部分复杂度分析可以归到三类结构循环、递归、均摊。每类有固定的拆解姿势熟练之后看代码几乎能条件反射。4.1 循环变量在跳对数复杂度的来源def halve_count(n): steps 0 while n 1: n n // 2 steps 1 return steps这个循环跑多少次n 每次减半从 n 到 1 需要 log₂n 次所以 T(n) log₂n 1复杂度 O(log n)。换成 n n // 3 呢底数变了但 O(log n) 不变因为换底公式 log₃n log₂n / log₂3差的是一个常数因子被丢掉了。所有“每次把问题规模按固定比例缩小”的代码都是 O(log n)二分查找、平衡树的查找、快速幂都是这个模式。再看一个容易看错的def tricky(n): i 1 total 0 while i n: j 0 while j i: total 1 j 1 i * 2 return total外层 i 按 1, 2, 4, 8... 增长到 n 需要 log n 次。内层跑 i 次累计是 1 2 4 ... n/2这是一个等比数列和小于 2n。所以整体是 O(n)不是 O(n log n)。内层规模随外层变化时要算求和不能简单相乘。这个坑我踩过当时把一段这样的代码标成了 O(n log n)被同事纠正后才养成“看内层上界是否依赖外层变量”的习惯。4.2 递归式的拆解画递归树比背公式管用递归代码的复杂度不能直接数循环得写出递归式。以归并排序为例T(n) 2T(n/2) O(n)含义是把问题分成两个规模为 n/2 的子问题对应 2T(n/2)合并两个有序数组需要 O(n)。拆解方法一递归树第一层合并代价 n第二层两个子问题各 n/2合计仍是 n第三层合计 n……一共 log₂n 层每层 n总代价 O(n log n)。这个方法形象我强烈建议先学它因为主定理Master Theorem用错了很麻烦而递归树很少出错。拆解方法二主定理对于 T(n) aT(n/b) f(n)比较 f(n) 和 n^(log_b a)情况条件结论情况一f(n) 明显小于 n^(log_b a)T(n) Θ(n^(log_b a))情况二f(n) 与 n^(log_b a) 同阶T(n) Θ(n^(log_b a) · log n)情况三f(n) 明显大于 n^(log_b a) 且满足正则条件T(n) Θ(f(n))拿归并排序套一遍a 2b 2n^(log₂2) nf(n) n同阶落入情况二答案是 Θ(n log n)和递归树一致。二分查找是 T(n) T(n/2) O(1)a 1n^(log₂1) n⁰ 1f(n) 1同阶情况二给出 Θ(log n)也对得上。必须提醒一个陷阱主定理只适用于a ≥ 1、b 1、且子问题规模严格按 n/b 缩小的形式。像 T(n) T(n-1) O(n) 这种每次只减一个的主定理不适用得展开成等差数列 n (n-1) ... 1 O(n²)。我看到过有人硬套主定理算出 O(n)结果面试挂掉——判断递归式是不是“分治型”是套公式之前的第一步。4.3 均摊复杂度动态数组扩容为什么还是 O(1)Python 的 list.append 平均复杂度是 O(1)但某些单次调用会明显变慢因为底层数组满了要扩容并整体拷贝。这是不是矛盾不矛盾这就要引入均摊复杂度。假设每次扩容翻倍从容量 1 开始连续 append n 次。拷贝发生的时刻是容量 1、2、4、8……拷贝的总代价是 1 2 4 ... n ≈ 2n。把这 2n 次拷贝操作分摊到 n 次 append 上每次平均 2 次操作所以均摊复杂度是 O(1)。翻倍策略是精髓所在如果每次只扩容固定大小比如每次加 10拷贝总代价会变成 O(n²/10) O(n²)均摊就是 O(n)。这就是为什么几乎所有语言的标准库动态数组都用翻倍而不是线性扩容。这个例子的意义在于复杂度分析的最终目的不是给每一行代码定罪而是给你一个在长周期上成立的期望值。写高并发场景时我更关心 P99 延迟而均摊分析恰好会掩盖掉偶发的长尾——所以扩容那一刻的停顿在设计实时系统时要单独考虑比如预分配容量或者改用分块结构。5. 经典实战用两个堆维护中位数插入 O(log n) 是怎么推出来的数据流的中位数问题特别适合用来练复杂度分析。需求是不断有数字进来随时能查询当前所有数字的中位数数据量可能到几百万。朴素做法是每次查询前排序或者维护一个有序数组每次插入用二分找到位置再搬移元素。下面把三种方案的复杂度全部算清楚你会看到 O(log n) 是怎么被逼出来的。5.1 朴素方案的复杂度账本方案一每次查询都全量排序排序是 O(n log n)如果查询 q 次总共 O(qn log n)。数据量一万、查询一万次就是 10⁸ 量级的操作卡。方案二维护有序数组插入时二分查找位置 O(log n)但插入本身要移动后面所有元素最坏 O(n)。查询时直接取下标 O(1)。所以插入 O(n)、查询 O(1)。整体 n 次插入是 O(n²)。方案三两个堆。插入 O(log n)查询 O(1)。这才是有工程价值的方案。5.2 两个堆的分工大顶堆放小半小顶堆放大半核心思想是把数据劈成两半用一个分界线左右各管一边大顶堆max-heap存较小的一半数据堆顶是这半边的最大值也就是“靠近中位数的左边那个”。小顶堆min-heap存较大的一半数据堆顶是这半边的最小值也就是“靠近中位数的右边那个”。维持两条不变式大顶堆里所有元素 ≤ 小顶堆里所有元素。两个堆的大小差不超过 1且约定大顶堆的大小 ≥ 小顶堆的大小。只要这两条成立中位数就只跟堆顶有关如果两个堆大小相等中位数是两个堆顶的平均值如果大顶堆多一个中位数就是大顶堆的堆顶。查询不需要遍历任何数据O(1) 拿下。5.3 插入流程与 O(log n) 的推导插入一个数 x标准流程分三步import heapq class MedianFinder: def __init__(self): self.small [] # 大顶堆存负值 self.large [] # 小顶堆 def add(self, x): # 第一步先塞进大顶堆 heapq.heappush(self.small, -x) # 第二步把大顶堆的最大值挪到小顶堆保证左右有序 heapq.heappush(self.large, -heapq.heappop(self.small)) # 第三步如果小顶堆反超了挪回来维持大小不变式 if 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] return (-self.small[0] self.large[0]) / 2复杂度怎么算整个插入过程最多执行 3 次堆操作1 次 push、1 次 pop 加 push、可能再来 1 次 pop 加 push每次堆操作是 O(log n)。常数次乘对数结果是 O(log n)。空间上两个堆一共存 n 个数O(n)。这里是全局最值得记住的一句话常数个 O(log n) 操作相加还是 O(log n)。很多人推复杂度时会纠结到底做了 2 次还是 3 次堆操作答案是不用纠结数量的常数倍不会改变量级。注意Python 只有小顶堆模拟大顶堆要存负数。别小看这个细节负号在插入和取值时都要成对出现漏一个取出来就是反的我调试过一个小时才发现。5.4 边界条件与几个容易翻车的地方第一堆大小差的约束方向要固定。上面代码约定大顶堆不小于小顶堆那么中位数在元素个数为奇数时一定在大顶堆顶。如果你允许小顶堆多一个median 函数里判断奇偶的分支就得反过来写反了会返回错误结果且不报错。第二空数据流。如果没有元素两个堆都空直接取堆顶会抛异常。工程代码里要么返回 None要么在调用方保证非空别让它静默崩掉。第三多线程。这个结构不是线程安全的两个堆的读写必须加锁或者用队列把插入操作串行化。加锁之后单次插入从 O(log n) 变成 O(log n) 加上锁开销量级没变但常数会涨高并发下要实测。第四数值类型。如果数据是浮点数两个堆顶取平均值没有精度问题如果是大整数注意 Python 的整数运算不会溢出其他语言要留意。最后对比一下三种方案的实际表现。按 n 100 万、插入和查询各 100 万次估算方案二的大规模搬移约 10¹² 次内存操作基本不可接受方案三的堆操作约 100 万 × 20 × 3 6 × 10⁷ 次加上每次的堆调整常数秒级能跑完。这就是渐进复杂度从 O(n) 降到 O(log n) 带来的实际差别量级上的降维打击。6. 排序算法的复杂度全景为什么工程上不总选最快的那个排序是复杂度分析最好的练习场因为同一个问题有五六种解法复杂度各不相同而且工程选型时的取舍逻辑特别典型。6.1 主流排序算法对照表算法平均最坏最好空间稳定性特点冒泡排序O(n²)O(n²)O(n)O(1)稳定教学用实际基本不用插入排序O(n²)O(n²)O(n)O(1)稳定小数组快常做混合排序的底座选择排序O(n²)O(n²)O(n²)O(1)不稳定交换次数少但比较次数恒定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定可外部排序链表排序首选快速排序O(n log n)O(n²)O(n log n)O(log n)不稳定常量小缓存友好实际最快堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定最坏有保证但跳访存不友好计数排序O(n k)O(n k)O(n k)O(k)稳定只适合小范围整数k 是取值范围基数排序O(d(n k))O(d(n k))O(d(n k))O(n k)稳定d 是位数适合定长整数或字符串桶排序O(n k)O(n²)O(n)O(n k)稳定数据分布均匀时接近线性6.2 比较排序的下界为什么 O(n log n) 是天花板你可能会想有没有 O(n) 的通用排序没有。用决策树可以证明这一点n 个元素共有 n! 种排列排序算法必须能区分所有情况对应的决策树至少有 n! 个叶子节点。一棵二叉树高度为 h 时最多有 2ʰ 个叶子所以 2ʰ ≥ n!取对数得到 h ≥ log₂(n!) 。用斯特林近似log₂(n!) ≈ n log₂n - 1.44n也就是 Θ(n log n)。任何基于两两比较的排序最坏情况都不可能低于这个量级。这解释了两件事第一为什么快排、归并、堆排序的平均复杂度都停在 O(n log n)它们已经摸到理论天花板再挤只能挤常数第二为什么计数排序能突破到 O(n k)——因为它不比较而是直接利用数值本身作为下标绕过了决策树的前提。6.3 快排最坏 O(n²)为什么标准库还是用它这是个高频疑问。快排最坏情况确实是 O(n²)发生在每次选的基准都是当前区间的最值时比如对已经有序的数组用固定取首元素的策略。但标准库的实现做了两件事规避它随机化选基准或者三数取中以及小区间切换插入排序。随机化之后出现最坏情况的概率极低而且平均复杂度稳定在 O(n log n)常数因子还特别小。对比堆排序堆排序最坏也是 O(n log n)听起来更稳妥但实际跑起来通常比快排慢 2 到 3 倍原因是堆的操作在内存里是“跳着访问”的缓存命中率差。而快排是顺序扫描和 CPU 缓存、分支预测配合得很好。渐进复杂度相同的两个算法实际的 T(n) 常数可以差好几倍这就是为什么大厂面试问你复杂度而工程上还得看基准测试。顺带说一句稳定性。业务里排序对象经常是结构体要求“按分数排序分数相同的保持原顺序”那就必须用稳定排序。快排和堆排序不稳定归并和插入稳定。Python 的 sorted 用的是 Timsort实际是归并加插入的混合体稳定且对部分有序数据接近 O(n)这也是它比纯快排更适合业务代码的原因。7. 空间复杂度、递归栈和那些让人栽跟头的分析误区复杂度分析做多了你会发现错误很少出在数学上基本都是“假设没想清楚”。下面这几条是我和身边人真实踩过的。7.1 递归函数的空间复杂度必须算调用栈写递归的时候很多人只算函数里声明的变量忘了每一层递归都会在栈上占一份空间。二分查找的递归版本空间复杂度不是 O(1)而是 O(log n)因为有 log n 层调用同时存在。快速排序的递归实现虽然原地交换不额外申请数组但递归栈深度在平均情况下是 O(log n)最坏是 O(n)。所以“原地快排空间 O(1)”这个说法是不严谨的。反过来递归改成循环通常能把空间降下来。我把一个深度可能上万层的树遍历从递归改成显式栈之后不仅空间可控还避免了某些语言栈溢出导致进程直接挂掉的风险。空间复杂度的实战意义往往比时间复杂度更直接因为它决定了你的服务会不会崩。7.2 平均、最坏、均摊三个词对应三种承诺这三个词经常被混用但语义完全不同最坏复杂度对任何输入都成立的上界。适合实时系统、对延迟敏感的场景。平均复杂度假设输入按某种分布随机。快排的 O(n log n) 属于这一类前提是基准随机。均摊复杂度一系列操作的总代价除以操作次数。适合长期运行的累积场景。我见过最典型的误用是拿哈希表的“平均 O(1)”去支撑一个对抗性输入的场景。如果攻击者能构造大量冲突的键哈希表会退化成链表查询变成 O(n)。所以线上服务如果用哈希结构处理用户可控的输入要么用随机化的哈希种子要么准备好在冲突时的退化路径。7.3 实测验证让纸上推导落地推导完了最好用实测对齐一次方法很简单把规模翻倍看耗时涨多少倍。耗时基本不变O(1)耗时增加约 1 个单位O(log n)耗时翻倍O(n)耗时增加略多于 2 倍比如 2.2 倍O(n log n)耗时涨 4 倍O(n²。我做过一个调试技巧给函数加个计数器统计基本操作执行了多少次直接把计数值和理论公式比对。这个手段在排查“复杂度分析对了但实际很慢”的问题时特别有效——如果计数值符合 O(n log n)但墙钟时间远超预期那问题就在常数上可能是内存分配、缓存不友好或者某个隐藏的昂贵操作比如字符串拼接、隐式的列表拷贝。8. 几个高频问题的快速对照把平时被问得最多的几个问题整理成对照表遇到卡壳的时候可以直接查。疑问结论说明for 循环里面有个 in 判断算 O(n) 还是 O(n²)看 in 的实现列表的 in 是 O(n)整体 O(n²)集合的 in 是 O(1)整体 O(n)字符串拼接为什么这么慢每次拼接都新建对象循环里 是 O(n²)改用列表收集再 join 变 O(n)字典取值是不是 O(1)平均是最坏 O(n)哈希冲突严重时退化递归和迭代复杂度一样吗时间通常一样空间不同递归多了调用栈开销两个嵌套循环一定是 O(n²) 吗不一定如果内层上界是常数或上界随外层变化且求和后收敛结果可能更低复杂度相同的算法怎么选看常数、缓存行为和实测例如快排 vs 堆排关于字符串拼接这条我印象很深。早年写日志拼接循环里用s line处理十万行数据花了十几秒。改成parts.append(line)最后.join(parts)之后降到 0.2 秒以内。代码逻辑一行没改复杂度从 O(n²) 变成 O(n)这就是分析能力直接换成性能的地方。再补一个很多人忽略的点Python 里 list 的 insert(0, x) 是 O(n)因为它要把后面所有元素往后挪。如果需要频繁在头部插入用 collections.deque它的 appendleft 是 O(1)。这类 API 的复杂度差异不会在代码里写出来但会实实在在地影响你的程序。我的习惯是用到一个不熟悉的方法时先去文档确认它的复杂度尤其是那些看起来“应该很快”的操作。回到最开始那个 20 毫秒变 40 分钟的例子事后复盘罪魁祸首是一个嵌套循环里对列表做了 in 判断输入规模从 1000 涨到 10 万正好撞在 O(n²) 的墙上。改法很简单把那个列表换成集合T(n) 从 c₁n² c₂n 直接掉到 c₃n耗时回到几十毫秒。整个过程最有价值的部分不是修复本身而是养成一个习惯写完一段带循环的代码先问自己两句话——输入规模 n 是什么这段代码对 n 是几次方。这两句话问下去大部分性能事故都能在提交代码之前拦下来。至于那些边界情况、常数陷阱和均摊假设都是在实际项目里被咬过几次之后才慢慢长出来的直觉光看公式是长不出来的。