第1章 算法设计基础

1-1 什么是算法

见识算法

• 算法是计算机科学的基石：从古代算术到现代计算机，算法始终是解决问题的核心。

算法的起源

• 张苍《九章算术》：创立了机械化算法体系（如“合分术”分数相加算法）。

• 欧几里得《几何原本》：奠定了逻辑演绎体系，为后世算法理论提供严密的数学基础。

---

1.1.1 算法的定义

• 算法：对特定问题求解步骤的一种描述，是指令的有限序列。

• 三要素：

  1. 有穷性：算法必须在有限步内终止，防止出现死循环或无限运行，以保证能在实际环境中获得结果；

  2. 确定性：每一步都有唯一明确定义，避免歧义和不一致，确保重复执行时输出一致；

  3. 可行性：每一步都能在有限时间和空间资源下执行，保证算法在实际计算环境中可实现。

Problem 与 Instance

• Problem（问题）：规定输入与输出之间关系的抽象集合；

• Instance（实例）：具体的输入数据集合。

• 排序问题示例：

  • 输入：<31, 41, 59, 26, 41, 58>

  • 输出：<26, 31, 41, 41, 58, 59>

示例题目

• 例1.1 设计算法求两个自然数的最大公约数

  • 思路（质因数分解法）：

    1. 找出 m 的所有质因子；

    2. 找出 n 的所有质因子；

    3. 求交集并相乘。

  • 缺陷：分解过程时间复杂度高，因子枚举不确定，难以扩展大数运算，且分解失败时无法输出。

• 例1.2 欧几里德算法——辗转相除法求最大公约数

  • 步骤：

    1. r = m % n

    2. 若 r = 0，则输出 n；否则 m ← n，n ← r，转步骤1。

  • 优点：时间复杂度 O(log min(m,n))，保证有穷性和可行性，简单易实现，确定性强。

---

1.1.2 算法的描述方法

1. 自然语言

   • 优点：通俗易懂；缺点：描述不够严密，易产生歧义。

2. 程序流程图

   • 优点：结构清晰、直观；缺点：难表达复杂逻辑，维护和修改成本高。

3. 伪代码

   • 优点：兼顾可读性与严密性，可快速转化为程序；缺点：语法非标准，不同风格可能导致理解成本。

示例伪代码题目

• （1）瓶子 A 与 B 液体互换

  1. C ← A

  2. A ← B

  3. B ← C

• （2）三个数由小到大排序

  1. 若 x > y，则交换；

  2. 若 z < x，则循环交换；否则若 z < y，则交换；

  3. 输出 x, y, z。

• （3）在 n 元素集合中查找最大值

  1. max ← a[1]；

  2. i ← 2；

  3. 当 i ≤ n 时：若 a[i] > max，则 max ← a[i]；i ← i + 1；

  4. 输出 max。

---

1.1.3 算法在问题求解中的地位

1. 人 分析问题并设计算法；

2. 人 编写程序；

3. 机器 执行程序，得到结果。

强调算法设计是沟通人和机器的桥梁，决定程序效率与可维护性。

---

1-2 什么是好算法

1.2.1 如何评价算法

1. 正确性：算法必须对所有合法输入产生正确输出，否则无法信赖；

2. 健壮性：能识别和处理无效或异常输入，避免程序崩溃或产生误导性结果；

3. 可理解性：清晰的逻辑结构和注释便于他人阅读、调试和维护，降低开发成本；

4. 抽象分级：合理划分模块和层次，符合人类认知规律（7±2 原则），提高复用性；

5. 高效性：兼顾时间复杂度和空间复杂度，使算法在大规模数据或复杂环境中仍能快速运行；

6. 可扩展性：便于后续功能扩展或性能优化，以适应需求变化。

案例对比：当 n = 10³ 时，冒泡排序约需 0.01 s；当 n = 10⁶ 时，快速排序仅需约 0.02 s，而冒泡排序则超过 10² s，效率差异随规模增长指数级放大。

---

1-3 为什么要学习和研究算法

1.3.1 算法研究推动计算机技术发展

• 查找问题：二分查找 O(log n)，将线性查找 O(n) 降为对数级，大幅提升检索效率；

• 图问题：Dijkstra 算法解决最短路径，实现地图导航、网络路由等核心功能；

• 组合优化：背包问题、旅行商问题等，影响资源分配与调度系统设计。

多数现代应用（搜索引擎、社交网络、电子商务）都依赖高效算法来支撑海量数据处理。

1.3.2 算法训练提升计算思维能力

• 模型化：将现实问题抽象为数学模型，有助于使用已知算法求解；

• 抽象思考：在机外表示与机内表示间切换，理解问题核心；

• 形式化：将解题思路转化为伪代码或程序，保证逻辑严密性和可执行性。

思维收益：培养分治、贪心、动态规划等思维模式，提高解决复杂问题的条理性与创造力。

1.3.3 程序员必学算法的程度

Algorithm + Data Structures = Programs

• 基础功底：理解算法思想有助合理选择和组合数据结构；

• 应用层面：不必精通所有算法，但应熟练掌握常用排序、查找、图算法等；

• 高级优化：针对性能关键场景，掌握算法优化技巧能显著提升系统效率。

---

1-4 如何设计算法

1.4.1 基本数据结构及其作用

• 集合：无序元素集合，支持高效去重和成员检测；

• 线性结构：表、栈（LIFO）、队列（FIFO），常用于任务调度和历史记录；

• 树结构：二叉树、平衡树，用于层级数据组织与快速查找；

• 图结构：邻接表、邻接矩阵，灵活表示网络、依赖关系等。

1.4.2 常见问题类型与典型算法思路

• 查找：顺序查找、二分查找、哈希查找；

• 排序：冒泡、插入、归并、快速、堆排序；

• 图：遍历（DFS/BFS）、最短路径、最小生成树；

• 组合优化：动态规划（背包、LCS）、分支限界；

• 数学：质数判定、最大公约数、快速幂；

• 几何：凸包、扫描线。

1.4.3 算法设计一般流程

1. 问题分析：明确输入输出与性能约束；

2. 选择技术：分治、动态规划、贪心、回溯等；

3. 算法描述：伪代码或流程图；

4. 手动模拟：验证正确性，修正逻辑；

5. 实现编码：关注可读性与可维护性；

6. 复杂度分析：评估时间和空间消耗；

7. 迭代优化：基于测试与分析，持续改进性能。

---

1-5 拓展与演练

1.5.1 图灵奖获奖者与算法贡献

• Edsger Dijkstra：Dijkstra 最短路径算法；

• Donald Knuth：《算法艺术》系列与文献规范；

• Tony Hoare：快速排序；

• Stephen A. Cook：NP 完全性理论；

• Andrew Yao（姚期智）：通信复杂度与伪随机数理论；

• Leslie Valiant：概率近似正确模型；

• Yoshua Bengio、Geoffrey Hinton、Yann LeCun：深度学习算法发展。

1.5.2 代码优化技巧及原因

1. 常量计算：编译期计算不变表达式，减少运行时开销；

2. 算术优化：用加减或 Horner 法则替代乘除；

3. 位运算替代：如 x & 1 判断奇偶，加快计算；

4. 避免重复：缓存中间结果，减少函数调用；

5. 共享子表达式：提高编译器优化机会；

6. 逻辑短路：提前终止无必要判断；

7. 合并循环：减少循环次数，降低控制开销；

8. 循环不变式外提：移出循环内不变运算；

9. 合理条件顺序：高概率分支优先，降低分支预测失败；

10. 嵌套循环优化：优先减少内层循环次数。