一、起源:为什么需要一把衡量"代价"的尺子
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 压力 |
由此确定其使用方式:
- 用于筛选。在候选方案中排除在目标规模下不可行的量级,把选择范围缩小到常数因子层面的比较。
- 用于预估可行性。在写下代码之前判断目标规模是否会落入不可接受的范围。
- 不用于定量承诺。容量、延迟目标一类需要具体数值的结论由实测给出,方法与边界见 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) 是对"仅通过比较获取元素间顺序"这一类算法的下界,一旦允许利用键的取值结构(计数排序、基数排序),该下界不再适用。
常见误用。
- 把最坏情况当作大 O 的定义。 这是最常见的一处混淆。大 O 描述的是函数的增长上界,"最好情况、最坏情况、平均情况"描述的是分析对象,两者是正交的两个维度。可以写"最好情况 O(1)"(如线性查找第一个元素即命中),也可以写"最坏情况 O(n)"。正确写法是"在最坏情况下,该算法的时间复杂度为 O(n)",而不是默认大 O 就等于最坏情况。
- 用 O 表示下界。 "该算法至少需要 O(n log n)"是错误表述,下界应当用 Ω。O 与 Ω 混用会让结论无法判断是"够用"还是"必需"。
- 忽略"n 足够大"这一前提。 渐近结论只在 n 超过某个起点后成立。归并排序比插入排序量级更优,但插入排序在 n 小于十几时往往更快,因为渐近分析忽略了常数因子与递归调用开销。
- 把常数写进记号。 O(2n)、O(n/2)、O(3n² + 5n + 7) 都应约简为 O(n)、O(n)、O(n²)。渐近记号本身已丢弃常数与低阶项,保留它们只说明尚未完成分析。
- 认为 O(1) 就等于快。 O(1) 只说明不随规模增长,不说明绝对耗时。一次数据库查询的索引命中是 O(log n),一次内存数组取值是 O(1),前者的实际耗时可以是后者的百万倍。O(1) 的常数因子同样可以相差几个数量级。
- 多变量场景下只写一个 n。 涉及两张表长度 m 与 n 的算法,代价应写成 O(m·n);用 O(n²) 表述会掩盖其中一个维度可能远小于另一个的事实。
- 未说明 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 秒 |
三个可直接使用的判断:
- n 较小时常数因子主导。 在 n 小于 10 至 20 的区间,n² 与 n log n 的差距常被循环开销、函数调用、内存分配等常数因素覆盖,此时简化实现往往比"更优量级"的复杂实现更快。优化应针对真实规模,而非量级排名。
- 交叉点比排名重要。 两个不同量级的算法存在一个交叉规模:低于该规模时低量级算法更慢,高于该规模时反超。选型需要关心的是交叉点相对目标规模的位置。
- 量级决定了可行性边界。 当结论属于指数或阶乘级时,问题不再是"如何优化常数",而是必须改变解法(改用动态规划、分支限界、近似算法),因为常数优化无法跨越量级带来的量级差距。
2.3 分析对象:最好、最坏、平均与摊还
同一个算法在不同输入上的代价不同,因此需要明确"分析的是哪种输入"。
| 分析对象 | 定义 | 用途 | 局限 |
|---|---|---|---|
| 最好情况 | 使代价最小的输入下的代价 | 说明性能下限,判断是否存在廉价路径 | 几乎不反映真实表现,不能作为选型依据 |
| 最坏情况 | 使代价最大的输入下的代价 | 给出性能保证,是延迟上限与容量规划的依据 | 可能过度悲观,与实际分布相差很远 |
| 平均情况 | 在输入分布假设下代价的期望 | 描述典型表现 | 结论依赖于分布假设是否成立 |
| 摊还 | 一串操作序列的总代价均摊到每次操作 | 估计长期运行的平均成本 | 不保证单次操作的延迟上界 |
最好与最坏。 线性查找在首位命中时为 O(1),在末位或不存在时为 O(n)。工程上关注的是最坏情况,因为它决定了服务的最差响应时间与超时设置;只有最坏情况的界才能保证"任何输入都不会超过该代价"。
平均情况的分析前提。 平均代价是对输入分布求期望,因此必须显式声明分布假设。常见的三类假设:
- 等概率假设。线性查找中目标元素出现在每个位置的概率相同,平均比较次数为 (n+1)/2,仍是 O(n)。若实际访问存在热点(少数元素被反复查询),等概率假设不成立,把热点元素前移可显著降低实际代价。
- 随机输入假设。快速排序在随机排列下平均复杂度为 O(n log n)。该结论依赖输入顺序与枢轴选择无关;若输入已近乎有序且固定选取首元素为枢轴,每次划分极不平衡,退化为 O(n²),这正是最坏输入被构造的方式。
- 哈希均匀假设。哈希表平均 O(1) 的结论依赖哈希值在桶间近似均匀分布。若哈希函数对某类键退化(大量键的低位相同),或键由外部可控(哈希碰撞攻击),平均假设被破坏,单次查找退化到 O(n)。
由此得到一条实践结论:平均情况的结论必须与分布假设一起给出,并在假设可能不成立时用最坏情况的界兜底。哈希容器在链表长度达到阈值后转为红黑树,正是为均匀假设失效准备的兜底,见 Java 集合框架实现原理 的链表与红黑树转换阈值一节。
摊还分析。 摊还分析不依赖输入分布,是对操作序列本身性质的确定性结论。它回答"连续执行 n 次操作的总代价是多少,均摊到每次是多少"。三种方法:
- 聚合法。先求 n 次操作的总代价上界 T(n),再除以 n 得到摊还代价。动态数组的例子:容量按倍数增长时,n 次追加引发的元素搬移总量不超过 2n(几何级数之和),总代价 O(n),摊还每次 O(1)。该方法最直观,适合结构简单的场景;动态数组的扩容倍数选择与均摊结论见 栈与队列 中数组扩容与均摊代价一节。
- 记账法。为每类操作设定摊还代价(相当于收费),并允许把余额存入"信用"账户,供后续的昂贵操作支取。要求任意前缀操作序列中信用余额始终非负。动态数组的例子:每次追加收取 3 个单位,1 个单位用于当前的写入,2 个单位存储在该元素上;扩容搬移某元素时用其存储的 2 个单位支付搬移成本,任何时刻余额都不为负,因此摊还代价为常数。
- 势能法。定义势函数 Φ,把结构的"潜在未支付代价"映射为非负实数,摊还代价定义为"实际代价 + ΔΦ"。总摊还代价为总实际代价加上首末势能差,只要 Φ 非负且 Φ₀ = 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) | 见下方说明 |
主定理的适用边界。 主定理不覆盖所有递归式,以下情况需要退回到递归树或代入法:
- 落在情形之间的空隙。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)。
- 子问题规模不成等比。T(n) = T(n−1) + n 的缩减方式是相减而非相除,主定理不适用;用递归树逐层展开得 n + (n−1) + … + 1 = Θ(n²),对应快速排序的最坏情况与选择排序。
- 子问题规模不等。T(n) = T(n/3) + T(2n/3) + n 中两个子问题比例不同,需用递归树逐层求和:每层总代价为 n,最短路径深度 log₃n、最长路径深度 log₃␣₂ n,故总代价 Θ(n log n)。该递归式对应随机化快速排序的平均情形。
- 参数不是常数。a、b 依赖 n(如 T(n) = n·T(n/2) + n)时,主定理的前提不成立。
- 非多项式形态。出现 √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 吸收)。代入法的两个用途:
- 验证递归树或主定理得到的结论。
- 处理主定理不适用、递归树不易估计的递归式;上界与下界的猜测需要分别证明。
常见递归结构的复杂度结论。
| 结构 | 递归式 | 复杂度 | 说明 |
|---|---|---|---|
| 二分查找 | 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²) 更能反映真实代价。
判断标准是"输出规模是否可能远小于最坏情况"。若是,用输出规模表达复杂度更有意义,也更能指导选型。
空间与时间的换算。
- 预计算与缓存(记忆化):把重复计算的子问题结果存起来,时间从指数级降到多项式级,代价是 O(n) 的空间。这是动态规划的基本手段。
- 滚动数组:当状态转移只依赖前若干行的状态时,可以把 O(n²) 的表格压缩为 O(n) 甚至 O(1),用状态覆盖的顺序保证正确性。
- 空间换时间:建立索引、预排序、构造哈希表,把多次线性查找降为常数或对数查找。
- 时间换空间:流式处理、分批读取、不落缓存,用重复计算或重复 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)
结论有两个要点:
- 它是对"只通过元素间比较获取顺序信息"这一类算法的下界。归并排序与堆排序达到该下界,因此在这一类中已是最优,不存在量级上的改进空间;优化只能落在常数因子与缓存行为上。
- 绕过该下界必须改变前提。计数排序、基数排序、桶排序利用了键的取值结构(整数范围、位宽、可分桶),不依赖比较,因此可达到 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 分析方法实践
从代码推导复杂度的步骤。
- 确定 n 的口径。明确哪些输入量会影响执行次数:一个集合的长度、两个集合的长度、字符串长度、树的节点数、图的顶点数与边数。多个独立输入量必须分别设变量,不可合并为一个 n。
- 定位基本操作。找出执行最频繁的那一类语句(比较、赋值、数组访问、函数调用),以它为单位计数。基本操作的选择只影响常数因子,不影响量级结论。
- 逐层相乘。对每层循环,确定该层的迭代次数;嵌套循环的总次数为各层次数之积。注意迭代次数可能依赖外层变量,如内层为 i 到 n,此时内层次数为 n − i。
- 递归部分写递归式。递归调用的次数为 a,子问题规模为 n/b,其余工作为 f(n),写成 T(n) = a·T(n/b) + f(n),再按 2.4 的方法求解。
- 把库调用展开。任何库函数都对应一段实现,必须按其实现的复杂度计入(见下文)。
- 相加取最高阶,去掉常数与低阶项。多个顺序执行的片段代价相加,保留增长最快的项;乘号前的常数系数一律省略。
循环嵌套的推导。
// 单层循环: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)。需要注意三点:
- 摊还不约束单次延迟。触发扩容的那一次追加是 O(n),在延迟敏感的路径上应通过预设容量消除扩容(见 Java 集合框架实现原理)。
- 扩容倍数影响总搬移量。倍数越大,总搬移量越小,但空间浪费与内存峰值越大。1.5 倍是总搬移量与空间利用率之间的折中。
- 扩容易造成内存峰值。旧数组与新数组同时存在,峰值可达 2.5 倍数组容量。这是"大数据量必须预设容量"的主要原因,其代价不止于搬移指令。
哈希表的扩容。 负载因子达到阈值时容量翻倍并重新分布元素。单次扩容为 O(n),随元素数增长的总工作量同样摊还为 O(1)。要点:
- 扩容的判定依据是"元素数 / 容量",因此需要的初始容量应按
元素数 / 负载因子向上取整到 2 的幂计算。 - 扩容除时间开销外还带来内存峰值与计数重算,批量写入前预设容量可同时消除两者。
- 该摊还结论建立在哈希分布良好的前提上。分布退化时(大量键冲突)单次操作退化,摊还结论也随之失效。这是摊还分析依赖结构不变量的例子:摊还 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 集合框架实现原理。
避免过早优化与必须优化时的判断依据。 优化的顺序应当是先正确、再清晰、最后依据测量结果优化,原因有三:
- 复杂度分析能指出候选,但不能给出实际收益。在未测量的情况下按量级猜测优化点,容易优化了不占耗时的路径。
- 优化通常以提高复杂度(代码结构与认知成本)为代价,若收益不可测,则净收益为负。
- 简化实现本身就是一种优化:更少的分配、更少的间接调用、更少的缓存失效。
需要优化的判断依据(满足其中一项即可着手):
- 端到端占比可观:该路径在整体耗时中的占比可以通过测量确定,占比偏低时优化收益被稀释。
- 规模会增长:当前规模下可接受,但数据量或调用量会随业务增长;此时应优先做量级级别的改进。
- 存在隐藏的量级问题:循环内含线性操作、嵌套遍历、重复构造集合或索引。
- 资源约束明确:内存配额、GC 停顿时间、栈深度、连接数等出现实际限制。
- 有历史数据可比:存在基线可供对比,改动效果可验证,方法见 linux: 压测与性能基线。
优化的优先顺序,从高到低:
- 换算法量级:从 O(n²) 降到 O(n log n) 或 O(n),收益随规模扩大。
- 消除隐藏的线性操作:把循环内的
contains、字符串拼接、排序、集合构造提到循环外或换用常数级结构。 - 换数据结构:在同一量级内选择常数更小、缓存局部性更好的实现。
- 减少分配与回收:复用对象、预设容量、避免装箱。
- 常数级调优:减少函数调用、合并循环、调整判断顺序。
前两项属于量级层面,随规模增长收益扩大,应在规模可能增长时优先执行;后三项收益固定,在规模稳定且已测量确认热点后才值得投入。
3.4 实测方法
复杂度分析的结论需要在目标规模下验证,验证方式取决于观测对象。
测量思路与干扰控制。
- 固定条件:同一硬件、同一数据分布、同一版本、同一时段,一次只改一个变量。
- 排除干扰:关闭或隔离构建、索引、监控采集、其他基准进程;固定 CPU 频率策略并把频率作为结论的附带信息记录。
- 明确预热:让运行时状态(即时编译层级、类加载、缓存)进入稳态后再采集数据。
- 覆盖规模区间:至少取三个规模点,观察耗时随规模变化的曲线形态,而不是比较单点数值。
- 覆盖数据分布:至少包含随机与最坏两类输入,随机数据会掩盖分支预测与缓存局部性的差异。
- 多轮取稳态值:每档参数多轮测量,以中位数或稳定区间作为结论。
- 同时记录资源用量:时间与内存分配量一起报告,两者趋势不一致时必须解释差异来源。
基准与压测的分工。
| 方法 | 观测对象 | 回答的问题 | 结论边界 |
|---|---|---|---|
| 复杂度分析 | 算法的增长量级 | 规模增长后哪一方占优 | 量级层面的趋势,不含常数 |
| 微基准 | 方法或代码路径 | 同一量级下哪种实现局部成本更低 | 该版本、该规模下的相对关系 |
| 系统压测 | 完整服务与主机资源 | 能承载多少、延迟分位是多少 | 该环境与配置下的容量边界 |
| 线上观测 | 真实流量 | 变更后实际表现是否改善 | 当前数据分布下的实际结果 |
微基准的具体设计(预热与测量轮次分离、黑洞消费结果、分叉隔离、参数化展开规模、结果判读)见 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,不存在已知多项式精确算法 | 识别问题类别,转向精确算法加时间上限、近似算法或启发式 |
排查顺序。 出现"耗时随数据量增长异常"时的检查顺序:
- 确认规模增长与耗时的关系形态:线性、线性对数,还是平方级以上。平方特征通常指向嵌套遍历或循环内的线性调用。
- 检查循环体内是否有库调用、字符串拼接、集合构造、排序或正则匹配。
- 检查是否存在重复计算:同一数据在多处被反复遍历、反复解析、反复建立索引。
- 检查内存分配:是否有大对象、大数组、无上限容器;内存峰值是否触发额外回收。
- 检查最坏输入:是否存在排序退化的输入、哈希冲突集中的键、递归深度异常的树形。
- 检查数据的实际规模与分布是否与分析时的假设一致。
- 上述检查无结论时,用采样与转储定位实际热点,而不是继续按代码阅读推测。
3.6 检查清单:代码评审中的复杂度关注点
循环与嵌套。
- 是否存在两层及以上对同一集合的完整遍历;能否改为单次遍历配合哈希索引。
- 循环体内是否调用了含线性扫描的方法(
contains、indexOf、remove(Object)、字符串拼接、正则匹配)。 - 循环体内是否执行排序、去重、建立集合或索引;这些操作能否提到循环外。
- 循环的步长是否为倍增或减半(对数级),是否被误读为线性。
集合与数据结构。
- 容器的选择是否与访问模式匹配:按位置访问用数组、按键访问用哈希、需要顺序用平衡树、需要最值用堆。
- 数据量大时是否预设容量,以消除扩容的时间开销与内存峰值。
- 是否存在把列表当作集合使用(用
contains做去重)的写法。 - 是否存在对链表的按下标访问,形成隐式的平方级遍历。
- 键对象的
equals与hashCode是否一致且稳定,避免哈希退化与元素失联。
递归与分治。
- 递归深度是否与数据规模线性相关,最坏深度是否会触发栈溢出。
- 是否存在重复子问题;能否改为记忆化或自底向下的动态规划。
- 递归式属于哪一类,是否落在主定理不适用的区间。
- 归并类操作是否在每层复制了整份数据,能否改为原地合并或多个指针。
排序与去重。
- 是否在循环内排序;能否一次排序后复用。
- 去重是否使用哈希集合而非嵌套遍历。
- 是否对已排序数据重复排序;能否复用排序结果。
- 排序的键提取是否在比较器中重复计算;能否预先提取并缓存。
空间与资源。
- 是否一次性把全部数据载入内存;能否改为分批或流式处理。
- 是否存在与输入规模同阶的大数组或多份副本(含扩容峰值)。
- 大对象是否在长生命周期结构中累积,是否设置了容量上限与淘汰策略。
- 是否存在只使用一次的中间集合,能否直接消费数据源。
- 递归或缓存所占空间是否计入结论;是否已说明是原地算法。
结论与文档。
- 复杂度结论是否说明了分析对象(最好、最坏、平均、摊还)与 n 的口径。
- 平均情况的结论是否与分布假设一起给出。
- 已知的最坏输入是否被记录;是否有兜底措施。
- 性能结论是否带测量条件(规模、数据分布、版本、硬件),是否避免无条件的最优性表述。
四、总结
定位。 复杂度分析度量的是代价随输入规模变化的增长速度,用于在规模增长后仍能成立的比较。它给出趋势与量级,不给出耗时数值;用于筛选候选与判断可行性,不用于容量与延迟承诺。定量结论由实测给出。
记号。 大 O、大 Ω、大 Θ、小 o 分别表示上界、下界、紧界与严格低阶。上界与紧界的区分决定了结论的信息量:宽松的上界在形式上成立但无指导意义。大 O 是增长上界的记号,不是"最坏情况"的同义词;分析对象与渐近记号是两个正交维度。
量级。 对数、线性、线性对数、平方、指数、阶乘之间的差距随规模扩大而急剧拉开。对数级几乎对规模不敏感,平方级在 10⁴ 规模已接近一秒,指数级在 30 以内用尽预算。n 较小时常数因子主导,此时简化实现常优于复杂实现;量级决定的是可行性边界。
分析对象。 最坏情况用于给出性能保证,平均情况需显式声明分布假设,摊还给出操作序列的长期平均且不约束单次延迟。摊还的三种方法(聚合法、记账法、势能法)结论一致,用途各异;摊还结论依赖结构不变量。
递归式。 递归树通用且直观,主定理在三种情形下给出快捷结论,落入情形之间空隙或子问题规模不成等比时需要退回归纳与展开。二分、归并、快排、树遍历、朴素递归的复杂度均可由递归式直接得到。递归深度同时决定了栈空间与栈溢出的风险。
空间。 空间复杂度的口径是输入之外的额外空间;原地算法、递归栈、输出敏感型复杂度、时空换算(预计算、滚动数组、索引与流式处理)是四个需要分别确认的维度。空间代价常通过分配与回收间接影响时间。
理论的边界。 比较排序的 Ω(n log n) 是问题固有的下界,绕过它必须改变前提;P 与 NP 的区分决定了面对问题时应当追求精确解、近似解还是启发式。近似算法有可证明的界,启发式只有经验表现,两者的结论都需注明"可行解而非最优解"。
理论与实测的差异。 常数因子、内存层次与缓存命中、分支预测、运行时开销、数据分布、外部成本与空间代价共同造成差异。数组与链表的线性遍历、小规模排序、哈希表与平衡树的取舍都说明"量级更优"不等于"实际更快"。量级不同且规模足够大时可直接依据分析决策;量级相同或落在交叉点附近时必须实测。
实现层面的落点。 推导流程为确定 n 的口径、定位基本操作、逐层相乘、写出递归式、展开库调用、约简常数与低阶项。隐藏循环是最常见的量级误判来源,其形态是循环体内调用线性复杂度的库函数。优化按"换算法量级、消除隐藏线性操作、换数据结构、减少分配、常数调优"的顺序推进,前两项随规模增长收益扩大。测量需固定条件、明确预热、覆盖规模与分布、同时记录时间与分配量,结论必须带限定条件。
复杂度分析与实测是两种互补的方法:前者回答"数据量增长后是否仍然可行",后者回答"在当前条件下哪一个实际更快"。把量级结论当作性能数值使用,与在两个量级相同的实现之间凭直觉取舍,是同一类错误的两面。