欢迎来到算法的世界！
欢迎来到离散数学的第一章。别被“进阶数学”（Further Maths）这个名字吓到了——其实算法是你每天都在用的东西！无论是跟着食谱烤蛋糕、用 GPS 导航，还是根据天气决定穿什么，你都在使用算法。在这一章中，我们将学习如何清晰地写出这些“数学食谱”，如何测试它们，以及如何找出其中执行速度最快的方法。
1. 什么是算法？
简单来说，算法（Algorithm）就是一套用于解决特定问题的逐步指令。要成为一个真正的算法，必须具备以下三个要素：
1. 输入（Input）：你开始时的数据（例如一串数字列表）。
2. 输出（Output）：你最终得到的结果（例如排序后的列表）。
3. 有限性（Finiteness）：它必须在有限步骤内结束！永远不会停止的指令是没有意义的。
策略的主要类型
在设计算法时，我们有时会采取不同的“思维模式”：
• 贪婪法（Greedy）：这种算法在每一步都做出当前看起来最好的选择，希望藉此达到整体最佳结果。比喻：如果你要凑出 40p 的硬币，贪婪算法会先选最大的那个（20p），然后再选一个（20p）。
• 启发式算法（Heuristic）：这是所谓的“经验法则”。它们可能无法每次都给出最完美、最优化的答案，但对于处理复杂的大问题时，它们速度快且“足够好”。
• 递归（Recursive）：这是一种会“调用自己”的算法。它将一个大问题分解成若干个同类型的较小问题。比喻：要打扫整间屋子，先打扫一个房间，然后“调用”清理剩余房间的指令。
快速回顾：检查清单
• 它是否具有确定性（Deterministic）？（相同的输入是否总能得到相同的输出？）
• 它是否有终止条件（Stopping Condition）？（告诉“计数器”何时停止的规则。）
• 它是否有计数器（Counter）？（用来记录某个步骤重复执行次数的方法。）
重点总结：算法是一组有限、可预测的指令，将输入转化为输出。
2. 算法追踪（Tracing）与操作
在考试中，你经常会被要求“追踪”（trace）一个算法。这意味着你要像计算机一样，精确地遵循每一条指令，即使你觉得给自己已经找到了捷径！
追踪工具
算法可以用流程图（Flow Diagrams）（使用方框和箭头）或伪代码（Pseudo-code）（用类似英语的数学语言写成的指令）来表示。你需要掌握两个特定的函数：
• INT(x)：这是“取整”函数。它会将任何数字向下舍入到最接近的整数。例如，\( INT(4.7) = 4 \)，而 \( INT(5.99) = 5 \)。
• ABS(x)：这是“绝对值”。它会忽略负号。例如，\( ABS(-3) = 3 \)，而 \( ABS(3) = 3 \)。
重点总结：追踪需要使用追踪表（Trace Table）。每当变量（如 \( x \) 或 \( y \)）的值发生变化时，都要新开一行进行记录。
3. 算法的阶数（效率）
并非所有算法都是一样的。随着问题的“规模”（记作 n）增加，有些算法所需的时间会比其他算法长得多。我们使用大 O 符号（Big O Notation）来衡量这一点。
理解 Big O
如果一个算法的运行时间公式是 \( T(n) = n^2 + 5n + 10 \)，我们称其阶数（Order）为 \( O(n^2) \)。为什么呢？因为当 \( n \) 变得非常大（比如一百万）时，\( n^2 \) 项远大于其他项，使得 \( 5n \) 和 \( 10 \) 变得微不足道。我们将最高次幂称为主导项（dominant term）。
阶数的层级
从最快（最有效率）到最慢（效率最低）：
\( O(1) \) [常数阶] \( \subset O(\log n) \) [对数阶] \( \subset O(n) \) [线性阶] \( \subset O(n \log n) \) \( \subset O(n^2) \) [二次阶] \( \subset O(n^3) \) [立方阶] \( \subset O(a^n) \) [指数阶] \( \subset O(n!) \) [阶乘阶]
你知道吗？一个指数级算法 \( O(2^n) \) 是如此缓慢，以至于如果 \( n=100 \)，在普通计算机上运行完成所需的时间将超过宇宙的年龄！
数学技巧：整数和
在分析排序算法进行了多少次比较时，你通常需要这个公式：
前 \( n \) 个整数之和为 \( \sum_{r=1}^n r = \frac{1}{2}n(n+1) \)。
由于这里的最高次幂是 \( n^2 \)，许多简单的排序算法都属于二次阶（Quadratic Order） \( O(n^2) \)。
重点总结：效率是指运行时间如何缩放（scales）。如果一个 \( O(n^2) \) 算法处理 10 个项目需要 4 秒，那么将项目加倍到 20 个时，它会花费 \( 2^2 = 4 \) 倍的时间（即 16 秒）。
4. 排序算法
排序是计算中最常见的任务。你需要掌握三种主要方法：
A. 冒泡排序（Bubble Sort）
比较前两个项目。如果顺序不对，就交换它们。然后移动到下一对。在第一轮“遍历”（pass）结束时，最大的项目会像气泡一样“浮”到最后面。
• 效率： \( O(n^2) \)。对于大型列表来说，它很简单但速度较慢。
B. 穿梭排序（Shuttle Sort）
与冒泡排序类似，但当你进行一次交换后，你会立即检查该项目后方的项目，看是否需要进一步向后移动。
• 效率：同样是 \( O(n^2) \)，但在实际应用中，通常比冒泡排序的交换次数少。
C. 快速排序（Quick Sort，Stage 2）
选择一个“枢轴”（pivot，通常是第一个项目）。将所有小于枢轴的项目放在其左侧，大于枢轴的放在右侧。然后对新创建的两个列表重复此过程。
• 效率：通常非常快，但在最坏情况下是 \( O(n^2) \)。
重点总结：除非题目另有说明，否则排序时始终从左边开始！
5. 装箱算法（Bin Packing）
这涉及将不同大小的物品装入固定容量的“箱子”中。就像试图有效地整理行李箱一样。
策略（启发式）
• 下个适合（Next-Fit）：将物品放入当前箱子，直到下一个物品放不下为止。关闭该箱子并移至一个新箱子。（你永远不会回头处理旧箱子）。
• 首次适合（First-Fit）：对于每个新物品，尝试将其放入你最先开始使用的箱子中。只有当现有箱子都放不下时，才开始使用一个新箱子。
• 递减首次适合（First-Fit Decreasing, FFD）：先将物品按降序排列，然后使用“首次适合”。这通常是处理“离线”问题最有效的方法。
• 满箱（Full Bin）：“手动”搜索物品组合，使箱子刚好 100% 装满。
记忆小帮手：在线（Online）与离线（Offline）
• 在线（Online）：你像物品到达时一样即时进行装箱（Next-Fit, First-Fit）。
• 离线（Offline）：你可以先看到所有物品并将它们进行排序（FFD）。
重点总结：FFD 通常是最好的，但你必须记得先对列表进行排序，否则会失分！
6. 背包问题（The Knapsack Problem）
想象你是个人小偷，带着一个只能承重一定重量的背包。你想要选择能获得最大利润的物品，且背包不会破裂。
这是一个经典的优化（optimisation）问题。你必须在物品的质量和价值之间取得平衡。
快速回顾总结：算法是工具。我们使用追踪（Tracing）来检查它们是否有效，使用大 O（Big O）来检查它们的速度，并使用启发式（Heuristics）来解决诸如装箱和排序之类的棘手问题。