时间复杂度手推指南：从T(n)到O(log n)与双堆中位数

很多人第一次接触复杂度分析，都是在刷题或者准备面试的时候。看到题解上写着"本解法时间复杂度 O(n log n)，空间 O(log n)"，心里大概知道这是"衡量快慢"的东西，但真要自己推一遍，往往就卡在"这个 O 是怎么算出来的"上。更麻烦的是，网上很多讲复杂度的内容一上来就是极限符号、渐进上界、大 O 定义，看完还是不知道怎么下手算。我打算换个路子，从最朴素的 T(n) 出发，把"数操作次数"这件事一步步做完，再告诉你怎么把它化简成 O(n)，最后用两个堆求中位数这个经典案例，把 O(log n) 从头算到尾。读完你应该能做到两件事：拿到一段代码能自己推复杂度，遇到别人给的复杂度结论能判断它靠不靠谱。无论你是刚学数据结构的学生，还是写了几年业务代码、想回头补一补基础的老手，这篇都能对得上。

1. 先搞清楚 T(n) 和 O(n) 到底在讨论什么

1.1 从"跑一遍计时"到"数操作次数"

最直观衡量代码快慢的办法是什么？跑一遍，掐表。我最早干过这事，写了个循环跑一百万次，用time.time()前后一减，得出"耗时 0.38 秒"。问题是这个数字第二天就变了：换了台机器，从 0.38 秒变成 0.12 秒；数据量从一百万变成五百万，又变成 2.1 秒。你拿这个数字去跟同事说"我这个算法比较快"，对方第一反应是"你那台机器什么配置"。

所以计时这条路走不通，不是因为不准，而是因为它把算法本身和运行环境混在一起了。我们需要一个只跟算法结构有关、跟机器无关的度量。答案就是数"操作次数"：不管你用什么语言、什么 CPU，冒泡排序在数据量翻倍的时候，比较次数会变成原来的四倍——这个倍数关系是算法自带的属性，不会因为换了台电脑就改变。

T(n) 就是这个思路的产物。它表示当输入规模为 n 时，算法需要执行的基本操作次数。这里的"基本操作"是个约定俗成的概念，通常指一次比较、一次赋值、一次算术运算、一次数组下标访问这类常数时间内完成的操作。你不用纠结常数级别里的细微差别，因为后面的化简会把它们全部抹掉。

1.2 T(n) 是精确账本，O(n) 是趋势地图

打个比方。T(n) 像一本流水账，记录每一笔开销：这个循环跑了 n 次，里面又跑了 n 次，主函数里还有三行赋值。这本账很实在，但实在过头了——一个双层循环可能是 3n² + 5n + 7，另一个是 0.5n² + 100n，谁快谁慢？光看表达式，你没法一眼判断。

O(n) 则是一张趋势地图。它不关心具体数字，只关心"当 n 变大时，开销按什么形状增长"。上面那两个表达式都记为 O(n²)，因为主导增长的都是 n² 那一项。地图把细节抹掉了，但也正是这种"抹掉"让不同算法之间可以横向比较。

1.3 为什么工程上更认可 O(n)

有人会问，精确账本不是更有用吗？工程上的答案是：常数系数不可控，增长阶数才可控。你的代码编译成什么指令、缓存命中率多少、分支预测对不对，这些都会影响那个常数系数，但它们不在你的掌控范围内，而且换台机器、换个编译器就全变了。而增长阶数是算法层面的性质，你选了什么策略、用了什么数据结构，直接决定它。

注意：O(n) 只描述增长趋势，不代表"n 很小时它一定快"。一个 O(n log n) 的算法在 n=10 的时候，完全可能输给 O(n²) 的暴力解法，因为后者的常数系数可能小得多。工程里小数据量用暴力、大数据量才上高级算法，是很常见的做法。

2. 渐进记号的家族：O、Ω、Θ、o 一次讲透

2.1 三分钟看懂 O(n) 的数学定义

正式定义是这样的：f(n) = O(g(n))，当且仅当存在两个正常数 c 和 n₀，使得对所有 n ≥ n₀，都有 0 ≤ f(n) ≤ c·g(n)。这句话翻译成人话就是：从某个规模开始，f(n) 永远被 g(n) 的某个常数倍压在下面。

我举个具体例子。假设 f(n) = 3n + 5，要证明 f(n) = O(n)。取 c = 4，n₀ = 5：当 n ≥ 5 时，3n + 5 ≤ 3n + n = 4n，成立。所以 3n + 5 = O(n)。那能不能说它是 O(n²) 呢？也能，因为取 c = 1、n₀ = 1，3n + 5 ≤ n² 对 n ≥ 4 都成立。这就引出一个关键认知：O 给出的上界不唯一，写 O(n) 是最紧的那个，写 O(n²) 也没错但不精确。面试场上如果答成 O(n²)，面试官大概率会追问一句"还能更紧吗"。

2.2 上界、下界、紧确界各管什么

很多人只知道 O，其实同族还有几个兄弟，分工挺清楚的。

• Ω（大 Omega）：渐进下界。f(n) = Ω(g(n)) 表示从某个规模起，f(n) 永远被 g(n) 的某个常数倍托住。它回答"至少要花这么多"。
• Θ（大 Theta）：渐进紧确界。f(n) = Θ(g(n)) 同时满足上界和下界，即存在 c₁、c₂、n₀，使得 c₁·g(n) ≤ f(n) ≤ c₂·g(n)。它回答"就是这么多"。
• o（小 o）：严格上界，类似于小于号相对于小于等于号。f(n) = o(g(n)) 意味着 f(n)/g(n) 当 n 趋于无穷时趋近于 0。比如 2n = o(n²) 成立，但 2n² = o(n²) 不成立，因为系数 2 不趋近于 0。

用一句话串起来：O 是"不超过"，Ω 是"不少于"，Θ 是"差不多就是"，o 是"严格少于"。

2.3 最容易混淆的 Θ 和 O

初学者最常见的错误是把 O 当成 Θ 用。比如有人写"快速排序的时间复杂度是 O(n log n)"，严格来说这句话没问题，但会误导人以为快排"就是 n log n 级别"。实际上快排的最坏情况是 Θ(n²)，平均情况才是 Θ(n log n)。

我自己在写技术文档的时候有个习惯：只在确实只关心上界时写 O，需要表达"上下都卡死"的时候写 Θ。比如"哈希表查找平均 Θ(1)"就比"平均 O(1)"更准确，因为单次查找不可能比常数还快。这个习惯一开始会被人说"太较真"，但一旦参与过性能评审，就会发现这种精确性是有价值的——它逼着你去想清楚最坏和平均的区别。

3. 手把手算 T(n)：从计数到化简的完整流程

3.1 第一步：确定输入规模 n 指什么

这一步看似废话，但翻车率极高。n 是"输入规模"，不是"输入数值"。对一个数组排序，n 是数组长度；对一个整数做质因数分解，n 应该是这个整数的位数（即 log₁₀ 数量级），而不是它本身。因为计算机处理一个 64 位整数和两个 32 位整数，实际代价不会差 20 亿倍。

再举个例子，遍历字符串比较两个字符串是否相等，n 应该取两者的较小长度，因为一旦发现不同字符就可以提前返回。如果你把它当成 O(max(len1, len2))，在多数实际场景下会高估。

3.2 第二步：挑出基本操作并计数

定好 n 之后，就要选一个"主操作"来数。选择原则是：选执行次数最多的那个基本操作，或者选最能代表算法特征的那个。冒泡排序里选比较次数；二分查找里选比较次数；矩阵乘法里选乘法次数。选谁其实不影响最终结果，因为常数系数会被抹掉，但选对了会让推导过程清爽很多。

我举个具体的。下面这段代码：

def sum_array(arr): total = 0 for x in arr: total += x return total

逐行计数：第 1 行赋值 1 次；第 2 行循环，比较 n+1 次（最后一次判断越界），第 3 行加法加赋值共 2n 次；第 4 行返回 1 次。合计 T(n) = 1 + (n+1) + 2n + 1 = 3n + 3。

3.3 第三步：求和化简，甩掉常数和低阶项

得到 T(n) = 3n + 3 之后，化简只有两条规则：

1. 去掉常数系数：3n 变成 n。
2. 只保留增长最快的一项，去掉低阶项：n + 3 变成 n。

结果就是 O(n)。为什么可以这么粗暴？回到定义就明白了。3n + 3 ≤ 4n 对 n ≥ 3 成立，取 c = 4 就证明了它是 O(n)。也就是说，去掉常数系数本质上是把那个 c 吸收进来了。同理，n² + n ≤ 2n² 对 n ≥ 1 成立，所以低阶项也可以丢。

这里有个常见误区值得单独提一下：有人觉得 O(2n) 和 O(n) 是两种复杂度，还煞有介事地比较谁更优。在渐进记号体系里它们是同一个集合，写 2n 只在"我知道常数是 2，而且我关心这个常数"的语境下才有意义。这种时候应该直接用 T(n) 或者 Θ 加常数说明，而不是硬造一个 O(2n)。

4. 六类代码模式的时间复杂度速判模板

4.1 顺序、分支、单层循环

顺序结构用加法法则：几段代码依次执行，总复杂度取最大的那个。如果 A 是 O(n)、B 是 O(n²)、C 是 O(log n)，整体是 O(n²)。

分支结构取两者较大值。注意这里说的是复杂度的最大值，不是执行时间。if和else里分别写了 O(n) 和 O(1)，整体还是 O(n)，因为你必须按最坏情况考虑。

单层循环最直接：循环体如果是 O(1)，循环执行 n 次，整体 O(n)。但要点在于循环次数。for i in range(n)是 n 次，for i in range(0, n, 3)是 n/3 次，化简后还是 O(n)。

4.2 嵌套循环与乘法法则

嵌套循环用乘法法则：外层 n 次、内层 m 次，整体 O(n·m)。如果两层都是 n，就是 O(n²)。

但有个坑：内层循环的边界依赖外层变量时，不能直接相乘。看这段：

for i in range(n): for j in range(i): do_something()

内层执行次数是 0 + 1 + 2 + ... + (n-1) = n(n-1)/2，化简后是 O(n²)。你看，结果一样，但推导过程不能偷懒说"两层 n 乘出来 n²"。再看这个反例：

for i in range(n): for j in range(i, n): do_something()

内层是 n + (n-1) + ... + 1，同样是 n(n+1)/2，还是 O(n²)。但如果内层是固定长度呢？

for i in range(n): for j in range(100): do_something()

内层固定 100 次，总共 100n，化简后是 O(n) 而不是 O(n²)。这个例子很典型：看起来是双层嵌套，但只要内层次数不随 n 增长，它就是个常数。

4.3 循环变量倍增：O(log n) 的来源

对数复杂度几乎都来自"每次把规模缩小一个固定比例"或"变量按倍数增长"。两种写法：

i = 1 while i < n: i *= 2

设执行 k 次后终止，则 2^k ≥ n，即 k = ⌈log₂n⌉，所以是 O(log n)。注意底数被忽略了，因为 log₂n = log₁₀n / log₁₀2，它们之间只差一个常数因子 log₁₀2，属于常数系数。所以写 O(log n) 时不需要标底数，这也是为什么二分查找、平衡树操作统一写成 O(log n)。

二分查找是另一个经典：

def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1

区间长度从 n 变成 n/2 变成 n/4，直到 1，共 log₂n 轮，每轮 O(1)，整体 O(log n)。

4.4 递归式与主定理

递归算法没法直接数循环，得列递归式。以归并排序为例：

T(n) = 2T(n/2) + O(n)

含义是：把规模 n 的问题拆成两个规模 n/2 的子问题，合并这一步花 O(n)。解这种式子，主定理是主力工具。主定理针对形如 T(n) = aT(n/b) + f(n) 的递归式（a ≥ 1，b > 1），比较 n^(log_b a) 和 f(n) 的相对大小：

拿归并排序代入：a = 2，b = 2，n^(log₂2) = n，f(n) = n，落在情况二，所以 T(n) = Θ(n log n)。

提示：情况三的"正则条件"指存在常数 c < 1 和足够大的 n，使得 a·f(n/b) ≤ c·f(n)。这个条件在大多数常见递归式里都满足，遇到复杂的再去查证。

主定理用起来快，但它覆盖不了所有递归式。比如 T(n) = T(n−1) + O(1) 这种减法形式就不在其管辖范围内，得用别的方法。

4.5 递归树：不想背主定理时的笨办法

递归树是我最推荐新手先学的方法，因为它不需要记公式，只要会画图加法。思路是：把每层递归的总代价算出来，然后对所有层求和。

以 T(n) = 2T(n/2) + n 为例。第一层代价 n；第二层分成两个 n/2，合计 n；第三层四个 n/4，合计 n……直到规模变成 1，层数是 log₂n。每层合计都是 n，所以总和是 n·log₂n。

再看 T(n) = T(n−1) + n。第一层 n，第二层 n−1，第三层 n−2……到最后一层 1。求和是 n(n+1)/2，即 Θ(n²)。这个用主定理套不进去，但递归树一眼就能看出来。

递归树还有个好处是能暴露"叶子层不对称"的情况，比如 T(n) = T(n/3) + T(2n/3) + n 这种，主定理也处理不了，但画出来会发现每层合计都是 n，深度是 log_{3/2} n，所以是 Θ(n log n)。

4.6 均摊分析：动态数组 append 为什么是 O(1)

这一个特别容易被误判。Python 里 list 的 append 是 O(1) 吗？严格说单次操作可能是 O(n)——触发扩容时要把所有元素搬一遍。但我们仍然说 append 的平均（均摊）复杂度是 O(1)。

证明用聚合分析法：假设每次扩容容量翻倍。从空数组开始，连续 append n 次，扩容发生在第 1、2、4、8、…、2^k 次插入时，搬运代价分别是 1、2、4、…、n/2，总和小于 2n。加上 n 次插入本身，总代价小于 3n，除以 n 次操作，均摊下来是 O(1)。

这个结论在实际工程里的意义是：你可以放心用动态数组当栈或缓冲区，而不必预先分配固定容量。代价是内存可能有一倍左右的浪费，因为扩容后有空闲槽位。

5. 排序算法复杂度横向对比与选型逻辑

5.1 常见排序算法复杂度全表

这张表我建议打印出来贴在显示器边上，面试和写代码都用得上。

表里有几个点值得单独说。

插入排序的"最好 O(n)"来自于原始数据已经有序的情况。此时内层循环一进来就退出，只做 n−1 次比较。这解释了为什么工程上的混合排序（比如很多标准库用的 Timsort）要在小规模区间上切回插入排序——真实数据往往局部有序，插入排序能吃到这个红利。

计数排序的 k 是数值范围。它的 O(n + k) 里 k 可能远大于 n，比如给 10 个数排序但最大值是 10 亿，那就退化成灾难。用计数排序前一定要问自己：k 和 n 是一个量级吗？

5.2 快排最坏 O(n²) 到底会不会发生

理论上，当每次选的基准恰好是当前区间的最小值或最大值时，分区会退化成 1 和 n−1 两部分，递归深度变成 n，每层代价 O(n)，总计 O(n²)。

实践中会不会发生？用固定选第一个元素作为基准、输入又恰好是已排序数组时，每次都会命中这个最坏情况。我见过线上服务因为用户上传了有序数据导致接口超时的案例。解决办法有三个：随机选基准、三数取中、或者干脆切换到 introsort（堆排序兜底）。

注意：三数取中依然存在被构造出最坏情况的可能，随机化之所以更稳，是因为它让攻击者无法预先构造输入。安全敏感的排序场景优先选随机化版本或归并排序。

5.3 稳定性和空间复杂度哪些场景必须考虑

稳定性指相等元素在排序后是否保持原有相对顺序。什么时候必须用稳定排序？多关键字排序。比如先按姓名排序，再按部门排序，如果第二趟不稳定，同部门内的姓名顺序就乱了。前端表格的多列排序就是典型场景。

空间复杂度上，归并排序需要 O(n) 额外空间，这在嵌入式或内存敏感场景里是硬伤。快排的 O(log n) 是递归栈深度（平均情况），如果改成递归转迭代、手动维护栈，可以压到 O(1)。堆排序则是原地排序，空间 O(1)，但它的缓存局部性很差，因为访问模式是跳跃的，实际跑起来常常比快排慢好几倍——这也是"复杂度相同但性能差很多"的经典例证。

6. 实战案例：用两个堆求中位数，把 O(log n) 算明白

6.1 需求与朴素方案的天花板

问题是这样：设计一个数据结构，支持两个操作——插入一个数，以及随时查询当前所有数的中位数。数据流式到来，数量未知。

最朴素的方案是维护一个列表，插入就直接 append，查询时排序再取中间。插入 O(1)，查询 O(n log n)。如果查询很频繁，这个方案就废了。

第二个方案是插入时就排序，保持列表有序，用二分插入。插入 O(n)（因为要移动元素），查询 O(1)。查询频繁时这个方案好，但插入变成瓶颈。

两个方案都是 O(n) 级别的瓶颈，因为有大量的工作在做"全局调整"，而我们真正需要的只有中间那一个或两个数。

6.2 双堆结构的核心不变量

关键洞察是：中位数只跟"较小的一半"和"较大的一半"有关，两个半区内部的顺序完全不重要。于是我们只需要快速拿到左半区的最大值和右半区的最小值。

• 大顶堆存较小的一半，堆顶就是左半区的最大值。
• 小顶堆存较大的一半，堆顶就是右半区的最小值。
• 中位数从堆顶取。

维持两个不变量：

1. 顺序不变量：大顶堆里的任何元素 ≤ 小顶堆里的任何元素。
2. 平衡不变量：两个堆的大小差不超过 1。

这两条保证了中位数要么是较多那个堆的堆顶，要么是两个堆顶的平均值。

6.3 插入与取中位数的代价拆解

插入分三步走。第一步，把新元素推进大顶堆（先假设它属于小的一半）。第二步，把大顶堆的堆顶弹出来，推进小顶堆——这一步同时完成了两件事：保证了顺序不变量（大顶堆最大值不超过小顶堆最小值），也把"不该留在大顶堆里的最大元素"挪走了。第三步，检查大小平衡，如果小顶堆比大顶堆多，就把小顶堆堆顶推回大顶堆。

每一步都只涉及堆的插入或弹出，而堆操作是 O(log n)——插入是"上浮"最多 log n 层，弹出堆顶是"下沉"最多 log n 层。三步都是常数次堆操作，所以总插入代价是 O(log n)。

取中位数只看两个堆顶，O(1)。对比一下，前面的方案里插入是 O(n)，这里是 O(log n)，查询从 O(n log n) 降到 O(1)。

6.4 关键代码与逐行复杂度注释

import heapq class MedianFinder: def __init__(self): # 大顶堆，存较小的一半，Python 只有小顶堆，用负数模拟 self.small = [] # 小顶堆，存较大的一半 self.large = [] def add_num(self, num): # 先入小半边，再把它里面最大的挪出来，保证顺序不变量 heapq.heappush(self.small, -num) # O(log n) heapq.heappush(self.large, -heapq.heappop(self.small)) # O(log n) # 平衡：小顶堆元素多了就还回去一个 if len(self.large) > len(self.small): heapq.heappush(self.small, -heapq.heappop(self.large)) # O(log n) def find_median(self): if len(self.small) > len(self.large): return -self.small[0] # O(1) return (-self.small[0] + self.large[0]) / 2 # O(1)

用负数模拟大顶堆是个小技巧，因为 Python 的heapq只提供小顶堆。压入-num、取出时再取反，就能得到大顶堆语义。这个转换只是符号层面的操作，不改变复杂度。

跑一遍验证：依次插入 1、2、3。插入 1 后，small = [-1]，large = []，中位数是 1。插入 2 后，small = [-1]，large = [2]，中位数是 (1+2)/2 = 1.5。插入 3 后，large 变成 [2, 3]，大小失衡，把 2 挪回 small，得到 small = [-2, -1]，large = [3]，中位数是 2。正确。

再算一下空间：存储了全部 n 个数，所以是 O(n)。这是流式场景无法回避的，除非允许近似算法。

7. 常见误区与排查清单

7.1 十个高频踩坑

我把这些年遇到的错误整理了一下，按出现频率排序：

7.2 复杂度存疑时的三步排查法

如果你推出来的复杂度和直觉对不上，可以按这个顺序检查。

第一步，重数循环次数，别数循环层数。写下最内层语句总共执行了多少次，最好用一个关于 n 的表达式写出来。很多错误都是"看到两层循环直接写 n²"造成的。

第二步，检查有没有提前终止或条件跳过。break、return、边界依赖都会让实际次数小于最坏次数。要注意区分"平均"和"最坏"，别把两者的结论混着用。

第三步，递归必须列式子。函数体里数循环是不够的，要把递归调用也算进去。列完式子后，优先尝试主定理，套不进去就画递归树。

7.3 面试场景下的表达技巧

面试里被问复杂度，别只报一个结果。我通常这样说："这个解法用了哈希表做计数，遍历数组一遍是 O(n)，遍历哈希表是 O(k)，k 是不同值的个数，所以整体 O(n + k)，空间 O(k)。"

这种表达有三个好处：展示了推导过程、暴露了变量的定义、给出了优化的方向。如果面试官追问"能不能只用 O(1) 空间"，你就知道该往哪儿想了。

还有一种情况是面试官问"你这个 O(n) 能再优化吗"，这时候要想清楚下界是什么。如果问题本身要求读入所有 n 个元素，那 Ω(n) 是绕不过去的，你就该回答"信息论下界决定了至少 Ω(n)，我这已经是紧确的"，而不是硬凑一个看起来更快的方案。

7.4 写业务代码时的工程取舍

离开面试场景，日常写业务代码其实很少需要精确的复杂度推导，更多是快速估算量级，判断方案是否可行。我的经验是关注三个数字：n 的量级是多少、单次操作大概多少纳秒、时间预算有多少毫秒。

粗略地说，十亿次简单操作在现代服务器上大约秒级。所以当 n 是 10⁵ 时，O(n²) 就是 10¹⁰ 次操作，直接出局，必须换 O(n log n)。当 n 是 10³ 时，O(n²) 只有 10⁶ 次，完全够用，没必要为了"理论最优"引入复杂的数据结构。

这个估算还能帮你快速识别性能隐患。看到循环里嵌套查数据库，或者循环里做字符串拼接，就要警惕——这些都是把 O(n) 变成 O(n²) 甚至更糟的常见操作，而且实际代价远高于理论分析，因为每次操作背后都可能是一次网络往返或一次内存分配。

最后分享一个我在实际排查中学到的经验：当线上接口变慢，第一件事不是看算法复杂度，而是看有没有循环里做 I/O。我见过太多明明复杂度写着 O(n)，实际却跑了几十秒的代码，原因就是那个 n 次循环里每次都发了一次网络请求。复杂度分析告诉你的是计算量的增长趋势，但真实的耗时瓶颈常常藏在常数项里，而常数项在真实系统里可以大到离谱。所以复杂度是设计阶段的工具，性能优化阶段的工具则是火焰图和耗时打点，两者配合着用，才不至于在错误的方向上钻牛角尖。