Chapter 2 · Getting Started

按CLRS第四版第2章重建插入排序、循环不变式、RAM模型、最好/最坏与平均输入、分治设计、归并过程和T(n)=2T(n/2)+Theta(n)递推。

从“打牌时怎样把新牌插进手牌”开始

先预测：手中左侧牌已经有序，拿到一张新牌时，需要重新排序整手牌吗？不需要。只要从右向左跳过比新牌大的牌，把新牌插入留下的空位，就把一个有序前缀扩大一格。

Getting Started用这个简单算法建立全书反复使用的三种能力：写出精确过程、证明过程正确、计算过程成本。随后再从插入排序的增量设计转向归并排序的分治设计。

2.1 Insertion sort

把数组划分为已排序前缀和未处理后缀。外层第 $j$ 轮开始时，前缀A[0..j)已排序；保存A[j]为key，向右移动所有大于key的前缀元素。

void insertion_sort(std::vector<int>& a) {
    for (std::size_t j = 1; j < a.size(); ++j) {
        int key = a[j];
        std::size_t i = j;
        while (i > 0 && a[i - 1] > key) {
            a[i] = a[i - 1];
            --i;
        }
        a[i] = key;
    }
}

保存key之后，移动操作可以覆盖原位置；循环结束时i正是第一个不大于key的元素之后。条件使用>而非>=，让相等元素不跨越彼此。

用loop invariant证明

可写为：

每次外层迭代开始时，A[0..j)包含原数组前 $j$ 个元素，且按非降序排列。

Initialization：j=1前缀只有一个元素，自然有序且元素保持。
Maintenance：右移所有大于key的元素不会改变多重集；把key放入空位后，新前缀有序。
Termination：循环在j=n结束，不变式此时描述整个数组，得到排序后置条件。

若不变式只写“前缀有序”却不写“包含原前缀相同元素”，仍可能允许算法删除或改值。证明命题必须足以推出完整contract。

2.2 Analyzing algorithms

Analyzing algorithms先固定实现技术和计算模型。输入规模为 $n$ ，运行时间是每条语句成本乘执行次数之和。精确常数依赖机器，但增长率能跨机器比较。

RAM模型与word假设

假设一个word能容纳数组索引与问题中的普通整数。它不允许把任意长整数乘法或整块磁盘读取悄悄算作一步。

若输入整数有 $b$ bits，加法、乘法与比较成本可能依赖 $b$ ；若数据不在内存，I/O次数可能比CPU指令更关键。成本模型必须和输入表示一起声明。

最好、最坏和平均运行时间

对已排序输入，while条件每轮第一次就失败，比较次数约 $n-1$ 。对逆序输入，第 $j$ 轮移动 $j$ 个元素：

\sum_{j=1}^{n-1}j=\frac{n(n-1)}2

因此最好时间 $\Theta(n)$ ，最坏时间 $\Theta(n^2)$ 。给出每个实例都不超过的保证，也常由容易构造的极端输入实现。

平均时间需要输入分布。若假设所有排列等概率，期望逆序对为 $n(n-1)/4$ ，插入排序仍为 $\Theta(n^2)$ ：

\mathbb E[\operatorname{inversions}]=\frac{n(n-1)}4

真实数据若几乎有序，逆序对 $k$ 很小，插入排序成本可描述为 $\Theta(n+k)$ 。参数化成本比只报最坏阶更能解释它为何适合小数组与近乎有序输入。

从语句计数到增长阶

设第 $j$ 轮while测试 $t_j$ 次，运行时间可写成若干常数乘求和。渐近分析忽略与 $n$ 无关的固定系数和低阶项，不是因为它们不存在，而是最高增长项决定大规模行为。

an^2+bn+c\in\Theta(n^2)\qquad(a>0)

把运行时间写成可核查的成本账本

精确分析不是先看见两层循环就宣布二次复杂度，而是为每条语句标出单次成本和执行次数。外层初始化执行一次，边界测试执行 $n$ 次，key保存和最终写回各执行 $n-1$ 次；内层测试次数 $t_j$ 取决于第 $j$ 个key之前有多少更大元素。于是总成本可以写成固定项与 $\sum t_j$ 的组合。已排序输入中每个 $t_j=1$ ，逆序输入中 $t_j=j+1$ ，两种输入由同一份代码产生不同账本。

这种写法还能暴露“比较次数”和“数据移动次数”并非同一个指标。昂贵对象的移动成本可能远高于整数比较；缓存友好的连续移动也可能胜过指针结构中的较少比较。因此渐近阶负责描述规模增长，操作分类与实测负责解释同一渐近阶实现之间的工程差异。只有先声明统计什么，测量结果才可复现。

时间之外还要声明空间

原地插入排序只保存key和少量索引，辅助空间为 $\Theta(1)$ ；这里的“原地”不表示完全没有内存，而是额外空间不随 $n$ 增长。上面的merge_sorted为输出分配长度 $n$ 的缓冲区，所以辅助空间为 $\Theta(n)$ 。若递归调用栈也计入，merge sort还要增加 $\Theta(\lg n)$ 栈空间，但它被线性缓冲区支配。

空间结论同样依赖实现：每层递归都重新分配临时数组会提高分配次数和峰值常数；预先申请一个共享缓冲区并在各层复用，仍保持 $\Theta(n)$ 辅助空间，却更接近可部署实现。分析报告应把输入存储、输出存储、辅助缓冲区和调用栈分开，避免用“内存是线性的”掩盖所有权与生命周期。

2.3 Designing algorithms

Insertion sort是incremental design：假设前 $j$ 项已解决，再插入一项。Designing algorithms还引入：

Divide：把长度 $n$ 数组分成两个近半子数组。
Conquer：递归排序两半。
Combine：线性merge两个有序序列。

Merge过程

Merge保持一个不变式：输出前缀包含两输入序列中最小的已消费元素，且有序。因为左右序列各自有序，未输出的全局最小值一定是两个front之一。

std::vector<int> merge_sorted(std::span<const int> left,
                              std::span<const int> right) {
    std::vector<int> out;
    out.reserve(left.size() + right.size());
    std::size_t i = 0, j = 0;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) out.push_back(left[i++]);
        else out.push_back(right[j++]);
    }
    out.insert(out.end(), left.begin() + i, left.end());
    out.insert(out.end(), right.begin() + j, right.end());
    return out;
}

每个元素恰好复制一次，比较次数至多 $n-1$ ，因此merge为 $\Theta(n)$ 时间、 $\Theta(n)$ 辅助空间。选择左侧相等元素使merge稳定。

Merge的正确性可以用“已输出前缀”不变式精确表达：循环每次比较前，out已经包含原左右序列中最小的若干元素，保持非降序；left[i]与right[j]分别是两边尚未输出的最小元素。输出二者较小者后，多重集只减少该元素，顺序仍成立。当一侧耗尽，另一侧剩余部分本来有序且不小于输出末尾，可以整体追加。初始化时输出为空，终止时所有元素恰好输出一次，因此同时得到有序性和排列保持。

边界条件决定实现是否真的满足这份证明。空序列必须直接追加另一侧；相等时先取左侧才能保持跨分区的原始顺序；索引类型不能在零位置向前递减。证明不是代码旁的装饰，它列出的命题正好转化为空输入、重复值、单元素和奇数长度分区测试。

Merge sort与递推

MERGE-SORT(A, p, r)
1  if p ≥ r
2      return
3  q = floor((p + r) / 2)
4  MERGE-SORT(A, p, q)
5  MERGE-SORT(A, q + 1, r)
6  MERGE(A, p, q, r)

两次半规模递归加一次线性merge得到：

T(n)= \begin{cases} \Theta(1),&n=1\\ 2T(n/2)+\Theta(n),&n>1 \end{cases}

递归树每层总merge成本 $\Theta(n)$ ，高度 $\lg n$ ，所以：

T(n)=\Theta(n\lg n)

Merge sort渐近优于插入排序，却需要辅助空间，且小数组上递归和复制常数可能更大。实际库常用hybrid：大区间分治，小区间切换插入排序。

混合阈值不是复杂度定理给出的常数。设递归与merge的固定开销为 $c_m$ ，插入排序在短区间上的局部成本为 $c_i k^2$ ；缓存层级、元素大小、移动语义和编译器都会改变交点。合理做法是在保持最坏复杂度不变的前提下，用代表性数据对多个阈值做基准测试，并分别包含随机、近乎有序和大量重复值输入。阈值是实现参数，不能把某台机器测出的数字伪装成算法普遍性质。

正确性与成本是两张证书

Merge sort正确性分层证明：归纳假设两次递归返回有序排列，merge不丢元素且按序组合，因此当前区间有序且保持多重集。成本证明则依赖划分平衡与merge线性；正确算法也可能因为不平衡切分退化。

小结

Chapter 2 Getting Started从Insertion sort建立“算法、证明、分析”闭环。插入排序通过有序前缀工作，循环不变式用initialization、maintenance、termination证明正确；输入逆序对数量解释了运行时间随数据分布变化。

Analyzing algorithms要求声明RAM模型、输入规模和概率假设；最坏情况提供上界，平均情况必须有分布。Designing algorithms用divide-and-conquer构造merge sort，线性merge与两次半规模递归产生 $\Theta(n\lg n)$ 成本。这套语言会贯穿后续章节。