第23章 算法与算法描述

23.1 算法的概念

算法：解决特定问题、有限步可执行的步骤集合，有明确定义的输入与输出，能在有限时间内求得结果。

23.2 算法五大基本特性

1. 有穷性：步骤一定有限，不能死循环。例：1~100 求和最多 100 次循环结束。
2. 确定性：每步无歧义，相同输入必得相同输出。"随便算一下"不满足确定性。
3. 可行性：每步都能用基础操作在有限时间完成。
4. 输入：0 个或多个输入数据。求最大值需输入两个数；打印 Hello 无需输入。
5. 输出：至少产生一个结果。排序算法输出有序数组。

23.3 算法四大评价标准

1. 正确性：所有合法输入都得正确结果，最基础的要求。
2. 可读性：逻辑清晰、易调试维护。
3. 时间复杂度：衡量快慢，用大 O 记号 $O(\dots)$，数值越小越快。$O(n)$ 远快于 $O(n^2)$。
4. 空间复杂度：运行额外占用的内存大小。

23.4 四种算法描述方法

23.4.1 自然语言（中文/英文）

优点：通俗易懂；缺点：冗长、易歧义。

示例：求两数最大值

1. 输入整数 a、b；
2. 比较 a 和 b；
3. 若 a > b 输出 a，否则输出 b。

23.4.2 流程图

标准符号：

• 圆角矩形：开始 / 结束
• 矩形：处理 / 计算
• 菱形：条件判断
• 箭头：执行流向

23.4.3 伪代码

介于自然语言与代码之间，忽略语法细节、保留逻辑，极易转成 C/C++。

算法：选择排序
输入：长度为 n 的数组 arr
1. for i = 0 to n-2
       min_index = i
       for j = i+1 to n-1
           若 arr[j] < arr[min_index]，则 min_index = j
       交换 arr[i] 与 arr[min_index]
2. 输出 arr

23.4.4 编程语言（C/C++）

直接可运行的完整代码，语法严格无歧义。

#include <iostream>
using namespace std;
int main() {
    int num1 = 12, num2 = 18;
    int a = num1, b = num2;
    // 辗转相除法求最大公约数
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    int gcd = a;
    int lcm = (num1 / gcd) * num2;  // 先除后乘防溢出
    cout << "最大公约数：" << gcd << "\n";
    cout << "最小公倍数：" << lcm << endl;
    return 0;
}

23.5 常见基础算法思想

1. 枚举：遍历全部候选解，筛选符合条件的答案（百钱百鸡、水仙花数）。
2. 递推：由初始值按公式向后迭代（斐波那契、阶乘）。
3. 递归：大问题拆成同结构小问题，自身调用（阶乘、汉诺塔）。
4. 贪心：每步取局部最优，期望全局最优（活动选择）。
5. 分治：均分拆分子问题分别求解再合并（快排、归并排序）。

23.6 选择题练习

1. 下列不属于算法五大特性的是？

A. 有穷性
B. 确定性
C. 高效性
D. 可行性

2. 用来表示"条件判断"的流程图图形是？

A. 圆角矩形
B. 矩形
C. 菱形
D. 平行四边形

3. 衡量算法运行快慢的指标是？

A. 空间复杂度
B. 时间复杂度
C. 可读性
D. 正确性

4. 以下哪种描述方式最不容易产生歧义、且可直接运行？

A. 自然语言
B. 流程图
C. 伪代码
D. 编程语言代码

5. 一个"永不停止的循环"违反了算法的哪一特性？

A. 确定性
B. 有穷性
C. 可行性
D. 输入