一、起源:为什么需要一把衡量"代价"的尺子

1.1 规模增长下直觉失效

在小规模数据上,几乎任何实现都能在可接受的时间内完成。用循环逐项比较两张表的差异,在几十条记录时没有可感知的耗时;用线性查找在一百个元素中定位,也不比哈希查找慢多少。这类经验一旦被推广到更大规模,就会失效。

原因在于代价随规模增长的方式不同。线性查找的工作量与元素数成正比,哈希查找接近恒定,两者在 n 较小时差异被调用开销掩盖,在 n 达到百万级时差距可达数个数量级。以每秒约 10^8 次基本操作为参照量级:

n = 10^3    线性查找     约 10^3 次操作      微秒级
            哈希查找     约 1 次操作         纳秒级

n = 10^6    线性查找     约 10^6 次操作      毫秒级
            哈希查找     约 1 次操作         纳秒级

同样的代码、同样的机器,仅因为输入规模变化,判断就从"两者都可以"变成"其中一种不可用"。直觉失效的根源是:人在小规模下感知到的是常数因子,而规模增长后起作用的是增长量级。

1.2 脱离机器与语言的比较需求

直接计时是最直观的代价度量,但它给出的结论无法迁移。

  • 与机器绑定:同一段代码在不同 CPU 上的耗时相差数倍,同一台机器在不同负载、不同频率档位下的结果同样不稳定。
  • 与语言和运行时绑定:解释执行与即时编译、有无垃圾回收、是否装箱、容器实现不同,都会改变常数因子,甚至改变实现之间的排序。
  • 与输入绑定:同一实现的耗时随输入数据的分布变化,最坏输入可能比随机输入慢一个数量级。
  • 不可外推:一次测量只回答"在这台机器、这份数据、这个版本下是多少",无法回答"数据量涨十倍后会怎样"。

比较两种算法时真正稳定、可迁移的量,是代价随输入规模变化的增长速度。这个量只由算法本身的结构决定,与机器主频、编程语言、编译器优化无关。复杂度分析就是提取这个量的方法。

1.3 复杂度分析的定位:预测趋势而非精确计时

复杂度分析给出的不是耗时数值,而是增长趋势与其分类。它可以回答的问题:

可以回答 不能回答
数据量增长 10 倍时,耗时大致增长几倍 单次调用耗时是 30 纳秒还是 300 纳秒
两个算法中哪一个在规模变大后更占优势 在当前数据规模下哪一个实际更快
该解法在目标规模下是否可行 该解法在具体硬件与实现下的绝对性能
空间占用随规模如何变化 运行时的真实内存峰值与 GC 压力

由此确定其使用方式:

  1. 用于筛选。在候选方案中排除在目标规模下不可行的量级,把选择范围缩小到常数因子层面的比较。
  2. 用于预估可行性。在写下代码之前判断目标规模是否会落入不可接受的范围。
  3. 不用于定量承诺。容量、延迟目标一类需要具体数值的结论由实测给出,方法与边界见 linux: 压测与性能基线 与 JMH 微基准测试。

复杂度分析与接口抽象是两条互补的主线:ADT 决定了"能做什么",复杂度决定了"以什么代价做"。同一 ADT 的不同存储结构(见 抽象数据类型(ADT))之间的取舍,最终都要落到复杂度上。


二、原理

2.1 渐近记号

渐近记号把"增长量级"形式化。以 T(n) 表示输入规模为 n 时的代价(时间或空间),以 n₀ 表示某个足够大的起点:

记号 名称 形式化含义 直观说法 典型用法
O(f(n)) 大 O 存在 c、n₀,使所有 n ≥ n₀ 有 T(n) ≤ c·f(n) 增长速度不超过 f 给出上界,声明"最坏也不会超过"
Ω(f(n)) 大 Ω 存在 c、n₀,使所有 n ≥ n₀ 有 T(n) ≥ c·f(n) 增长速度不低于 f 给出下界,声明"至少需要这么多"
Θ(f(n)) 大 Θ 同时满足 O(f(n)) 与 Ω(f(n)) 增长速度与 f 同阶 给出紧界,是最准确也最常用的结论
o(f(n)) 小 o 对任意 c > 0,存在 n₀ 使所有 n ≥ n₀ 有 T(n) < c·f(n) 增长速度严格低于 f 强调"不是同阶",如 n = o(n log n)

四个记号的差别集中在两点:方向(上界还是下界)与是否紧(是否允许差距任意大)。

上界与紧界的区别。 "哈希表查找是 O(n)"这句话在形式上成立——最坏情况下所有键落在同一个桶,逐个比较确实是线性的。但这个上界极不紧,无法反映哈希表的实际行为;写成 Θ(1)(期望意义下)或"平均 O(1)、最坏 O(n)"才有信息量。实践中,只给宽松上界等于没有结论。反过来,下界同样需要说明范围:比较排序的下界 Ω(n log n) 是对"仅通过比较获取元素间顺序"这一类算法的下界,一旦允许利用键的取值结构(计数排序、基数排序),该下界不再适用。

常见误用。

  1. 把最坏情况当作大 O 的定义。 这是最常见的一处混淆。大 O 描述的是函数的增长上界,"最好情况、最坏情况、平均情况"描述的是分析对象,两者是正交的两个维度。可以写"最好情况 O(1)"(如线性查找第一个元素即命中),也可以写"最坏情况 O(n)"。正确写法是"在最坏情况下,该算法的时间复杂度为 O(n)",而不是默认大 O 就等于最坏情况。
  2. 用 O 表示下界。 "该算法至少需要 O(n log n)"是错误表述,下界应当用 Ω。O 与 Ω 混用会让结论无法判断是"够用"还是"必需"。
  3. 忽略"n 足够大"这一前提。 渐近结论只在 n 超过某个起点后成立。归并排序比插入排序量级更优,但插入排序在 n 小于十几时往往更快,因为渐近分析忽略了常数因子与递归调用开销。
  4. 把常数写进记号。 O(2n)、O(n/2)、O(3n² + 5n + 7) 都应约简为 O(n)、O(n)、O(n²)。渐近记号本身已丢弃常数与低阶项,保留它们只说明尚未完成分析。
  5. 认为 O(1) 就等于快。 O(1) 只说明不随规模增长,不说明绝对耗时。一次数据库查询的索引命中是 O(log n),一次内存数组取值是 O(1),前者的实际耗时可以是后者的百万倍。O(1) 的常数因子同样可以相差几个数量级。
  6. 多变量场景下只写一个 n。 涉及两张表长度 m 与 n 的算法,代价应写成 O(m·n);用 O(n²) 表述会掩盖其中一个维度可能远小于另一个的事实。
  7. 未说明 n 指代什么。 字符串处理的 n 可以是字符数,图算法的 n 可以是顶点数、m 是边数。n 的口径不同,结论不可比较。图算法中 O(n + m) 与 O(n²) 的对比在稀疏图上意义完全不同。

2.2 量级与增长

下表给出各量级在同一规模下的操作次数估值(对数保留一位小数,其余取数量级),用于建立"规模多大时量级差异才显现"的判断:

量级 名称 n = 10 n = 100 n = 10³ n = 10⁶ 典型来源
1 常数 1 1 1 1 数组下标寻址、哈希查找(期望)
log₂n 对数 3.3 6.6 10 20 二分查找、平衡树操作
n 线性 10 100 10³ 10⁶ 顺序遍历、单层扫描
n log₂n 线性对数 33 664 9.97×10³ 1.99×10⁷ 归并排序、堆排序、比较排序下界
n² 平方 10² 10⁴ 10⁶ 10¹² 双重循环、冒泡排序、朴素去重
n³ 立方 10³ 10⁶ 10⁹ 10¹⁸ 朴素矩阵乘法、三重循环
2ⁿ 指数 10³ 1.27×10³⁰ 10³⁰¹ — 枚举全部子集、朴素递归斐波那契
n! 阶乘 3.6×10⁶ 9.3×10¹⁵⁷ — — 枚举全排列、朴素旅行商

增长对比的读法。 表中的关键不在单点数值,而在同一行内相邻两列的倍数关系:

  • 对数级:n 增长 10 倍,代价只增加一个常数(约 3.3)。从 10 增长到 10⁶(五个数量级),代价从 3.3 增长到 20,不足 7 倍。
  • 线性级:n 增长 10 倍,代价增长 10 倍。规模与代价同步。
  • 线性对数级:n 增长 10 倍,代价增长约 11 至 12 倍,略高于线性,与线性级处于同一梯队。
  • 平方级:n 增长 10 倍,代价增长 100 倍。线性级与平方级的分界线是"数据量翻倍后耗时是否翻两番",这是实践中区分两者的快速判据。
  • 指数与阶乘级:n 每增加 1,代价就乘一个因子,可用规模被迅速压缩到几十以内。

n 的取值与实用边界。 以每秒约 10^8 次基本操作为参照,不同量级可处理的最大规模与相应耗时:

量级 可处理的规模上限 依据
n log n 10⁷ 至 10⁸ 量级 10⁸ 规模的排序约需数秒
n² 10⁴ 量级 10⁴ 规模需 10⁸ 次操作,约 1 秒;10⁵ 规模需 10¹⁰ 次,约 100 秒
n³ 数百至 10³ 量级 10³ 规模需 10⁹ 次操作,约 10 秒
2ⁿ 20 至 30 量级 2³⁰ ≈ 10⁹,约 10 秒;2⁴⁰ 已超过十分钟
n! 11 至 12 量级 12! ≈ 4.8×10⁸,接近 1 秒

三个可直接使用的判断:

  1. n 较小时常数因子主导。 在 n 小于 10 至 20 的区间,n² 与 n log n 的差距常被循环开销、函数调用、内存分配等常数因素覆盖,此时简化实现往往比"更优量级"的复杂实现更快。优化应针对真实规模,而非量级排名。
  2. 交叉点比排名重要。 两个不同量级的算法存在一个交叉规模:低于该规模时低量级算法更慢,高于该规模时反超。选型需要关心的是交叉点相对目标规模的位置。
  3. 量级决定了可行性边界。 当结论属于指数或阶乘级时,问题不再是"如何优化常数",而是必须改变解法(改用动态规划、分支限界、近似算法),因为常数优化无法跨越量级带来的量级差距。

2.3 分析对象:最好、最坏、平均与摊还

同一个算法在不同输入上的代价不同,因此需要明确"分析的是哪种输入"。

分析对象 定义 用途 局限
最好情况 使代价最小的输入下的代价 说明性能下限,判断是否存在廉价路径 几乎不反映真实表现,不能作为选型依据
最坏情况 使代价最大的输入下的代价 给出性能保证,是延迟上限与容量规划的依据 可能过度悲观,与实际分布相差很远
平均情况 在输入分布假设下代价的期望 描述典型表现 结论依赖于分布假设是否成立
摊还 一串操作序列的总代价均摊到每次操作 估计长期运行的平均成本 不保证单次操作的延迟上界

最好与最坏。 线性查找在首位命中时为 O(1),在末位或不存在时为 O(n)。工程上关注的是最坏情况,因为它决定了服务的最差响应时间与超时设置;只有最坏情况的界才能保证"任何输入都不会超过该代价"。

平均情况的分析前提。 平均代价是对输入分布求期望,因此必须显式声明分布假设。常见的三类假设:

  1. 等概率假设。线性查找中目标元素出现在每个位置的概率相同,平均比较次数为 (n+1)/2,仍是 O(n)。若实际访问存在热点(少数元素被反复查询),等概率假设不成立,把热点元素前移可显著降低实际代价。
  2. 随机输入假设。快速排序在随机排列下平均复杂度为 O(n log n)。该结论依赖输入顺序与枢轴选择无关;若输入已近乎有序且固定选取首元素为枢轴,每次划分极不平衡,退化为 O(n²),这正是最坏输入被构造的方式。
  3. 哈希均匀假设。哈希表平均 O(1) 的结论依赖哈希值在桶间近似均匀分布。若哈希函数对某类键退化(大量键的低位相同),或键由外部可控(哈希碰撞攻击),平均假设被破坏,单次查找退化到 O(n)。

由此得到一条实践结论:平均情况的结论必须与分布假设一起给出,并在假设可能不成立时用最坏情况的界兜底。哈希容器在链表长度达到阈值后转为红黑树,正是为均匀假设失效准备的兜底,见 Java 集合框架实现原理 的链表与红黑树转换阈值一节。

摊还分析。 摊还分析不依赖输入分布,是对操作序列本身性质的确定性结论。它回答"连续执行 n 次操作的总代价是多少,均摊到每次是多少"。三种方法:

  1. 聚合法。先求 n 次操作的总代价上界 T(n),再除以 n 得到摊还代价。动态数组的例子:容量按倍数增长时,n 次追加引发的元素搬移总量不超过 2n(几何级数之和),总代价 O(n),摊还每次 O(1)。该方法最直观,适合结构简单的场景;动态数组的扩容倍数选择与均摊结论见 栈与队列 中数组扩容与均摊代价一节。
  2. 记账法。为每类操作设定摊还代价(相当于收费),并允许把余额存入"信用"账户,供后续的昂贵操作支取。要求任意前缀操作序列中信用余额始终非负。动态数组的例子:每次追加收取 3 个单位,1 个单位用于当前的写入,2 个单位存储在该元素上;扩容搬移某元素时用其存储的 2 个单位支付搬移成本,任何时刻余额都不为负,因此摊还代价为常数。
  3. 势能法。定义势函数 Φ,把结构的"潜在未支付代价"映射为非负实数,摊还代价定义为"实际代价 + ΔΦ"。总摊还代价为总实际代价加上首末势能差,只要 Φ 非负且 Φ₀ = 0,总摊还代价就是总实际代价的上界。动态数组取 Φ 为两倍元素数减去容量,追加操作的实际代价为 1(无扩容)或 1+搬移量(扩容),两种情况下的摊还代价都不超过某个常数。散列扩容、栈上的多弹出操作(multipop)都适合用势能法统一处理;散列表扩容的再散列成本与内存峰值见 散列表 中负载因子与扩容一节。

摊还与平均的关键区别:

  • 摊还是对所有输入序列成立的确定性结论,不含概率成分;平均是对输入分布求期望,分布假设改变则结论改变。
  • 摊还给出的是"长期平均",不保证单次操作的延迟上限。动态数组在触发扩容的那一次追加是 O(n),若该次延迟落在请求路径上,仍会造成超时。需要单次延迟确定性的场景必须放弃摊还结构,或改用增量扩容、分段结构。
  • 摊还通常优于平均:能给出摊还界时,一般不需要再引入分布假设。

2.4 递归式

递归算法的代价由递归式描述。求解递归式的常用手段有三种。

递归树方法。 把递归式按层展开成一棵树,每层节点代价求和,再对层求和。

以归并排序为例,T(n) = 2·T(n/2) + c·n:

第 0 层:           c·n                            代价 c·n
第 1 层:      c·n/2     c·n/2                     代价 c·n
第 2 层: c·n/4  c·n/4  c·n/4  c·n/4               代价 c·n
 ...
第 k 层:共 2^k 个节点,每个代价 c·n/2^k            代价 c·n
 ...
叶子层:n 个节点,每个常数代价                      代价 c·n

树高为 log₂n(每层规模减半,缩减到 1 需要 log₂n 层),每层代价恒为 c·n,总代价 Θ(n log n)。

递归树方法的价值在于,它不依赖主定理的适用条件,几乎对所有递归式都能给出结论,只是当每层代价不等时需要对求和做出估计:

  • T(n) = T(n/2) + O(1):每层常数代价,层数 log n,结果 O(log n)。
  • T(n) = T(n/2) + O(n):顶层代价 n,逐层减半,几何级数求和为 O(n),结果 O(n)。
  • T(n) = 2·T(n/2) + O(n log n):每层代价不等,总代价 O(n log²n)。

主定理。 对形如 T(n) = a·T(n/b) + f(n) 的递归式(a ≥ 1,b > 1,a、b 为常数,f(n) 渐近正),比较 f(n) 与 n^(log_b a) 的增长速度:

情形 条件 结论 直观解释
情形一 f(n) = O(n^(log_b a − ε)),ε > 0 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 + ε)) 且存在 c < 1 使 a·f(n/b) ≤ c·f(n) T(n) = Θ(f(n)) 根节点代价占主导,递归部分可忽略

情形三附加的条件称为正则条件,作用是排除"单层代价下降得不够快、下层反而超过上层"的构造。线性函数、多项式、n log n 一类函数通常自动满足。

三种情形的实例:

递归式 a, b, f(n) n^(log_b a) 情形 结论 对应算法
T(n) = 2T(n/2) + n a=2, b=2, f=n n 情形二 Θ(n log n) 归并排序、堆排序
T(n) = T(n/2) + 1 a=1, b=2, f=1 n⁰ = 1 情形二 Θ(log n) 二分查找
T(n) = 2T(n/2) + n² a=2, b=2, f=n² n 情形三 Θ(n²) 划分代价过高的分治
T(n) = 7T(n/2) + n² a=7, b=2, f=n² n^2.807 情形一 Θ(n^2.807) Strassen 矩阵乘法
T(n) = 9T(n/3) + n a=9, b=3, f=n n² 情形一 Θ(n²) 朴素分治枚举
T(n) = 2T(n/2) + n log n a=2, b=2, f=n log n n 不适用 Θ(n log²n) 见下方说明

主定理的适用边界。 主定理不覆盖所有递归式,以下情况需要退回到递归树或代入法:

  1. 落在情形之间的空隙。T(n) = 2T(n/2) + n log n 中,f(n)/n^(log_b a) = log n,虽比 n^(log_b a) 大,但并非多项式级别地大(不存在 ε > 0 使 f(n) = Ω(n^(1+ε))),既不满足情形二也不满足情形三。用递归树求得 Θ(n log²n)。
  2. 子问题规模不成等比。T(n) = T(n−1) + n 的缩减方式是相减而非相除,主定理不适用;用递归树逐层展开得 n + (n−1) + … + 1 = Θ(n²),对应快速排序的最坏情况与选择排序。
  3. 子问题规模不等。T(n) = T(n/3) + T(2n/3) + n 中两个子问题比例不同,需用递归树逐层求和:每层总代价为 n,最短路径深度 log₃n、最长路径深度 log₃␣₂ n,故总代价 Θ(n log n)。该递归式对应随机化快速排序的平均情形。
  4. 参数不是常数。a、b 依赖 n(如 T(n) = n·T(n/2) + n)时,主定理的前提不成立。
  5. 非多项式形态。出现 √n、log n 作为规模时,需先做变量替换。T(n) = 2T(√n) + log n 令 n = 2^m,转化为 T(2^m) = 2T(2^(m/2)) + m,再逐层分析。

代入法。 先猜测结论形式,再用数学归纳法验证。步骤是:猜测 T(n) = O(f(n)),假设对所有小于 n 的规模成立,代入递归式推导 T(n) ≤ c·f(n),并处理边界条件与取整带来的偏差(floor、ceil 会让 n/2 不完全相等,通常靠放宽常数 c 吸收)。代入法的两个用途:

  1. 验证递归树或主定理得到的结论。
  2. 处理主定理不适用、递归树不易估计的递归式;上界与下界的猜测需要分别证明。

常见递归结构的复杂度结论。

结构 递归式 复杂度 说明
二分查找 T(n) = T(n/2) + O(1) O(log n) 每次排除一半,递归深度为 log₂n
归并排序 T(n) = 2T(n/2) + O(n) O(n log n) 合并代价线性,层数 log n
快速排序(平均) T(n) = T(n/3) + T(2n/3) + O(n) O(n log n) 划分近似均衡
快速排序(最坏) T(n) = T(n−1) + O(n) O(n²) 每次划分只减少一个元素
二叉树遍历 T(n) = T(k) + T(n−1−k) + O(1) O(n) 每个节点访问常数次,与树形无关
朴素递归斐波那契 T(n) = T(n−1) + T(n−2) + O(1) O(φⁿ) ≈ O(1.618ⁿ) 指数级,重复子问题导致
用记忆化的斐波那契 每个子问题只算一次 O(n) 时间换空间
汉诺塔 T(n) = 2T(n−1) + O(1) O(2ⁿ) 移动次数为 2ⁿ − 1
二分求幂 T(n) = T(n/2) + O(1) O(log n) 与二分查找同构

递归结构还带来一项常被忽略的成本:调用栈深度。树遍历的递归深度等于树高,平衡树上为 O(log n),退化的链表形树上为 O(n),深度输入可能直接触发栈溢出。可用规模受栈空间限制时,应把递归改写为显式栈的迭代形式,此时空间复杂度从"随深度增长"变为"由显式栈的容量决定"。

2.5 空间复杂度

空间复杂度的度量口径需要先明确:通常只统计输入之外额外申请的空间(auxiliary space),而不计入输入本身。某算法"原地"运行时,额外空间为 O(1) 或 O(log n)(仅递归栈)。

原地与非原地。

算法 额外空间 性质
冒泡排序、插入排序、选择排序 O(1) 原地
堆排序 O(1) 原地
快速排序 平均 O(log n),最坏 O(n) 近乎原地,空间来自递归栈
归并排序(数组) O(n) 非原地,需要等长辅助数组
归并排序(链表) O(log n) 近乎原地,仅递归栈
计数排序 O(k),k 为键的取值范围 非原地,k 可能与 n 无关而很大
二叉树中序遍历(递归) O(h),h 为树高 空间来自递归栈

原地算法的价值不只在省内存:它避免了大规模的内存分配,从而减少 GC 压力,也提高了缓存局部性。这在数据量大时往往比省下的内存本身更重要。

递归栈空间。 递归算法的空间复杂度由"最大递归深度 × 每层栈帧大小"决定,与递归调用总次数无关。归并排序的树形递归有两种口径:若统计所有栈帧,深度为 log n,空间 O(log n);若统计辅助数组,则为 O(n)。面试中常被问到的是前者之外的辅助数组,工程中应同时记录两项。

输出敏感型复杂度(output-sensitive)。 一部分算法的合理复杂度由输入规模与输出规模共同决定:

  • 枚举一个 n 元集合的全部子集,输出本身有 2ⁿ 个,因此 O(2ⁿ) 是输出规模的下界,已是最优。
  • 求两集合的交集,结果规模可达 min(m, n),此时 O(min(m, n)) 是最优,无需追求 O(1) 空间之外的进一步优化。
  • 计算几何中的凸包,输出有 h 个顶点,Graham 扫描为 O(n log n),而 Jarvis 步进为 O(n·h)——在 h 远小于 n 的场景更优。
  • 稀疏图算法用 O(n + m) 表述(m 为边数)比 O(n²) 更能反映真实代价。

判断标准是"输出规模是否可能远小于最坏情况"。若是,用输出规模表达复杂度更有意义,也更能指导选型。

空间与时间的换算。

  1. 预计算与缓存(记忆化):把重复计算的子问题结果存起来,时间从指数级降到多项式级,代价是 O(n) 的空间。这是动态规划的基本手段。
  2. 滚动数组:当状态转移只依赖前若干行的状态时,可以把 O(n²) 的表格压缩为 O(n) 甚至 O(1),用状态覆盖的顺序保证正确性。
  3. 空间换时间:建立索引、预排序、构造哈希表,把多次线性查找降为常数或对数查找。
  4. 时间换空间:流式处理、分批读取、不落缓存,用重复计算或重复 IO 换取内存的常量占用。

这条换算关系在多处出现:数据库的索引与物化视图、HTTP 的缓存、JVM 的方法区与代码缓存、构建系统的增量编译结果。取舍依据是资源的相对稀缺程度:内存受限(如容器内存配额)时偏向时间换空间,CPU 受限时偏向空间换时间。

2.6 理论的边界

复杂度分析能给出代价的增长趋势,但有些界限不是"实现得不够好",而是问题本身的固有性质。

下界与比较排序的下界。 判定任何基于比较的排序都需要 Ω(n log n) 次比较,论证方式是决策树:

n 个元素共有 n! 种可能的排列,算法必须区分全部 n! 种情况。
决策树的每个叶节点对应一种输出排列,因此叶节点数不少于 n!。
高度为 h 的二叉树最多有 2^h 个叶节点,因此 2^h ≥ n!
取对数:h ≥ log₂(n!) ≥ log₂((n/2)^(n/2)) = (n/2)·log₂(n/2)
即 h = Ω(n log n)

结论有两个要点:

  1. 它是对"只通过元素间比较获取顺序信息"这一类算法的下界。归并排序与堆排序达到该下界,因此在这一类中已是最优,不存在量级上的改进空间;优化只能落在常数因子与缓存行为上。
  2. 绕过该下界必须改变前提。计数排序、基数排序、桶排序利用了键的取值结构(整数范围、位宽、可分桶),不依赖比较,因此可达到 O(n + k) 或 O(d·n)。代价是适用范围受限:键必须是小范围整数或可映射到有限区间,且空间开销与键的取值范围绑定。

判定问题、可判定性与停机问题。 部分问题不存在任何算法能在有限时间内对所有输入给出正确答案(如停机问题),这类问题属于不可判定。遇到不可判定的问题,唯一的方向是放宽要求:限制输入范围、要求近似解、或接受"可能不终止"。

P 与 NP 的直观含义。

  • P:存在多项式时间算法的问题类。排序、最短路、最大流、线性规划都属于 P。
  • NP:给定一个候选解,能在多项式时间内验证其正确性的问题类。P 包含于 NP。
  • NP-hard:所有 NP 问题都能在多项式时间内归约到它;它本身未必属于 NP。
  • NP-complete:既属于 NP 又是 NP-hard 的问题,是 NP 中最难的一类。旅行商问题的判定形式、布尔可满足性(SAT)、图着色、集合覆盖、背包(判定形式)都属于此类。
  • P 是否等于 NP 尚未解决。工程意义不在于等待答案,而在于识别问题类型:若手头的问题被归约为某个 NP-complete 问题,应当放弃"找到多项式时间精确算法"这一目标。

对 NP-hard 问题的三条可行路径:

路径 做法 适用 代价
精确算法 分支限界、动态规划、整数规划求解器 规模小,或结构特殊(如背包的容量较小) 最坏情况仍是指数时间,需要设置时间上限
近似算法 给出有质量保证的解,如顶点覆盖的 2-近似、旅行商满足三角不等式时的 1.5-近似 可以接受"距最优不超过常数倍" 无法保证最优,需给出近似比证明
启发式 贪心、局部搜索、模拟退火、遗传算法 规模大,对最优性无严格要求 无质量保证,结果依赖参数与初始解

启发式与近似算法的区别在于是否有理论保证:近似算法给出"解不超过最优解的 c 倍"这类可证明的界;启发式只有经验表现。两者都必须在结论中说明"这是可行解而非最优解"。

2.7 理论与实测的差异

复杂度分析给出的是增长量级,实测给出的是特定条件下的数值。两者之间的差距来自多个方面,忽略这些差距会导致"量级更优的实现反而更慢"这类反直觉结果。

差异来源 机制 后果
常数因子 同样的量级下,指令条数、函数调用、分支数量可能相差数倍 小规模下量级排序被常数排序覆盖
内存层次与缓存命中 顺序访问与随机访问的延迟差可达两个数量级(L1 约几纳秒,主存约上百纳秒) 同为 O(n) 的数组遍历与链表遍历,实际耗时相差近一个数量级
分支预测 不可预测的分支导致流水线冲刷 同一算法在有序数据与随机数据上的耗时不同,约为常数倍的差距
语言与运行时开销 解释执行与即时编译、装箱与拆箱、边界检查、虚方法分派、GC 相同的算法描述在不同实现下差异显著
并发与流水线 复杂度模型是串行模型,未包含并行度与锁争用 多核场景下量级更差的实现可能因并行度更高而更快
数据分布与最坏输入 平均结论依赖分布假设 构造的最坏输入可让哈希退化为链表、快排退化为平方
外部成本 IO、网络、下游服务、序列化 局部量级优化在端到端耗时中占比可能极小
隐藏的空间代价 分配与回收的间接成本 时间上的量级相同,内存峰值与 GC 次数差异显著

三个具体例子:

数组与链表的线性遍历。 两者的时间复杂度都是 O(n),但数组元素在内存中连续,一次缓存行可覆盖多个元素,顺序扫描的硬件预取几乎总在命中;链表每跳一次都要访问一个可能位于堆中任意位置的节点对象,几乎每次都是缓存未命中。实测中同一规模的遍历,链表可能慢近一个数量级。相关代价的分析见 Java 集合框架实现原理。

排序在小规模下的表现。 插入排序是 O(n²),归并排序是 O(n log n),但多数语言标准库的排序实现对小区间(常见阈值为 7 至 16 个元素)切换为插入排序,正是因为在交叉规模以下插入排序的常数因子更小。这是"量级更优不等于更快"的直接体现。

哈希表与红黑树。 哈希表期望 O(1),红黑树为 O(log n)。除规模极大外,红黑树的 keyset 有序遍历能力可能比哈希表的常数优势更有价值;同时哈希表的实际耗时受哈希函数质量、负载因子、键对象分配成本影响,而红黑树的比较成本受比较器实现影响。两者的取舍需要实测。

结论。 复杂度分析负责筛选候选方案、排除不可行的量级、预测规模增长后的趋势;实测负责在量级相同或接近的候选中确定取舍。两者的分工与边界:

  • 量级不同且目标规模足够大时,可以依据分析直接决策,无需实测。
  • 量级相同,或目标规模落在交叉点附近时,必须实测。
  • 实测的结论必须带条件(规模、数据分布、版本、硬件),否则不可复用。

实测方法见 JMH 微基准测试(方法级、代码路径级)与 linux: 压测与性能基线(服务级、容量级)。两者的干扰控制原则一致:固定条件、明确预热、一次只改一个变量、多轮取稳态值。


三、实现

3.1 分析方法实践

从代码推导复杂度的步骤。

  1. 确定 n 的口径。明确哪些输入量会影响执行次数:一个集合的长度、两个集合的长度、字符串长度、树的节点数、图的顶点数与边数。多个独立输入量必须分别设变量,不可合并为一个 n。
  2. 定位基本操作。找出执行最频繁的那一类语句(比较、赋值、数组访问、函数调用),以它为单位计数。基本操作的选择只影响常数因子,不影响量级结论。
  3. 逐层相乘。对每层循环,确定该层的迭代次数;嵌套循环的总次数为各层次数之积。注意迭代次数可能依赖外层变量,如内层为 i 到 n,此时内层次数为 n − i。
  4. 递归部分写递归式。递归调用的次数为 a,子问题规模为 n/b,其余工作为 f(n),写成 T(n) = a·T(n/b) + f(n),再按 2.4 的方法求解。
  5. 把库调用展开。任何库函数都对应一段实现,必须按其实现的复杂度计入(见下文)。
  6. 相加取最高阶,去掉常数与低阶项。多个顺序执行的片段代价相加,保留增长最快的项;乘号前的常数系数一律省略。

循环嵌套的推导。

// 单层循环:n 次迭代 → O(n)
for (int i = 0; i < n; i++) {
    process(items.get(i));
}

// 双重循环,两层都到 n → n × n → O(n^2)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (items.get(i).equals(items.get(j))) {
            duplicates++;
        }
    }
}

// 内层依赖外层 → n + (n-1) + ... + 1 = n(n+1)/2 → O(n^2)
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        compare(items.get(i), items.get(j));
    }
}

// 外层步长倍增 → 外层 log n 次,内层 n 次 → O(n log n)
for (int step = 1; step < n; step *= 2) {
    for (int i = 0; i < n; i += step) {
        merge(items, i, step);
    }
}

// 外层线性、内层对数 → O(n log n)
for (int i = 0; i < n; i++) {
    int j = binarySearch(sorted, items.get(i));
    record(i, j);
}

第三段的常见错误是看到"内层也是循环"就直接写 O(n²) 而不核算实际次数;当内层次数依赖外层变量时,需要把各层的次数写成关于外层变量的表达式后再求和。第四段说明"循环嵌套层数"并不直接决定量级:外层是倍增步长时实际迭代 log n 次。

库函数调用的代价必须展开。

// 隐藏的 O(n):contains 内部逐元素比较
List<String> seen = new ArrayList<>();
for (String item : items) {
    if (!seen.contains(item)) {   // 每次线性查找
        seen.add(item);
    }
}
// 总计 O(n^2)

// 改为哈希集合后每次查找期望 O(1)
Set<String> seenSet = new HashSet<>();
for (String item : items) {
    seenSet.add(item);            // 总计 O(n)
}
// 隐藏的 O(n):字符串在循环中拼接
String result = "";
for (String fragment : fragments) {
    result += fragment;           // 每次创建新字符串并复制已有内容
}
// 总计 O(n^2),n 为片段数与平均长度之积

展开方法是把每个库调用翻译成它的实现结构,再按基本操作计数。下表给出常用操作的复杂度,可作为展开的参照(Java 集合类的完整对照见 Java 集合框架实现原理):

调用 复杂度 依据
ArrayList.get(i) / set(i, e) O(1) 数组下标寻址
ArrayList.add(e)(尾部) 摊还 O(1) 可能触发扩容与搬移
ArrayList.add(i, e) / remove(i) O(n) 需要搬移后续元素
ArrayList.contains(o) / indexOf(o) O(n) 线性扫描
LinkedList.get(i) O(n) 从较近一端线性定位
LinkedList.addFirst / removeLast O(1) 直接操作头尾指针
HashMap.get / put / containsKey 期望 O(1),最坏 O(n) 哈希分布良好时;链表退化或树化后为 O(log n) / O(n)
TreeMap / TreeSet 的单个操作 O(log n) 红黑树树高保证
PriorityQueue.offer / poll O(log n) 堆的上升与下沉
PriorityQueue.contains O(n) 堆不是搜索结构
String.length() O(1) 长度字段
String.substring / 字符串 + 拼接 复制内容 复制长度与结果长度成正比
String.indexOf / contains O(n·m) 最坏 朴素匹配;实际实现有优化,最坏仍非线性
StringBuilder.append 摊还 O(1) 容量足够时追加;扩容时整体复制
Arrays.sort(基本类型) O(n log n) 双轴快排
Arrays.sort(对象) O(n log n) TimSort,最坏 O(n log n),近乎有序输入接近 O(n)
Collections.sort / List.sort O(n log n) TimSort
List.removeAll(Collection) O(n·m) 最坏 内部依赖 contains
Stream.sorted O(n log n) 排序
Stream.distinct O(n) 内部维护 LinkedHashSet
Collectors.groupingBy O(n) 按分组键散列,输出为多个小集合
正则表达式匹配 最坏 O(2^m),m 为模式长度 回溯型引擎可能指数爆炸

常见代码片段的复杂度速查表。

代码形态 复杂度 说明
对 n 个元素各做一次常数操作 O(n) 单层遍历
两层全量嵌套循环 O(n²) 两两比较、朴素去重
内层依赖外层的嵌套循环 O(n²) 三角形态循环
每次把问题规模减半 O(log n) 二分、倍增步长
规模减半且递归两次 O(n log n) 归并、分治
每次只减少一个元素 O(n²) 朴素选择、快排最坏
递归调用两次但子问题规模为 n−1 与 n−2 O(1.618ⁿ) 朴素斐波那契
循环内调用含线性扫描的库函数 量级升一阶 contains、indexOf、字符串拼接
循环内排序 O(n² log n) 排序应提到循环外
循环内建立哈希集合 O(n²) 空间与时间开销之和 集合应在循环外复用
对每个元素遍历其全部子元素(树的遍历) O(总节点数) 与树的形状无关

3.2 摊还与均摊实践

三种典型的摊还结构,日常使用频率最高。

动态数组的扩容。 容量按倍数增长(Java 的 ArrayList 为 1.5 倍),每次扩容需要把全部元素搬移到新数组,单次代价为 O(n)。由于容量按几何级数增长,n 次追加引发的搬移总量不超过元素总数的常数倍,摊还到每次追加为 O(1)。需要注意三点:

  1. 摊还不约束单次延迟。触发扩容的那一次追加是 O(n),在延迟敏感的路径上应通过预设容量消除扩容(见 Java 集合框架实现原理)。
  2. 扩容倍数影响总搬移量。倍数越大,总搬移量越小,但空间浪费与内存峰值越大。1.5 倍是总搬移量与空间利用率之间的折中。
  3. 扩容易造成内存峰值。旧数组与新数组同时存在,峰值可达 2.5 倍数组容量。这是"大数据量必须预设容量"的主要原因,其代价不止于搬移指令。

哈希表的扩容。 负载因子达到阈值时容量翻倍并重新分布元素。单次扩容为 O(n),随元素数增长的总工作量同样摊还为 O(1)。要点:

  1. 扩容的判定依据是"元素数 / 容量",因此需要的初始容量应按 元素数 / 负载因子 向上取整到 2 的幂计算。
  2. 扩容除时间开销外还带来内存峰值与计数重算,批量写入前预设容量可同时消除两者。
  3. 该摊还结论建立在哈希分布良好的前提上。分布退化时(大量键冲突)单次操作退化,摊还结论也随之失效。这是摊还分析依赖结构不变量的例子:摊还 O(1) 的前提是"每个桶的平均长度有界"。

并查集(不相交集合)的路径压缩。 两种优化共同作用:

  • 按秩合并(或按大小合并):把较矮的树挂到较高的树上,使树高保持在 O(log n) 以内。
  • 路径压缩:查找时把沿途的节点直接指向根,后续查找接近 O(1)。

单独使用路径压缩的摊还复杂度为 O(log n);单独使用按秩合并为 O(log n);两者同时使用时,n 次操作的总代价为 O(n·α(n)),摊还每次 O(α(n))。α 为反阿克曼函数,在一切可想象的输入规模下都不超过 4(α(10⁸⁰) ≈ 4),因此工程上可以按常数处理,但严格结论是"近乎常数"而非常数。

这里的摊还结论同样依赖结构不变量:"树高受到秩的上界限制,且路径压缩只会降低后续查找的代价"。使用路径压缩时若要撤销操作(可持久化并查集),该摊还结论不再成立,需要用其他结构。并查集的两种优化(路径压缩与按秩合并)以及带权变体的实现见 线段树与并查集 中并查集一节。

摊还结论的使用边界。 引用摊还结论时需要同时说明三点:结论针对的是操作序列的总代价;单次操作的最坏代价可能远高于摊还代价;结论依赖某项结构不变量,破坏该不变量(哈希函数退化、结构被外部修改)会使结论失效。

3.3 优化决策

小规模下常数因子主导。 目标规模决定了应关注的对象:

目标规模 关注点 典型做法
数十以内 常数因子、代码简洁性 用简单直接实现,不引入复杂结构;避免为微小规模引入缓存或索引
数百至数千 常数因子与低阶项 减少函数调用与对象分配,选择常数更小的实现
上万至百万 量级开始显现 检查是否存在隐藏的线性操作被放在循环内
百万以上 量级主导 确保关键路径为 O(n) 或 O(n log n),评估内存占用与 GC

数据结构选择与复杂度的关系。 选型的第一步是把访问模式翻译为操作频次,再据此比较复杂度:

访问模式 复杂度要求 推荐结构
按下标随机访问为主 随机访问 O(1) 基于数组的实现
尾部追加为主 追加摊还 O(1) 动态数组
两端增删为主 头尾操作 O(1) 双端队列、环形数组
按键查找为主 查找期望 O(1) 哈希表
需要有序遍历或范围查询 单个操作 O(log n) 平衡树、跳表
反复取最值 取最值 O(1)、插入 O(log n) 二叉堆
反复判断存在性 判定 O(1) 哈希集合
前缀匹配、字典查询 与键长相关 前缀树
频繁合并集合 摊还近常数 并查集

选型同时要看操作比例。以查找为主、写入极少的场景,哈希表与平衡树的差异被放大;写入与查找各半且需要有序时,平衡树更合适。详细对照见 Java 集合框架实现原理。

避免过早优化与必须优化时的判断依据。 优化的顺序应当是先正确、再清晰、最后依据测量结果优化,原因有三:

  1. 复杂度分析能指出候选,但不能给出实际收益。在未测量的情况下按量级猜测优化点,容易优化了不占耗时的路径。
  2. 优化通常以提高复杂度(代码结构与认知成本)为代价,若收益不可测,则净收益为负。
  3. 简化实现本身就是一种优化:更少的分配、更少的间接调用、更少的缓存失效。

需要优化的判断依据(满足其中一项即可着手):

  • 端到端占比可观:该路径在整体耗时中的占比可以通过测量确定,占比偏低时优化收益被稀释。
  • 规模会增长:当前规模下可接受,但数据量或调用量会随业务增长;此时应优先做量级级别的改进。
  • 存在隐藏的量级问题:循环内含线性操作、嵌套遍历、重复构造集合或索引。
  • 资源约束明确:内存配额、GC 停顿时间、栈深度、连接数等出现实际限制。
  • 有历史数据可比:存在基线可供对比,改动效果可验证,方法见 linux: 压测与性能基线。

优化的优先顺序,从高到低:

  1. 换算法量级:从 O(n²) 降到 O(n log n) 或 O(n),收益随规模扩大。
  2. 消除隐藏的线性操作:把循环内的 contains、字符串拼接、排序、集合构造提到循环外或换用常数级结构。
  3. 换数据结构:在同一量级内选择常数更小、缓存局部性更好的实现。
  4. 减少分配与回收:复用对象、预设容量、避免装箱。
  5. 常数级调优:减少函数调用、合并循环、调整判断顺序。

前两项属于量级层面,随规模增长收益扩大,应在规模可能增长时优先执行;后三项收益固定,在规模稳定且已测量确认热点后才值得投入。

3.4 实测方法

复杂度分析的结论需要在目标规模下验证,验证方式取决于观测对象。

测量思路与干扰控制。

  1. 固定条件:同一硬件、同一数据分布、同一版本、同一时段,一次只改一个变量。
  2. 排除干扰:关闭或隔离构建、索引、监控采集、其他基准进程;固定 CPU 频率策略并把频率作为结论的附带信息记录。
  3. 明确预热:让运行时状态(即时编译层级、类加载、缓存)进入稳态后再采集数据。
  4. 覆盖规模区间:至少取三个规模点,观察耗时随规模变化的曲线形态,而不是比较单点数值。
  5. 覆盖数据分布:至少包含随机与最坏两类输入,随机数据会掩盖分支预测与缓存局部性的差异。
  6. 多轮取稳态值:每档参数多轮测量,以中位数或稳定区间作为结论。
  7. 同时记录资源用量:时间与内存分配量一起报告,两者趋势不一致时必须解释差异来源。

基准与压测的分工。

方法 观测对象 回答的问题 结论边界
复杂度分析 算法的增长量级 规模增长后哪一方占优 量级层面的趋势,不含常数
微基准 方法或代码路径 同一量级下哪种实现局部成本更低 该版本、该规模下的相对关系
系统压测 完整服务与主机资源 能承载多少、延迟分位是多少 该环境与配置下的容量边界
线上观测 真实流量 变更后实际表现是否改善 当前数据分布下的实际结果

微基准的具体设计(预热与测量轮次分离、黑洞消费结果、分叉隔离、参数化展开规模、结果判读)见 JMH 微基准测试;压测的环境确认、基线归档、回归阈值与容量换算见 linux: 压测与性能基线。

结果表述方式。 结论需要同时包含被测内容、条件与数值,且不把局部结论外推:

  • 可用的表述:"在 JDK 17、输入规模 10⁵ 的随机数据下,实现 A 的单次耗时约为实现 B 的 3 倍,置信区间不重叠。"
  • 不可用的表述:"实现 A 性能更好"(未限定条件)、"该实现能支撑每秒百万次调用"(局部结论外推为容量结论)。
  • 引用复杂度结论时说明是最好、最坏还是平均,并对平均情况注明分布假设。

3.5 常见误判与排查

误判 表现 成因 纠正
把平均情况当最坏分析 压测通过,上线后偶发超时;构造输入时性能雪崩 平均结论依赖分布假设,热点或恶意输入改变分布 关键路径以最坏情况为准;对输入可控的接口评估恶意构造的可能
忽略隐藏循环 单次请求耗时与数据量平方相关 循环内调用了线性复杂度的库函数(contains、indexOf、字符串拼接、排序) 把库调用展开为复杂度,检查每次迭代内的最坏代价
误判库函数代价 以为容器操作都是常数级 认为 O(1) 属于"集合操作"的通性 按实现判断:哈希为期望 O(1)、平衡树为 O(log n)、列表查找为 O(n)、堆查找为 O(n)
忽略空间与 GC 代价 时间量级相同,但内存峰值与回收次数显著上升 只统计时间,未统计分配量 固定堆与回收器参数,同时记录每操作的分配量;评估内存峰值(如扩容瞬间的 2.5 倍)
在错误规模下做结论 用 10 条数据的测量结果推导百万级的表现 目标规模与测量规模不一致;小规模下常数主导 规模参数覆盖从最小可接受规模到预期峰值规模,观察曲线形态
忽略递归深度 数据规模未到,先出现栈溢出 递归深度等于结构高度,退化结构下深度为线性 评估最坏深度;必要时改写为显式栈的迭代
把摊还代价当作单次代价 平均耗时正常,但个别请求严重超时 摊还结论不约束单次延迟 延迟敏感路径消除扩容与重建;必要时用增量式结构替换
量级相同即认为性能相同 量级分析显示一致,但实际差异数倍 常数因子、缓存局部性、分页访问模式不同 量级相同或接近时以实测为准,同时控制数据分布
忽略输入预处理 同样的算法在不同调用点表现差异大 一方已在之前排序或建立了索引 把预处理成本计入整体代价,避免重复预处理或遗漏预处理
对不可解问题追求最优解 优化方向长期无效,耗时随规模爆炸 问题属于 NP-hard,不存在已知多项式精确算法 识别问题类别,转向精确算法加时间上限、近似算法或启发式

排查顺序。 出现"耗时随数据量增长异常"时的检查顺序:

  1. 确认规模增长与耗时的关系形态:线性、线性对数,还是平方级以上。平方特征通常指向嵌套遍历或循环内的线性调用。
  2. 检查循环体内是否有库调用、字符串拼接、集合构造、排序或正则匹配。
  3. 检查是否存在重复计算:同一数据在多处被反复遍历、反复解析、反复建立索引。
  4. 检查内存分配:是否有大对象、大数组、无上限容器;内存峰值是否触发额外回收。
  5. 检查最坏输入:是否存在排序退化的输入、哈希冲突集中的键、递归深度异常的树形。
  6. 检查数据的实际规模与分布是否与分析时的假设一致。
  7. 上述检查无结论时,用采样与转储定位实际热点,而不是继续按代码阅读推测。

3.6 检查清单:代码评审中的复杂度关注点

循环与嵌套。

  • 是否存在两层及以上对同一集合的完整遍历;能否改为单次遍历配合哈希索引。
  • 循环体内是否调用了含线性扫描的方法(contains、indexOf、remove(Object)、字符串拼接、正则匹配)。
  • 循环体内是否执行排序、去重、建立集合或索引;这些操作能否提到循环外。
  • 循环的步长是否为倍增或减半(对数级),是否被误读为线性。

集合与数据结构。

  • 容器的选择是否与访问模式匹配:按位置访问用数组、按键访问用哈希、需要顺序用平衡树、需要最值用堆。
  • 数据量大时是否预设容量,以消除扩容的时间开销与内存峰值。
  • 是否存在把列表当作集合使用(用 contains 做去重)的写法。
  • 是否存在对链表的按下标访问,形成隐式的平方级遍历。
  • 键对象的 equals 与 hashCode 是否一致且稳定,避免哈希退化与元素失联。

递归与分治。

  • 递归深度是否与数据规模线性相关,最坏深度是否会触发栈溢出。
  • 是否存在重复子问题;能否改为记忆化或自底向下的动态规划。
  • 递归式属于哪一类,是否落在主定理不适用的区间。
  • 归并类操作是否在每层复制了整份数据,能否改为原地合并或多个指针。

排序与去重。

  • 是否在循环内排序;能否一次排序后复用。
  • 去重是否使用哈希集合而非嵌套遍历。
  • 是否对已排序数据重复排序;能否复用排序结果。
  • 排序的键提取是否在比较器中重复计算;能否预先提取并缓存。

空间与资源。

  • 是否一次性把全部数据载入内存;能否改为分批或流式处理。
  • 是否存在与输入规模同阶的大数组或多份副本(含扩容峰值)。
  • 大对象是否在长生命周期结构中累积,是否设置了容量上限与淘汰策略。
  • 是否存在只使用一次的中间集合,能否直接消费数据源。
  • 递归或缓存所占空间是否计入结论;是否已说明是原地算法。

结论与文档。

  • 复杂度结论是否说明了分析对象(最好、最坏、平均、摊还)与 n 的口径。
  • 平均情况的结论是否与分布假设一起给出。
  • 已知的最坏输入是否被记录;是否有兜底措施。
  • 性能结论是否带测量条件(规模、数据分布、版本、硬件),是否避免无条件的最优性表述。

四、总结

定位。 复杂度分析度量的是代价随输入规模变化的增长速度,用于在规模增长后仍能成立的比较。它给出趋势与量级,不给出耗时数值;用于筛选候选与判断可行性,不用于容量与延迟承诺。定量结论由实测给出。

记号。 大 O、大 Ω、大 Θ、小 o 分别表示上界、下界、紧界与严格低阶。上界与紧界的区分决定了结论的信息量:宽松的上界在形式上成立但无指导意义。大 O 是增长上界的记号,不是"最坏情况"的同义词;分析对象与渐近记号是两个正交维度。

量级。 对数、线性、线性对数、平方、指数、阶乘之间的差距随规模扩大而急剧拉开。对数级几乎对规模不敏感,平方级在 10⁴ 规模已接近一秒,指数级在 30 以内用尽预算。n 较小时常数因子主导,此时简化实现常优于复杂实现;量级决定的是可行性边界。

分析对象。 最坏情况用于给出性能保证,平均情况需显式声明分布假设,摊还给出操作序列的长期平均且不约束单次延迟。摊还的三种方法(聚合法、记账法、势能法)结论一致,用途各异;摊还结论依赖结构不变量。

递归式。 递归树通用且直观,主定理在三种情形下给出快捷结论,落入情形之间空隙或子问题规模不成等比时需要退回归纳与展开。二分、归并、快排、树遍历、朴素递归的复杂度均可由递归式直接得到。递归深度同时决定了栈空间与栈溢出的风险。

空间。 空间复杂度的口径是输入之外的额外空间;原地算法、递归栈、输出敏感型复杂度、时空换算(预计算、滚动数组、索引与流式处理)是四个需要分别确认的维度。空间代价常通过分配与回收间接影响时间。

理论的边界。 比较排序的 Ω(n log n) 是问题固有的下界,绕过它必须改变前提;P 与 NP 的区分决定了面对问题时应当追求精确解、近似解还是启发式。近似算法有可证明的界,启发式只有经验表现,两者的结论都需注明"可行解而非最优解"。

理论与实测的差异。 常数因子、内存层次与缓存命中、分支预测、运行时开销、数据分布、外部成本与空间代价共同造成差异。数组与链表的线性遍历、小规模排序、哈希表与平衡树的取舍都说明"量级更优"不等于"实际更快"。量级不同且规模足够大时可直接依据分析决策;量级相同或落在交叉点附近时必须实测。

实现层面的落点。 推导流程为确定 n 的口径、定位基本操作、逐层相乘、写出递归式、展开库调用、约简常数与低阶项。隐藏循环是最常见的量级误判来源,其形态是循环体内调用线性复杂度的库函数。优化按"换算法量级、消除隐藏线性操作、换数据结构、减少分配、常数调优"的顺序推进,前两项随规模增长收益扩大。测量需固定条件、明确预热、覆盖规模与分布、同时记录时间与分配量,结论必须带限定条件。

复杂度分析与实测是两种互补的方法:前者回答"数据量增长后是否仍然可行",后者回答"在当前条件下哪一个实际更快"。把量级结论当作性能数值使用,与在两个量级相同的实现之间凭直觉取舍,是同一类错误的两面。