很多人第一次接触复杂度分析都是在刷题或者准备面试的时候。看到题解上写着本解法时间复杂度 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) 的算法在 n10 的时候完全可能输给 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 4n₀ 5当 n ≥ 5 时3n 5 ≤ 3n n 4n成立。所以 3n 5 O(n)。那能不能说它是 O(n²) 呢也能因为取 c 1、n₀ 13n 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 行循环比较 n1 次最后一次判断越界第 3 行加法加赋值共 2n 次第 4 行返回 1 次。合计 T(n) 1 (n1) 2n 1 3n 3。3.3 第三步求和化简甩掉常数和低阶项得到 T(n) 3n 3 之后化简只有两条规则去掉常数系数3n 变成 n。只保留增长最快的一项去掉低阶项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(n1)/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 ≥ 1b 1比较 n^(log_b a) 和 f(n) 的相对大小情况条件结论情况一f(n) O(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落在情况二所以 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(n1)/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²)O(n)O(n²)O(1)稳定插入排序O(n²)O(n)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定希尔排序O(n^1.3)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 log n)O(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)稳定基数排序O(d(n k))O(d(n k))O(d(n k))O(n k)稳定表里有几个点值得单独说。插入排序的最好 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。这两条保证了中位数要么是较多那个堆的堆顶要么是两个堆顶的平均值。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]中位数是 (12)/2 1.5。插入 3 后large 变成 [2, 3]大小失衡把 2 挪回 small得到 small [-2, -1]large [3]中位数是 2。正确。再算一下空间存储了全部 n 个数所以是 O(n)。这是流式场景无法回避的除非允许近似算法。7. 常见误区与排查清单7.1 十个高频踩坑我把这些年遇到的错误整理了一下按出现频率排序误区正确认知O(1) 意味着只执行一次O(1) 是执行次数不随 n 变化可能是 100 次O(2n) 比 O(n) 慢一倍两者是同一个集合没有可比性嵌套两层就一定是 O(n²)内层固定次数时是 O(n)递归的空间复杂度是 O(1)递归栈深度要计入通常是 O(递归深度)快排总是 O(n log n)最坏是 Θ(n²)平均才是 Θ(n log n)哈希表查找一定是 O(1)平均 O(1)最坏 O(n)且常数受哈希函数影响n 就是输入的那个数字n 是规模整数分解的 n 是位数复杂度低就一定跑得快小 n 时常数系数和缓存局部性更关键二分查找是 O(log n) 不用管前提前提是数据有序排序本身要花时间均摊 O(1) 等于每次都是 O(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 次循环里每次都发了一次网络请求。复杂度分析告诉你的是计算量的增长趋势但真实的耗时瓶颈常常藏在常数项里而常数项在真实系统里可以大到离谱。所以复杂度是设计阶段的工具性能优化阶段的工具则是火焰图和耗时打点两者配合着用才不至于在错误的方向上钻牛角尖。