第1章 · 欢迎来到算法的世界

按图解版第1章重建算法、算法竞赛、C++、复杂度、三种基础排序、常数与规模，以及从约束到高效算法的完整推理链。

从“步骤写出来就叫算法吗”开始

日常语言里，人们常把“先做A，再做B”叫作算法。但程序必须面对更严格的问题：输入是什么、输出必须满足什么性质、每一步是否可执行、是否一定停止、资源是否够用。先预测：一个程序能对样例给出正确答案，却可能在哪些方面仍然不是可接受的算法？

不等于代码。代码是某种实现；算法还包括问题模型、状态表示、正确性理由、终止条件和成本边界。第1章“欢迎来到算法的世界”先建立这套判断标准，再把它带入算法竞赛。

1.1 算法是什么

一个可审查的算法至少有五部分：

输入域：允许空输入吗？元素可重复吗？数值范围是否会溢出？
输出契约：排序要求非降序，还是严格递增？是否保留重复元素？
状态与操作：每一步都能由目标机器精确执行。
正确性：对输入域中的每个实例，而不只是样例，都满足契约。
终止与成本：有限步内结束，并适合时间和空间限制。

以排序为例，输入为序列 $a_0,\ldots,a_{n-1}$ ，输出 $b$ 必须同时满足排列保持和有序：

\operatorname{multiset}(b)=\operatorname{multiset}(a)

b_0\le b_1\le\cdots\le b_{n-1}

只验证第二式不够。一个把所有元素都改成最小值的程序“有序”，却破坏了第一式。正确性必须覆盖完整输出契约。

1.2 算法竞赛是什么

把“读题、建模、设计、证明、实现、测试”压缩到一场比赛里。评测系统只看到程序在隐藏数据上的行为，因此竞赛训练的核心不是背模板，而是快速建立可证伪的假设。

1.2.1 紧张刺激的算法竞赛

紧张来自三重约束：

信息约束：题面给出故事，选手要还原数学结构。
资源约束：数据范围、时限和内存排除了大量做法。
证据约束：样例只说明几个实例，提交结果由隐藏测试决定。

contest workflow: 2 / 6

read

model

design

prove

implement

test

choose state and invariants

Competitive programming compresses the complete engineering loop into a short, measurable feedback cycle.

一次可靠解题循环可以写成以下检查顺序：

1.2.2 C++——统治算法竞赛的编程语言

C++与算法竞赛的契合点不是“语法更难”，而是同时提供：

接近机器成本的值类型、连续数组和位运算；
vector、sort、lower_bound、priority_queue、unordered_map等成熟组件；
模板与泛型算法，使同一实现服务多种类型；
明确的整数宽度和较强的性能可控性。

标准库应当被当作已验证的算法积木，而不是黑箱。使用std::sort时仍要知道它提供 $O(n\log n)$ 级比较成本、要求随机访问迭代器，并且默认不保证稳定性。选错容器也会改变复杂度，例如在vector头部反复插入是线性移动。

void selection_sort(std::vector<int>& a) {
    for (std::size_t i = 0; i < a.size(); ++i) {
        std::size_t best = i;
        for (std::size_t j = i + 1; j < a.size(); ++j) {
            if (a[j] < a[best]) best = j;
        }
        std::swap(a[i], a[best]);
    }
}

这里的不变式是：进入第 $i$ 轮时，区间[0, i)已经包含全局最小的 $i$ 个元素，且按非降序排列。每轮把剩余区间最小值放到位置$i`，因此不变式推进一格。

1.3 算法的复杂度是什么

不是秒表读数，而是先选定规模参数和基本操作，再分析次数函数。例如双层循环的内层长度依次为 $n-1,n-2,\ldots,1$ ：

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

当 $n$ 很大时，最高次项决定增长速度。用 $O$ 给上界、用 $\Omega$ 给下界、用 $\Theta$ 给紧确阶：

\frac{n(n-1)}2\in\Theta(n^2)

规模参数也不一定只有一个。图算法常同时使用顶点数 $V$ 与边数 $E$ ，批量查询常同时使用数据量 $n$ 与查询数 $q$ 。把所有输入都笼统写成 $n$ ，可能掩盖稀疏图和稠密图、一次查询和百万次查询之间的关键差异。复杂度表达式必须保留真正独立、会改变成本的参数。

1.3.1 从三个排序算法说起

从三个排序算法说起，可以把“步骤、证明、成本”放到同一张桌上比较。

冒泡排序反复比较相邻逆序对并交换。每完成一轮，当前最大元素移动到未排序区间末尾。若实现提前退出，已排序输入只需一次扫描；若没有退出，仍执行平方级比较。

void bubble_sort(std::vector<int>& a) {
    for (std::size_t end = a.size(); end > 1; --end) {
        bool changed = false;
        for (std::size_t i = 1; i < end; ++i) {
            if (a[i] < a[i - 1]) {
                std::swap(a[i], a[i - 1]);
                changed = true;
            }
        }
        if (!changed) break;
    }
}

选择排序每轮在未排序区间找最小值，只做一次交换。无论输入是否已有序，比较次数几乎不变，都是 $n(n-1)/2$ ；它适合说明“输入分布对某些算法不敏感”。

插入排序保持前缀有序，把下一个元素向左移动到正确位置。移动次数与逆序对数量直接相关；几乎有序时接近线性，逆序时达到平方级。

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

三者最坏时间都可写为 $O(n^2)$ ，但这不代表运行轨迹相同：冒泡交换相邻元素，选择排序减少交换，插入排序利用已有顺序。复杂度先排除不可行方案，再由数据特征和测量决定同一数量级中的选择。

1.3.2 低复杂度算法一定更快吗

“低复杂度算法一定更快吗”的答案分两层：

当 $n$ 趋向足够大时，较低增长阶会越过常数差距。
对具体有限输入，、缓存、分支预测、分配和I/O都可能改变胜负。

设算法A执行 $20n\log_2n$ 个轻重混合操作，算法B执行 $n^2$ 个简单操作。交叉点之前，B可能更少；交叉点之后，A的增长优势稳定显现。

1.3.3 构建高效的算法

构建高效的算法不是把每行代码都改得更短，而是按影响层级行动：

重述问题：输出真的需要完整排序吗，还是只要最大值、前 $k$ 项或存在性？
利用结构：有序性、单调性、重复子问题、图的稀疏性都可能降低成本。
选表示：数组、堆、哈希表和图邻接表为不同操作提供不同成本。
证明正确：用不变式、交换论证、归纳或反证说明所有合法输入。
计算预算：把 $n$ 和查询次数代入成本函数，估算时间与内存。
测量瓶颈：只优化真实热点，并保留边界测试防止回归。

observed cause

quadratic pair scan

candidate change

replace with sort plus two pointers

measure

growth rate

Efficient algorithms come from identifying the actual bottleneck: growth, locality, and I/O require different repairs.

例如“两数之和”若直接枚举所有下标对，工作量为：

\binom n2=\frac{n(n-1)}2

若只需判断是否存在，可边扫描边查询哈希表，期望时间降到 $O(n)$ ，代价是 $O(n)$ 额外空间；若数据已经排序，可用双指针在 $O(n)$ 时间、 $O(1)$ 额外空间完成。没有脱离contract的“唯一最优”，只有与约束一致的设计。

bool has_pair_sum(const std::vector<int>& sorted, long long target) {
    std::size_t left = 0;
    std::size_t right = sorted.size();
    while (left < right) {
        const long long sum = static_cast<long long>(sorted[left]) + sorted[right - 1];
        if (sum == target) return true;
        if (sum < target) ++left;
        else --right;
    }
    return false;
}

双指针的关键不是代码短，而是单调性证明：当前和偏小时，保留更小的左端不可能通过减小右端得到目标，因此必须增大左端；偏大时对称地减小右端。每一步排除一整行候选，总移动次数至多 $2n$ 。

本章方法：从题面到证据

可复用的提交前证书包括：

契约证书：输入域、输出性质、失败条件写清楚。
正确性证书：初始化、保持、终止三段不变式完整。
复杂度证书：基本操作次数、额外空间、最坏与期望条件分开。
实现证书：整数宽度、下标边界、容器失效规则已检查。
测试证书：最小规模、最大规模、重复、极端有序、随机对拍均覆盖。

小结

第1章建立了全书的共同语言：算法是什么，决定了我们必须讨论contract、正确性、终止和成本；算法竞赛是什么，决定了约束与隐藏测试是设计的一部分；C++与算法竞赛的结合，提供了兼顾表达速度和运行效率的工具。算法的复杂度是什么，则把“感觉会快”变成可计算的增长模型。

从三个排序算法说起，我们看到相同的平方级标签仍可能有不同轨迹；“低复杂度算法一定更快吗”提醒我们区分渐近优势与有限输入；构建高效的算法最终依赖问题重述、结构、表示、证明、预算和测量的闭环。