企业官网建设流程全解析

学《算法导论》的人，十有八九会在第2章第2.2节这里卡一下。这一节叫“分析算法”，教材用插入排序当靶子，把运行时间怎么算、最好最坏情况怎么区分、渐进记号怎么用，一口气全讲完了。问题是教材写得很简练，很多推导中间步骤要自己补，课后习题也没有详细展开。这篇文章就把2.2节的完整过程拆开揉碎，陪你把算法跑一遍、把那张“成本×次数”的表格推一遍、把四道习题逐个解一遍，顺便讲讲我答疑时反复见到的几个理解误区。无论你是刚接触算法的新手，还是准备面试、考研复习时想把这章彻底弄明白，这篇都值得花半小时认真跟下来。

1. 插入排序的过程：先把“它在干什么”彻底搞清楚

1.1 摸牌式排序：从第二张牌开始往前插

插入排序的直观逻辑，用扑克牌来理解最舒服。你左手拿一手已经按大小排好的牌，右手摸一张新牌，然后从右往左比较，找到合适的位置插进去。代码里做的事情完全一样：把数组分成左半边“已排序区”和右半边“未排序区”，每次从右半区取第一个元素，向前插到正确位置。

很多初学者看伪代码觉得简单，但一细看就懵：“为什么从 j = 2 开始？”因为单个元素天然有序，A[1] 自己就是长度为1的已排序区，所以第一个要处理的元素是 A[2]。整个过程的循环不变量是：每一轮迭代开始时，A[1..j-1] 已经是排好序的，而且里面的元素就是原数组的前 j-1 个元素。

伪代码可以写成这样（这里按教材习惯，数组索引从1开始）：

INSERTION-SORT(A) 1 for j = 2 to A.length 2 key = A[j] 3 // 把 A[j] 插入到已排序序列 A[1..j-1] 中 4 i = j - 1 5 while i > 0 and A[i] > key 6 A[i + 1] = A[i] 7 i = i - 1 8 A[i + 1] = key

第5行的两个条件顺序也经常被忽略：要先判断 i > 0，再去访问 A[i]。否则当 i 减到0时，A[0] 是一个不存在的元素，这就越界了。这个细节看起来小，却是我见过新手手写代码时最常翻车的地方。

1.2 用一个小例子手跑一遍

拿 A = [5, 2, 4, 6, 1, 3] 来模拟，记住左边中括号里是已排序区，右边是未处理区：

• j = 2，key = 2：把5往后移一位，数组变成 [2, 5, 4, 6, 1, 3]
• j = 3，key = 4：5 > 4 后移，2 < 4 停下，插入，得到 [2, 4, 5, 6, 1, 3]
• j = 4，key = 6：5 < 6，原地不动，数组保持 [2, 4, 5, 6, 1, 3]
• j = 5，key = 1：一路和6、5、4、2比较，全部后移，1回到开头，得到 [1, 2, 4, 5, 6, 3]
• j = 6，key = 3：6、5、4后移，2 < 3 停下，得到 [1, 2, 3, 4, 5, 6]

跑完这一遍，你会注意到一个核心事实：插入排序每一轮做的“比较”和“移动”次数，取决于 key 前面的元素有多少比它大。也就是说，运行时间和输入数据的初始顺序强相关。这正是2.2节要分析的最好情况、最坏情况、平均情况的起点。

1.3 循环不变式为什么是“证明正确性”的钥匙

光靠跑几个例子，不能证明一个算法对所有输入都正确，所以教材引入了循环不变式。这套论证方式很像数学归纳法：初始化（还没进入循环时不变式成立）、保持（如果某轮迭代前成立，那么本轮结束后也成立）、终止（循环结束后不变式给出了有用的性质）。

对应到插入排序：初始化时 j = 2，A[1..1] 只有一个元素，显然有序；保持阶段，内层 while 把所有大于 key 的元素右移，最后把 key 放进空出来的位置，A[1..j] 重新有序；终止时 j = n + 1，于是 A[1..n] 全部有序，排序完成。

我在带人复习时经常强调：循环不变式不只是写给老师看的证明，它能帮你精确判断算法在什么条件下是对的、在什么边界下会崩。等你在第2节做运行时间分析时会发现，正因为有了这个正确性基础，我们计算出来的运行时间才有意义。

2. 运行时间怎么算：那张“成本×次数”的表格

2.1 RAM模型：算法分析的地基

为什么教材可以放心地说“第6行赋值需要常数时间”？因为它默认了一个理想计算模型——RAM（随机访问机）模型。在这个模型里，一条基本指令（加、减、比较、赋值、跳转）耗费常数时间，访问内存也耗费常数时间，不考虑缓存、流水线、并行这些真实硬件因素。

这个抽象非常重要。真实机器的每条指令耗时不同，但算法分析关心的不是“这台机器上跑3毫秒，那台上跑8毫秒”，而是“运行时间随输入规模增长的趋势”。所以在RAM模型下，我们把每条语句的成本写成常数 c_i，不急着给它具体数值，反正最后都会被渐进记号吸收掉。

2.2 重头戏：每一行语句的执行次数表格

现在把插入排序逐行拆开，统计每一行语句需要执行多少次。表格里的 t_j 表示第 j 轮外层循环中，while 循环体实际执行的次数。它是一个变量，因为这个次数取决于输入数据：

这里有几个最容易写错的点：

• 第1行 for 循环不是只执行 n - 1 次。它要先执行一次初始化（j = 2），然后每轮判断一次“j ≤ A.length”，判断成功才进入循环体，最后 j 变成 n + 1 时还要再做一次判断来退出。所以一共是 n 次判断，写 n。
• 第3行是注释，不占用实际运行时间，成本记为0。
• 第5行 while 语句每轮外层循环要判断一次，但进入循环体的次数才是 t_j。划分成本时，判断条件本身算第5行成本，循环体里的第6、7行各执行 t_j - 1 次，因为最后一次条件不满足，不会进入。
• 第8行把 key 写回空位，每一轮外层循环恰好执行1次，所以是 n - 1 次。

把这张表加起来，总运行时间就是：

T(n) = c1·n + c2·(n-1) + c4·(n-1) + c5·Σt_j + c6·Σ(t_j-1) + c7·Σ(t_j-1) + c8·(n-1)

这里的“Σ”都是从 j = 2 到 n 求和。不要漏掉任何一个 c_i，因为后面最坏情况的二次项系数，就是这些常数组合出来的。

2.3 从 Σ 求和到多项式：数学这一步不能跳

现在最关键的步骤来了：把求和式展开成关于 n 的多项式。这里要记住两条常用求和公式：

Σ j = n(n+1)/2 - 1（j 从2到 n） Σ (j - 1) = n(n-1)/2（j 从2到 n）

在最坏情况下，每个 t_j 都取到最大值 j，也就是每次插入都要从最右边一路比到最左边。代入后：

T(n) = (c5/2 + c6/2 + c7/2)·n² + (c1 + c2 + c4 + c8 + c5/2 - c6/2 - c7/2)·n - c5

这是一个关于 n 的二次函数。二次项系数显然大于0，所以当 n 足够大时，n² 项统治一切。这个从“求和”到“二次多项式”的推导过程，就是2.2节核心中的核心，后面所有的渐进结论都从这里长出来。

3. 最好情况、最坏情况，和那个重要的“增长率”

3.1 最好情况：输入已经排好序

最好情况发生在数组已经从小到大排好时。这时每个 key 一进 while，立刻发现 A[i] ≤ key，不需要移动元素，也就是每个 t_j = 1。代入和的式子：

Σt_j = Σ1 = n - 1 Σ(t_j - 1) = 0

于是 T(n) = (c1 + c2 + c4 + c5 + c8)·n - (c2 + c4 + c5 + c8)，这是一个关于 n 的线性函数。

理解最好情况别只当作“成绩单上的光环”，它有实际用途。比如很多现实数据局部有序，插入排序在近似有序的数据上会表现得非常好，这也是为什么一些混合排序算法会选择小规模或近排序数据时切到插入排序。但要注意：最好情况是线性，不代表平局情况也是线性。

3.2 最坏情况：输入完全反序

最坏情况发生在数组刚好从大到小排好时。每个 key 都要和前面所有已排序元素比较一遍并全部右移，即 t_j = j。于是：

Σt_j = Σj = n(n+1)/2 - 1 Σ(t_j - 1) = n(n-1)/2

代入后的运行时间是一个二次多项式。重点来了：当 n 翻倍时，n² 增长为原来的4倍，线性项 n 的贡献在它面前可以忽略。于是教材引出了 Θ 记号：丢弃低阶项和常数系数后，插入排序最坏情况运行时间是 Θ(n²)。

为什么能丢弃常数系数？因为 c_i 只在具体机器上才有确定数值，换台机器数值就变了。算法分析要的比较是“趋势”，不是“绝对值”。一个运行时间 100n² 的算法，和一个 n² 的算法，在渐进意义下是一类，但在现实中差100倍，这个细节我会在最后一节展开说。

3.3 平均情况也要算一算

平均情况假设元素取值不是那么极端，每个 key 大约会与前面一半的元素比较再停下。也就是说 t_j ≈ j/2，代入后得到的仍然是一个二次函数，渐进还是 Θ(n²)。

所以平均情况的常数系数大约是最坏情况的一半，但渐进阶没有变化。这件事常被一句话带过，但它解释了为什么插入排序在大规模随机数据上没有竞争力：不管你是不是平均，复杂度都死死卡在 n²。这也为后面引入归并排序那种 O(n log n) 的算法埋下伏笔。增长率这个概念，就是用来横向比较不同算法的核心尺子。

4. 2.2节习题逐题解析：从会看到会做

4.1 习题2.2-1：用 Θ 记号表示函数

这道题给的是：

n³/1000 - 100n² - 100n + 3

问你它的 Θ 表示是什么。答案很简单：Θ(n³)。原理是：当 n 足够大时，n³ 的增长速度碾压 n² 和 n，而常数 1/1000 只是一个系数，按 Θ 记号的规则被丢弃。

做题时有个实用技巧：先把所有低阶项划掉，再把所有系数变成1，看剩下哪个最高阶项。多项式只看最高次幂，这是 Θ 记号最基础也最常用的规则。别把“最高阶项”和“系数最大的项”搞混，比如 100n² 和 n³ 比，即使 n=1 时 100n² 更大，但从 n ≥ 100 开始 n³ 就永远领先，而且差距只会越拉越大。

4.2 习题2.2-2：选择排序的伪代码与分析

这道题要求写出选择排序的伪代码、循环不变式，并用 Θ 记号给出最好和最坏情况运行时间。伪代码如下：

SELECTION-SORT(A) 1 for i = 1 to A.length - 1 2 min = i 3 for j = i + 1 to A.length 4 if A[j] < A[min] 5 min = j 6 swap A[i] with A[min]

循环不变式：每轮外层迭代开始时，子数组 A[1..i-1] 已经由原数组中最小的 i-1 个元素组成，且处于最终位置。

为什么外层只需要到 n - 1？因为当前 n - 1 个元素都已经到位后，剩下的最后一个元素自然就是最大值，不需要再处理。

运行时间分析是这道题的考点。内层循环的比较次数是固定的：

Σ(i 从1到 n-1) (n - i) = n(n-1)/2 = Θ(n²)

不管输入是正序、反序还是乱序，每次都要扫一遍剩下的未排序部分，所以选择排序的最好情况也是 Θ(n²)，这一点和插入排序完全不同。但交换次数是 n - 1，是 Θ(n)，所以如果要比较的元素很大而交换成本很高，选择排序反而有优势。

4.3 习题2.2-3：线性查找的平均与最坏情况

线性查找就是从头到尾逐个扫描：

LINEAR-SEARCH(A, v) 1 for i = 1 to A.length 2 if A[i] == v 3 return i 4 return NIL

最坏情况：要查找的元素在最后一个位置，或者根本不在数组里，总共检查 n 次，运行时间 Θ(n)。

平均情况：假设查找值等可能地出现在数组的任意位置，那么检查次数的期望是：

E = (1/n)·(1 + 2 + … + n) = (n+1)/2 = Θ(n)

很多同学在这里会写“平均情况要检查 n/2 次”，这个直觉方向对，但严谨写法是 (n+1)/2。两者渐进都是 Θ(n)，可如果真的去推导期望，一定要写出这个求和过程，考试和面试都爱看这一步。

4.4 习题2.2-4：如何让算法拥有良好的最好情况运行时间

这道题是个开放题，答案是：可以先检查输入是否已经满足目标状态，如果满足就直接返回。比如在插入排序前先跑一遍扫描，如果发现数组已经有序，就直接结束：

IMPROVED-INSERTION-SORT(A) 1 sorted = true 2 for i = 2 to A.length 3 if A[i - 1] > A[i] 4 sorted = false 5 break 6 if sorted 7 return A 8 INSERTION-SORT(A) // 继续原算法

这样一来，当输入恰好有序时，最好情况运行时间是 Θ(n) 而不是原来的 Θ(n)，因为额外检查只花线性时间。但最坏情况下，这个检查也帮不上忙，整个算法仍然是 Θ(n²)。题目想让你意识到：优化“最好情况”很容易，难度在于如何优化“最坏情况”或“平均情况”。这个思路在后面的随机化算法里还会反复出现。

5. 实操心得与常见理解误区

5.1 别把循环不变式和数学归纳法对立起来

很多教材提到循环不变式时都会附一句“类似数学归纳法”。但实际学习时，有人过度纠结两者差异，反而绕远路。我建议直接把它们当成同一件事：初始化 = 归纳基础，保持 = 归纳步，终止 = 结论成立的条件。

真正要训练的是“保持”这一段的写法，不是背定义，而是去代码里找证据。以插入排序为例，要保持 A[1..j] 有序，你得说清楚 while 循环右移了哪些元素、key 为什么落在那个位置。不会写这一步，考试时循环不变式题基本拿不到分。

5.2 手写插入排序最容易踩的三个坑

第一个坑是数组越界。前面说过，i = i - 1 可能减到0，判断条件必须先检查 i > 0。第二个坑是忘记 key 变量保存原始值。如果直接拿 A[j] 去参与交换，一旦 A[j-1] 覆盖上来，原来的值就丢了。第三个坑是把比较条件和移动条件混在一起：插入排序找的是“比 key 大的元素”，不是“比 key 大的元素且同时满足某种额外条件”，写复杂了就失去它本来的简洁。

5.3 分析变体时要抓住比较次数和移动次数

我见过不少人用二分查找替换插入排序里的线性比较部分，形成“二分插入排序”。这时比较次数会从 O(n²) 降到 O(n log n)，但移动次数依然要移动元素，最坏情况整体还是 Θ(n²)。原因是移动次数是数组元素搬运成本，二分只在“找位置”这一步节省了时间。

这一类变体分析，核心是分清“比较”和“移动”两类操作，分别计算再合起来看。你如果在面试中遇见类似问题，建议直接把这两个计数器分开写，回答会清晰很多。

5.4 自测技巧：插桩统计比较次数

最后分享一个我帮人验证理解时常用的方法：在插入排序的 while 条件里放一个计数器，每次执行循环体也放一个计数器，把两个数字打印出来。然后用三种输入测试：正序、反序、乱序。你会发现正序时第一条计数等于 n-1，反序时等于 n(n-1)/2，乱序时约等于 n²/4。把这些数与前面推导的公式一对上，你就真正掌握2.2节了。很多人说“看懂了但不会做题”，往往就是少了这个亲手验证的过程。

第2.2节篇幅不大，但它把“算法正确性证明”和“运行时间分析”两个技能一起练了。插入排序本身不难，难的是把那张表格看懂、把求和推下来、把三种情况的含义想明白。把这篇文章里所有式子自己动手推导一遍，再去做后面的归并排序分析，你会顺畅很多。