欢迎来到算法的世界！
欢迎踏上离散数学之旅的第一步！别被「算法」(Algorithms) 这个名词吓到了。简单来说，算法就是一套用来解决问题的指令集——就像烘焙蛋糕的食谱，或是你系鞋带时遵循的步骤一样。
在本章中，我们将学习如何清晰地表达这些指令，如何衡量算法的「执行速度」，并探讨一些经典的数据排序方法以及如何在网络中找出最佳路径。让我们开始吧！
1. 什么是算法？
在开始编写之前，我们需要了解一个「好的」算法具备什么条件。根据 OCR 课程大纲，每个算法都必须具备以下特征：
• 有限性 (Finite)： 它必须在有限步骤内结束。如果食谱叫你「永远搅拌下去」，那绝对不是个好算法！
• 确定性 (Deterministic)： 如果你使用相同的起始数据并遵循相同的步骤，结果必须永远一致。
• 输入/输出 (Input/Output)： 它需要输入初始数据，并在最后给出答案（输出）。
必须记住的关键术语
贪婪算法 (Greedy Algorithm)： 这类算法在每一步都选择当下看起来「最好」的选项，而不考虑长远影响。想象你在吃自助餐，每次都拿盘子里最大块的披萨——这就是贪婪策略！
启发式方法 (Heuristic)： 这是一种「经验法则」或捷径。它未必每次都能给出 100% 完美的答案，但通常「够好」，而且比检查所有可能性快得多。
递归 (Recursive)： 指算法调用自身。想象俄罗斯套娃；为了到达最中心，你必须不断打开较小的同款娃娃。
快速回顾：基本概念
输入 (Input) → 算法 (指令) → 输出 (Output)
例子： 食材 → 食谱 → 蛋糕
2. 处理算法：追踪与解读
最重要的技能之一就是「追踪」(tracing) 算法。这意味着你要像电脑一样，通过追踪表 (trace table) 一行一行地执行指令。
算法可以通过流程图 (flow diagrams)（使用框图和箭头）或伪代码 (pseudo-code)（使用类似计算机程序代码但语句通顺的英文）来呈现。
你需要用到的数学工具
在伪代码中，你经常会看到这两个函数：
1. \( \text{INT}(x) \)：意指「向下取整」，即舍去小数点后的部分。例如，\( \text{INT}(4.7) = 4 \) 且 \( \text{INT}(4.1) = 4 \)。
2. \( \text{ABS}(x) \)：这是「绝对值」。它只是将数字转为正数。所以，\( \text{ABS}(-5) = 5 \) 且 \( \text{ABS}(5) = 5 \)。
别担心，一开始可能会觉得有点复杂！ 追踪的关键在于条理。请使用一个表格，为每个变量设立一栏，并在执行过程中随时更新数值。
重点总结： 追踪能帮你在此不实际编写程序的情况下，理解算法到底在达成什么目标。
3. 排序策略：数据的秩序
排序是离散数学中非常重要的一部分。我们专注于两种主要方法：冒泡排序 (Bubble Sort) 和 插入排序 (Shuttle Sort/Insertion Sort)。两者都从列表的最左端开始。
冒泡排序 (Bubble Sort)
想象最大的数字很「重」，会沉到底部（列表末端），而较小的数字则会像气泡一样「浮」到顶部。
1. 比较前两个项目。如果第一个比较大，就交换它们。
2. 向右移一步，比较下一对。重复此过程直到列表末端。
3. 最后一个数字现在已在正确位置。对剩余的数字重复整个流程。
插入排序 (Shuttle Sort)
把它想象成一旦找到一个数字，就把它「穿梭」回正确位置。
1. 比较第一个和第二个项目。必要时交换。
2. 接着看第三个项目。将它与第二个比较。如果需要左移，就进行交换，然后再与前一个比较。
3. 基本上，每检查一个新项目，就持续将其向左交换，直到它遇到比自己小的数字为止。
常见错误： 在冒泡排序中，许多学生会忘记，即使列表看起来已经排序完成，算法仍必须完成它的「轮次」(passes) 或达到特定的「停止条件」（例如在一轮中没有发生任何交换）才能正式结束。
重点总结： 这两种排序算法都是「二次方」(quadratic) 的，意味着如果将项目数量翻倍，所需的时间大约会变成原来的四倍！
4. 装箱问题：如何装好装满？
我们该如何将物品装入固定大小的箱子中？这些属于启发式 (heuristic)（捷径）方法。它们通常分为「在线」(online)（物品随到随装）或「离线」(offline)（开始前先看过所有物品）。
• 首次适应 (Next-Fit，在线)： 把物品放入当前的箱子。如果不够放，就永远关闭该箱子并开启一个新的。
• 首次适应 (First-Fit，在线)： 尝试将物品放入建立的第一个箱子。如果放不下，试试第二个，接着第三个，依此类推。只有当所有现有箱子都放不下时，才开启一个新的箱子。
• 首次适应递减 (First-Fit Decreasing，离线)： 先将物品按降序（从大到小）排列，然后使用 First-Fit 方法。这通常能得到更好的结果！
• 装满箱子 (Full Bin，启发式)： 寻找能将箱子容量刚好填满到 100% 的物品组合。
你知道吗？ First-Fit Decreasing 是「离线」的，因为你必须事先知道所有物品才能进行排序。而 Next-Fit 是「在线」的，因为你可以像在传送带上一样，来一个物品就装一个箱子！
5. 算法的「阶数」(Big O 符号)
我们需要一种方法来衡量效率。我们使用阶数 (Order) 符号，例如 \( O(n^2) \) 或 \( O(n^3) \)，其中 \( n \) 是问题的「规模」（例如列表中项目的数量）。
• 如果算法是 \( O(n) \)，项目翻倍，时间只需 2 倍。
• 如果是 \( O(n^2) \)，项目翻倍，时间变成 4 倍 (\( 2^2 \))。
• 如果是 \( O(n^3) \)，项目翻倍，时间变成 8 倍 (\( 2^3 \))。
记忆小撇步： 当看到执行时间公式（如 \( T(n) = 3n^2 + 5n + 10 \)）时，阶数取决于「主导项」（次数最高的那一项）。所以这就是 \( O(n^2) \)。
重点总结： 了解阶数能让你根据小规模的测试结果，预测庞大的计算机任务需要花费多少时间。
6. 网络算法：寻找最佳路径
先决条件：请记住，网络 (network) 就是一个边上有「权重」(weights)（如距离或成本）的图。
戴克斯特拉算法 (Dijkstra’s Algorithm，最短路径)
这用于找出起始点到网络中其他每个点的最短路径。它是一个贪婪算法，因为它每次都选择下一个「距离最近」且尚未访问过的节点。
• 阶数： 二次方，\( O(n^2) \)，其中 \( n \) 是顶点数量。
最小连接器 (生成树，Spanning Trees)
目标是用边的总权重最小化来连接网络中的每个节点。想象要以最少的管线将房屋连接到主水管。
1. 克鲁斯卡尔算法 (Kruskal’s Algorithm)： 随时挑选图中权重最小的边，只要它不会形成「回路」(cycle)（封闭的环）。
2. 普里姆算法 (Prim’s Algorithm)： 从一个节点开始。总是挑选一条边，连接一个「已访问」的节点与一个「未访问」的节点，且权重最小。
快速回顾：Dijkstra vs. Prim/Kruskal
• 使用 Dijkstra 来找出从 A 到 B 的路径。
• 使用 Prim 或 Kruskal 来以最低成本将所有节点连接起来。
重点总结： Prim 和 Kruskal 算法都能找到最小生成树 (MST)，但使用了不同的策略。两者都是三次方阶数 (cubic order)，即 \( O(n^3) \)。
算法阶数总表
• 排序 (Bubble/Shuttle)： \( O(n^2) \) (二次方)
• 最短路径 (Dijkstra)： \( O(n^2) \) (二次方)
• 最小连接器 (Prim/Kruskal)： \( O(n^3) \) (三次方)
你已经完成了算法章节！继续练习你的追踪表和排序轮次——持之以恒是掌握离散数学的关键。你一定行的！