1.3 最好、最坏与平均：三个不同的答案
学习目标：学完本节，你能
- 区分最好、最坏、平均三种情况，并说明各自的现实含义；
- 判断工程中该依据哪一种情况做决策；
- 用 $O$、$\Omega$、$\Theta$ 三个符号准确描述一个算法的代价。
先修：1.2（大 O 记法）。 固定术语：最好情况、最坏情况、平均情况。 环境与版本：.NET 8 / C# 12。 预计阅读：22 分钟。
一、直觉：上一节留下的矛盾
上一节的练习 1.1.6 留了一个矛盾：同一段"查重"代码，
- 数据有重复时，可能第一对就命中，几毫秒返回；
- 数据没有重复时，必须把所有 $\frac{n(n-1)}{2}$ 对都检查完才能确定，跑满全程。
那么这段代码到底是 $O(1)$ 还是 $O(n^2)$？
答案是：都是。 但这样说不清话，所以大 O 必须配一个前缀 —— "最坏情况下是 $O(n^2)$"。
用找钥匙打个比方：
| 情况 | 场景 | 找了几处 |
|---|---|---|
| 最好 | 一摸外套口袋就找到了 | 1 处 |
| 最坏 | 翻遍全屋、连冰箱都看了，还是没有 | 全部 |
| 平均 | 通常翻三四个地方能找到 | 3～4 处 |
三个答案都对，但它们回答的是不同的问题。关键在于：你要用哪一个来做决策。
二、形式化：三种情况与三个符号
| 名称 | 定义 | 用途 |
|---|---|---|
| 最好情况（Best Case） | 所有合法输入中代价最小的那次 | 说明算法最好能多快，通常没什么工程价值 |
| 最坏情况（Worst Case） | 所有合法输入中代价最大的那次 | 工程决策的依据：SLA、超时、容量规划 |
| 平均情况（Average Case） | 按输入分布假设加权平均 | 说明日常表现，但依赖假设是否成立 |
配套三个符号：
| 符号 | 含义 | 白话 |
|---|---|---|
| $O(f(n))$ | 上界 | 不会比这个更慢 |
| $\Omega(f(n))$ | 下界 | 不会比这个更快 |
| $\Theta(f(n))$ | 紧确界 | 就是这个量级（上下界一致） |
举例：如果某算法最坏是 $n^2$、最好是 $n$、平均是 $n \log n$，可以写成：
$$T{\text{最好}}(n) = \Omega(n), \quad T{\text{平均}}(n) = \Theta(n \log n), \quad T_{\text{最坏}}(n) = O(n^2)$$
全书的默认约定：本书后面说"这个算法是 $O(f(n))$"时，若不特别说明，一律指最坏情况。这是行业惯例，也是工程上最有用的那个数。
为什么工程上看最坏情况？
- 承诺要按最坏来定。 你告诉用户"这个接口 200 毫秒返回"，用户就会按 200 毫秒设计他们的系统。偶尔快没有意义。
- 最坏输入是可以被制造出来的。 攻击者会专门构造让哈希表疯狂冲突、让快排退化的数据。这正是历史上真实发生过的攻击。
- 平均情况的假设经常不成立。 "平均是 $n/2$"的前提是目标值等概率出现在任何位置 —— 但现实中热点数据往往集中在开头，或者永远不存在。
但平均情况绝不是没用。 快速排序的最坏情况是 $O(n^2)$，可它依然是工程中使用最广的排序之一 —— 因为它的平均表现是 $O(n \log n)$，而随机数据下最坏情况几乎不会发生。这个权衡我们在 8.2 节会详细讨论。
三、实验：同一个算法，三个答案
新建控制台项目，粘贴以下代码：
// 本节同样用「数操作次数」而不是「测时间」，结论与机器无关。
// ---------- 线性查找：统计比较次数 ----------
static int LinearSearchComparisons(int[] data, int target)
{
int comparisons = 0;
for (int i = 0; i < data.Length; i++)
{
comparisons++;
if (data[i] == target)
return comparisons; // 找到就停，剩下的元素不用看了
}
return comparisons; // 找不到，必须比完全部 n 个
}
// ---------- 插入排序：统计比较次数 ----------
static long InsertionSortComparisons(int[] source)
{
int[] a = (int[])source.Clone();
long comparisons = 0;
for (int i = 1; i < a.Length; i++)
{
int key = a[i];
int j = i - 1;
while (j >= 0)
{
comparisons++; // 每轮循环先做一次 a[j] > key 的判断
if (a[j] <= key)
break; // 找到插入位置，停止
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
return comparisons;
}
const int N = 2_000;
var rng = new Random(42);
var sorted = new int[N];
for (int i = 0; i < N; i++) sorted[i] = i; // 已有序
var reversed = new int[N];
for (int i = 0; i < N; i++) reversed[i] = N - i; // 完全逆序
var random = new int[N];
for (int i = 0; i < N; i++) random[i] = rng.Next(0, N); // 随机
Console.WriteLine($"=== 线性查找的比较次数（n = {N}）===");
int[] probe = new int[N];
for (int i = 0; i < N; i++) probe[i] = i;
Console.WriteLine($" 目标在第 1 位 : {LinearSearchComparisons(probe, 0),6} 次");
Console.WriteLine($" 目标在正中间 : {LinearSearchComparisons(probe, N / 2),6} 次");
Console.WriteLine($" 目标在最后一位 : {LinearSearchComparisons(probe, N - 1),6} 次");
Console.WriteLine($" 目标不存在 : {LinearSearchComparisons(probe, -1),6} 次");
Console.WriteLine();
Console.WriteLine($"=== 插入排序的比较次数（n = {N}）===");
Console.WriteLine($" 已有序数组（最好）: {InsertionSortComparisons(sorted),10} 次");
Console.WriteLine($" 随机数组（平均） : {InsertionSortComparisons(random),10} 次");
Console.WriteLine($" 完全逆序（最坏） : {InsertionSortComparisons(reversed),10} 次");
Console.WriteLine();
Console.WriteLine("理论值对照：");
Console.WriteLine($" 最好 n-1 = {N - 1}");
Console.WriteLine($" 平均 n^2/4 = {(long)N * N / 4}");
Console.WriteLine($" 最坏 n(n-1)/2 = {(long)N * (N - 1) / 2}");
实测输出（.NET 8 Release）：
=== 线性查找的比较次数（n = 2000）===
目标在第 1 位 : 1 次
目标在正中间 : 1001 次
目标在最后一位 : 2000 次
目标不存在 : 2000 次
=== 插入排序的比较次数（n = 2000）===
已有序数组（最好）: 1999 次
随机数组（平均） : 1002338 次
完全逆序（最坏） : 1999000 次
理论值对照：
最好 n-1 = 1999
平均 n^2/4 = 1000000
最坏 n(n-1)/2 = 1999000
逐个对照：
| 情况 | 实测 | 理论 | 量级 |
|---|---|---|---|
| 线性查找 · 最好 | 1 次 | $1$ | $O(1)$ |
| 线性查找 · 平均 | 1001 次 | $\frac{n}{2}$ | $\Theta(n)$ |
| 线性查找 · 最坏 | 2000 次 | $n$ | $O(n)$ |
| 插入排序 · 最好 | 1,999 次 | $n-1$ | $\Omega(n)$ |
| 插入排序 · 平均 | 1,002,338 次 | $\frac{n^2}{4}$ ≈ 1,000,000 | $\Theta(n^2)$ |
| 插入排序 · 最坏 | 1,999,000 次 | $\frac{n(n-1)}{2}$ | $O(n^2)$ |
注意插入排序这一组：最好与最坏差了 1000 倍。
- 最好（数组本来就有序）：每个元素只需和左边比一次就发现位置对了，共 $n-1$ 次。
- 最坏（完全逆序）：每个元素都要一路比到最左边，共 $\frac{n(n-1)}{2}$ 次。
- 平均（随机）：每个元素平均要往回比一半，约 $\frac{n^2}{4}$ 次 —— 实测 1,002,338，与理论值 1,000,000 吻合得很好。
这个"最好情况"不是摆设。 插入排序在"数据近乎有序"时表现极好，这个性质让它成为很多工业级排序算法（比如 C# 的
Array.Sort）在小数组和近乎有序时的收尾选择。8.5 节会用到这一点。
四、练习
练习 1.3.1（判断） 下面三种说法，哪些是正确的？ (a) 一个算法最好是 $O(1)$，说明它在实际使用中很快。 (b) 一个算法最坏是 $O(n^2)$，说明它一定很差。 (c) $\Theta(n \log n)$ 比 $O(n^2)$ 提供了更多信息。
练习 1.3.2（算一算） 在长度为 $n$ 的有序数组中做二分查找，它的最好、最坏、平均比较次数分别大约是多少？
练习 1.3.3（工程判断） 你写了一个接口，其中有一段是对长度为 $n$ 的数组做线性查找。请分别说明： (a) 如果这个接口有 200 毫秒的响应承诺，你应该报告哪个复杂度？ (b) 如果这个数组是"用户最近访问的 20 个商品"，且查询的目标 90% 集中在最近访问的 3 个里，你会用哪个复杂度来评估？
练习 1.3.4（挑战·设计最坏输入） 6.2 节会讲哈希表的冲突解决。假设某哈希表的哈希函数是"把字符串所有字符的 ASCII 码相加，再对槽位数量取模"。请说明攻击者如何构造大量键，让这张哈希表的查找从 $O(1)$ 退化到 $O(n)$。
五、练习答案
1.3.1
- (a) 错。 最好情况只说明"存在一种输入能让它很快"，不代表你会遇到那种输入。工程上要看最坏和平均。典型反例：快速排序最好情况是 $O(n \log n)$，但如果数据已有序且每次都取第一个元素做基准，最坏是 $O(n^2)$。
- (b) 错。 要结合数据规模看。$n$ 恒为 20 的时候，$O(n^2)$ 只有 400 次操作，可能比 $O(n \log n)$ 的实现（常数大、要分配内存）还快。
- (c) 对。 $O(n^2)$ 只说了"不快于 $n^2$"，它可能其实是 $O(n)$ 甚至 $O(1)$ —— 上界不够紧。$\Theta(n \log n)$ 同时给出了上界和下界，信息更强。
1.3.2
- 最好：1 次 —— 第一次取中间元素就命中了。
- 最坏：约 $\log_2 n$ 次 —— 每次把搜索范围砍一半，直到范围为空才发现不存在。$n = 1000$ 时约 10 次。
- 平均：也约 $\log_2 n$ 次。
二分查找的特点：三种情况几乎一样。这是它极其可靠的原因 —— 不会因为数据分布不同而突然变慢。代价是它要求数组必须预先有序。
1.3.3
- (a) 应该报告最坏情况。200 毫秒是承诺给用户的，用户会据此设计他们的超时和重试策略。如果按平均的 $\frac{n}{2}$ 报，一旦遇到"目标在最后一位"或"目标不存在"的请求，就会超时违约。SLA 必须按最坏情况定。
- (b) 应该用平均情况来评估，但要明确写出假设。这里目标 90% 落在最近 3 个元素中，实际平均比较次数约为 $0.9 \times 2 + 0.1 \times 10 \approx 2.8$ 次，远好于 $\frac{n}{2}$。 但必须警惕：这个结论完全依赖于"90% 集中在最近 3 个"这个假设。一旦缓存失效、或者用户行为变化，这个假设就不成立了。用平均情况做决策时，一定要写清楚假设是什么、假设不成立时会怎样。
1.3.4 攻击者的目标是：让尽可能多的键，字符 ASCII 码之和对槽位数取模后落在同一个槽里。
做法：
- 先确定槽位数。 哈希表的槽位数通常是 2 的幂（16、32、64……），可以从响应时间或公开文档推断，也可以穷举试探。
- 构造同余的键。 槽位数是 $m$ 时，只要保证字符码之和对 $m$ 取模的结果相同，就会落入同一槽。最省事的做法是固定一个字符，另一个字符作等差变化：比如让所有键都由同一个字符重复组成，长度相同则和必然相同。
- 更简单：任意两个键，只要把某个字符的码值 $+m$ 或 $-m$，和就不变（前提是码值仍在合法字符范围内）。用
'A'（65）与'q'（113），差 48；若 $m = 16$，$48$ 是 $16$ 的倍数，二者可互换而和不变。
- 更简单：任意两个键，只要把某个字符的码值 $+m$ 或 $-m$，和就不变（前提是码值仍在合法字符范围内）。用
- 批量提交。 用成千上万个构造好的键填充哈希表，它们全部落进同一个槽。
结果：该槽位上的链表长度变成 $O(n)$，查找这个槽里的任意键都需要遍历整条链表 —— 查找退化为 $O(n)$，哈希表丧失了它全部的优势。
这正是"最坏情况真的会发生"的现实版本：它不是理论上的可能性，而是有人会主动去构造的。防御手段（随机化种子、改用 SipHash 等抗碰撞哈希、限制单槽链表长度）在 6.4 节讨论。
六、常见错误
| 误区 | 纠正 |
|---|---|
| 只报一个复杂度，不说哪种情况 | 说"$O(n^2)$"是不完整的。要说"最坏 $O(n^2)$，平均 $O(n \log n)$"。 |
| 用最好情况做承诺 | 最好情况只说明"存在一种输入很快"，不能用来给用户任何保证。 |
| 认为平均情况一定更真实 | 平均情况依赖输入分布假设。假设错了，结论就错了。用平均情况必须声明假设。 |
| 认为最坏情况可以忽略 | 攻击者会主动构造最坏输入。哈希碰撞攻击就是真实案例。 |
| 把 $O$ 和 $\Theta$ 混用 | $O$ 是上界（可能不紧），$\Theta$ 是紧确界。说"快排最坏是 $O(n^2)$"对，说"快排是 $\Theta(n^2)$"错。 |
七、本节总结
- 同一个算法在同一组数据规模下，可能有三个不同的答案：最好、最坏、平均。
- 三个符号：$O$ 是上界，$\Omega$ 是下界，$\Theta$ 是紧确界。
- 工程决策看最坏情况 —— SLA 承诺、超时设置、安全防御都基于它。
- 平均情况同样重要，但必须写清楚它依赖的假设；好假设让快排成为工业标准，坏假设让你在攻击面前毫无防备。
- 实测中插入排序的最好与最坏差了 1000 倍 —— 差距不是来自代码，而是来自输入本身。
下一节衔接：到这里我们一直只讨论"花多少时间"。但内存同样是有限资源：上一节练习 1.2.5 里用哈希表建索引、本节插入排序要 Clone 一个数组，都是拿空间换时间。下一节把空间这块账算清楚，并介绍一个每个 C# 程序员每天都在用、却很少意识到其精妙之处的机制 —— List<T> 的摊还扩容。
状态外显
{
"book": "数据结构与算法自学：从工程直觉到复杂度思维",
"section": "1.3",
"title": "最好、最坏与平均：三个不同的答案",
"covered": [
"三种情况的定义与工程含义",
"O / Ω / Θ 三个符号的区分",
"线性查找的三组比较次数",
"插入排序 n-1 / n^2/4 / n(n-1)/2 的实测验证",
"为何 SLA 必须按最坏情况定",
"哈希碰撞攻击的构造思路（作为最坏情况真实存在的例证）"
],
"unresolved": [
"快排的平均 O(n log n) 与最坏 O(n^2) 的取舍留到 8.2",
"插入排序在近乎有序数据上的工程价值留到 8.5",
"哈希碰撞的防御手段留到 6.4"
],
"canonical_terms": {
"最好情况": "所有合法输入中代价最小的那次",
"最坏情况": "所有合法输入中代价最大的那次，工程决策依据",
"平均情况": "按输入分布假设加权平均，依赖假设成立"
},
"symbols_units": {
"O(f(n))": "增长率上界，不会更慢",
"Ω(f(n))": "增长率下界，不会更快",
"Θ(f(n))": "紧确界，上下界一致"
},
"assumptions": [
"读者已掌握 1.2 的大 O 化简规则",
"读者理解插入排序的基本流程（3.4/7.1 会再完整实现一次）"
],
"word_count_actual": 1245,
"checks": [
"C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
"项目文件：99-tools/samples/Ch01/Sec13/",
"实测值与理论值逐项对照：1999/1999、1002338/1000000、1999000/1999000",
"练习答案含关键步骤，不只给结果",
"术语写法与 glossary.md 一致"
],
"next": "1.4 空间复杂度与时间-空间权衡"
}