什么是算法

在这一模块中，我们将介绍算法的定义和分析方法，并讲解一些经典算法的 C 语言实现。

数学基础要求

本模块假定读者有一定的数学水平：基本的算术 + 集合论 + 概率论 + 矩阵。

《算法导论》附录 A~D 中有对这部分数学的简明扼要的讲解。

1. 基本概念

1.1 定义

算法是为了解决某类问题而规定的一个有限长的操作序列。

1.2 特征

1. 有穷性：一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。
2. 确定性：对千每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行，不会产生二义性。
3. 可行性：算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
4. 输入：一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。
5. 输出：一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果

1.3 一个“公式”

$$\mathrm{程}\mathrm{序}=\mathrm{数}\mathrm{据}\mathrm{结}\mathrm{构}+\mathrm{算}\mathrm{法}$$

1.4 算法的表示

1. 自然语言
2. 流程图和 N-S 图
3. 伪代码（《算法导论》中采用这种方法）

2. 从描述到实现：中间这一步不能省

很多初学者在“读懂题意”后直接写代码，结果通常是边写边改，最后很难判断到底是思路错了还是实现错了。更稳妥的方法是先把问题写成三件事：输入对象是什么，输出对象是什么，步骤对象如何保证有限步结束。只要这三件事写清楚，后面的 C 语言实现会自然很多，因为你写的每个循环和分支都能对应到前面的描述，而不是凭感觉堆出来。

3. 正确性与复杂度要同时给出

算法学习里最常见的误区是只关注“能跑出答案”。事实上，一个解法如果没有正确性依据，就无法确认边界输入是否可靠；如果没有复杂度分析，就无法判断输入规模扩大时会不会失控。因此每个算法至少应回答两个问题：第一，为什么它一定得到正确结果；第二，它在时间和空间上大致要付出多少代价。这两个问题在后续章节会不断重复，越早建立习惯，越容易把新题型归入已有框架。

4. 一个最小完整示例：线性搜索

下面给一个很小但完整的例子。它的目标是在数组中找到目标值第一次出现的位置，若不存在则返回 -1。这段代码之所以值得作为起点，是因为它同时具备了输入约束、终止条件、返回语义和复杂度结论，能把“算法”与“程序片段”区分开。

#include <stdio.h>

static int linear_search(const int *a, int n, int target) {
    for (int i = 0; i < n; ++i) {
        if (a[i] == target) {
            return i;
        }
    }
    return -1;
}

int main(void) {
    int a[] = {8, 3, 2, 7, 3};
    int n = (int)(sizeof(a) / sizeof(a[0]));
    printf("index(7) = %d\n", linear_search(a, n, 7));
    printf("index(9) = %d\n", linear_search(a, n, 9));
    return 0;
}

可能的输出（示例）：

bash

index(7) = 3 index(9) = -1

线性搜索的最坏时间复杂度是 O(n)，空间复杂度是 O(1)。尽管它并不高效，但它很好地展示了一个算法条目的完整形态：有定义、有实现、有可解释的代价。后续你会发现，排序、图、动态规划都可以沿着这条结构继续展开。

习题

1. [20101] 某些算法实际上是数学题目：首先要用数学技巧求得解的简单表达形式，再编写简单的程序直接输出结果。这道题带有一定脑筋急转弯性质，解答这道题对编程技巧和学习算法没有太大帮助。
   1. [2.2] 平面上有 $n(n>2)$ 个不重合的点，将它们两两连成线段，将这些线段的中点涂成红色（如果有两个或两个以上的中点重合，那里只会呈现出一个红点）。输入 $n$，输出红点个数的最小值。
   2. [3.2] 甲乙两人在玩抽硬币游戏。$n(n>0)$ 枚硬币紧挨着摆成一圈，从甲开始，轮流抽走一枚或紧挨着的（如果 ABC 是紧挨着的并且 A 和 C 不是紧挨着的，那么 B 抽走之后，A 和 C 不再是紧挨着的）两枚硬币。抽走最后一枚硬币的人取得胜利。两个人都很聪明，会采取最优的策略。编写程序，输入 $n$，输出甲获胜的概率。