欢迎来到算法的世界！
欢迎踏上离散数学之旅的第一步！别被「算法」(Algorithms) 这个名词吓到了。简单来说，算法就是一套用来解决问题的指令集——就像烘焙蛋糕的食谱，或是你系鞋带时遵循的步骤一样。
在本章中，我们将学习如何清晰地表达这些指令，如何衡量算法的「执行速度」，并探讨一些经典的数据排序方法以及如何在网络中找出最佳路径。让我们开始吧！
1. 什么是算法？
在开始编写之前，我们需要了解一个「好的」算法具备什么条件。根据 OCR 课程大纲，每个算法都必须具备以下特征：
• 有限性 (Finite)： 它必须在有限步骤内结束。如果食谱叫你「永远搅拌下去」，那绝对不是个好算法！
• 确定性 (Deterministic)： 如果你使用相同的起始数据并遵循相同的步骤，结果必须永远一致。
• 输入/输出 (Input/Output)： 它需要输入初始数据 (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) 和 快速排序 (Quick Sort)。默认情况下，冒泡排序和穿梭排序均从列表的最左端开始。
冒泡排序 (Bubble Sort)
想象最大的数字很「重」，会沉到底部（列表末端），而较小的数字则会像气泡一样「浮」到顶部。
1. 比较前两个项目。如果第一个比较大，就交换它们。
2. 向右移一步，比较下一对。重复此过程直到列表末端。
3. 最后一个数字现在已在正确位置。对剩余的数字重复整个流程。
穿梭排序 (Shuttle Sort)
把它想象成一旦找到一个数字，就把它「穿梭」回正确位置。
1. 比较第一个和第二个项目。必要时交换。
2. 接着看第三个项目。将它与第二个比较。如果需要左移，就进行交换，然后再与第一个比较。
3. 之后的每个项目，都持续将其向左交换，直到它遇到比自己小的数值为止。
快速排序 (Quick Sort)
快速排序利用枢轴 (pivot) 来对列表进行分治 (divide and conquer)。
1. 选择一个枢轴（在 OCR 中，除非另有说明，否则默认选择子列表中的第一个数值）。
2. 将剩余项目划分为两个子列表：小于枢轴的项目，以及大于或等于枢轴的项目，并保持它们原有的相对顺序。
3. 将枢轴放置在两个子列表之间（此时该枢轴的位置已固定）。
4. 对每个子列表递归应用此算法，直到所有项目都被选为枢轴为止。
常见错误： 在冒泡排序中，许多学生会忘记，即使列表看起来已经排序完成，算法仍必须完成它的轮次 (passes) 或达到正式的停止条件（在一整轮中没有发生任何交换）才能正式结束。
重点总结： 冒泡排序和穿梭排序都是二次方的，即 \( O(n^2) \)。快速排序平均为 \( O(n \log n) \)，但最坏情况下的阶数为 \( O(n^2) \)。
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) 就是一个边上有「权重」（数字，如距离或成本）的图。
戴克斯特拉算法 (Dijkstra’s Algorithm，最短路径)
这用于找出起始节点到其他节点之间的最短路径。它是一个贪婪算法，因为它每次都选择下一个距离最近且尚未访问过的节点。
• 阶数： 二次方，\( O(n^2) \)，其中 \( n \) 是顶点数量。
最小连接器 (生成树，Spanning Trees)
目标是用最小的边总权重连接网络中的每个节点，且不形成回路。
1. 克鲁斯卡尔算法 (Kruskal’s Algorithm)： 将所有边按权重升序排列。随时挑选图中可用的最短边，只要它不会形成回路 (cycle)（封闭的环）。
2. 普里姆算法 (Prim’s Algorithm，图形或矩阵形式)： 从一个起始顶点开始。总是挑选连接任何当前已访问顶点与未访问顶点的最短边。在距离矩阵／表格形式中，划掉所选顶点的行 (row)，并在活动的列 (columns) 中圈出最小值。
快速回顾：Dijkstra vs. Prim/Kruskal
• 使用 Dijkstra 来找出从起始顶点到其他顶点的路径。
• 使用 Prim 或 Kruskal 来以最低成本将所有顶点连接起来。
重点总结： Prim 和 Kruskal 算法都能找到最小生成树 (MST)。以顶点数量为基准，两者的阶数都是三次方 (cubic order)，即 \( O(n^3) \)。
算法阶数总表
• 排序 (Bubble/Shuttle)： \( O(n^2) \) (二次方)
• 排序 (Quick Sort)： 平均 \( O(n \log n) \)，最坏情况 \( O(n^2) \)
• 最短路径 (Dijkstra)： \( O(n^2) \) (二次方)
• 最小连接器 (Prim/Kruskal)： \( O(n^3) \) (三次方)
你已经完成了算法章节！继续练习你的追踪表和排序轮次——持之以恒是掌握离散数学的关键。你一定行的！