欢迎来到算法的世界！
在本章中，我们将深入探索现代科技的“心脏”。从 Netflix 如何推荐影集，到物流货车如何规划最快路径，算法 (Algorithms) 无处不在。在进阶数学中，我们学习算法不仅是为了找到问题的解法，更重要的是了解如何以“高效”的方式去解决。别担心，如果这听起来有点像“计算机科学”，请放心——我们会把它拆解成简单且合乎逻辑的步骤！
1. 什么是算法？
算法的本质就是一套指令。试着把它想象成烘焙蛋糕的食谱：如果你严格按照步骤操作，每次都应该会得到同样的结果。
算法的核心特征：
- 有限性 (Finiteness)： 必须有明确的起点（初始状态）和终点。它不能无限循环！
- 输入 (Input)： 开始时给予的数据。
- 输出 (Output)： 算法产生的结果或解决方案。
- 变量 (Variables)： 就像暂时性的“存储盒”，用来存放算法运行过程中会改变的数字或标签。
算法的呈现方式：
你通常会通过以下三种格式看到算法：
- 文字描述 (Written English)： 用通俗语言写成的逐步指令。
- 流程图 (Flowcharts)： 利用方框和箭头组成的视觉化地图。
- 伪代码 (Pseudocode)： 介于人类语言与计算机程序代码之间的格式（例如："Let \(i = i + 1\)" 意思是用 \(i\) 的当前值加 1 后的结果来取代 \(i\)）。
快速复习： 算法必须是有限的（必须有终止）且决定性的（遵循步骤会得出明确的结果）。
2. 算法复杂度 (Algorithmic Complexity)
并非所有算法都是平等的。有些很快，而有些在问题“规模”变大时会变得非常慢。这就是我们所说的复杂度 (Complexity)。
“大 O”符号 (Big O Notation)
我们使用阶数符号 (Order Notation) 来描述算法所需时间如何随输入规模 (\(n\)) 增加而增长。在本课程中，你需要特别了解二次复杂度 (Quadratic Complexity)，写作 \(O(n^2)\)。
例子： 如果你有 10 个项目，排序需要 100 秒，而 20 个项目则需要 400 秒，这代表时间随着项目增加的倍数呈现平方增长（\(2^2 = 4\) 倍）。这就是 \(O(n^2)\) 的特性。
避免常见错误： 不要把“问题的规模 (size of the problem)”与“数字的大小 (value of the numbers)”搞混。如果你正在排序一个列表，\(n\) 指的是列表中有多少个数字，而不是数字本身有多大。
3. 排序算法：快速排序法 (Quick Sort)
排序是算法中最常见的任务。快速排序法 (Quick Sort) 是一种强大的方法，它利用一个枢纽 (pivot) 将列表分成更小的部分。
如何执行快速排序（递增）：
- 选择一个枢纽 (pivot)（通常是列表中的第一个或中间项目）。
- 将其他所有项目与枢纽进行比较。
- 将小于枢纽的项目移至左侧子列表，大于枢纽的项目移至右侧子列表。
- 现在，枢纽已处于其最终正确位置。
- 对新的子列表重复上述过程，直到每个项目都成为过一次枢纽。
重要重点：
- 比较 (Comparisons)： 每当你询问“这个数字是否大于枢纽？”时，这就算作一次比较。
- 交换 (Swaps)： 每当你移动一个项目时，这就算作一次交换。
- 最差情况 (Worst Case)： 快速排序法的最差情况复杂度为 \(O(n^2)\)。
关键要点： 一旦一个数字被选为枢纽并形成了子列表，该枢纽在接下来的算法过程中将永远固定在那里，不会再移动！
4. 打包算法 (Bin Packing)
想象你有几个重量不同的物品，想要将它们放进有重量限制的箱子中。这是一个经典的“最优化”问题。
启发式算法 (Heuristic Algorithms)
启发式算法是一种“经验法则”。这种方法能快速找到一个“不错”的解决方案，但不保证能找到“最完美”(optimal) 的方案。当计算完美方案需要耗费计算机多年时间时，我们就会使用这种方法！
你需要知道的三种策略：
- 首次适应法 (First Fit, FF)： 按给定顺序取出每个项目，将其放入第一个有足够空间的箱子中。
- 递减首次适应法 (First Fit Decreasing, FFD)： 首先将项目按递减顺序（从大到小）排列，然后使用首次适应法。这通常会高效得多！
- 填满箱子法 (Full Bin)： 寻找能将箱子刚好装满的物品组合。先处理这些组合，然后再打包剩下的物品。
类比： 首次适应法就像你在超市挑选货品时，直接把物品装进购物袋。而递减首次适应法就像先把你所有的采购物品放在柜台上，在装入巧克力棒等小东西之前，先放进巨大的麦片盒。
你知道吗？ 首次适应法与递减首次适应法的最差情况复杂度都是 \(O(n^2)\)。
5. 算法的证明与修正
我们如何知道一个算法对所有可能的输入都有效呢？我们使用数学证明。
穷举证明法 (Proof by Exhaustion)
如果可能的输入数量很小，你可以简单地测试每一种情况。如果全部测试都成功，则证明该算法对于这组数据是正确的。
反例证明法 (Disproof by Counter-example)
要证明一个算法不正确，你只需要找到一个它失败的特定例子。例如，如果某个打包算法声称总是使用最少数量的箱子，但你发现有一组列表它用了三个箱子而不是两个，那么你就已经证明该算法是错误的！
关键要点： 如果题目要求你“修正 (repair)”一个算法，请寻找逻辑错误发生的步骤——通常是一个“大于”符号应该改为“大于或等于”，或者是一个索引值从 1 开始而不是从 0 开始。
总结：核心要点
- 算法 (Algorithms) 是有限且逻辑清晰的指令集合。
- 复杂度 \(O(n^2)\) 意味着如果输入量倍增，所需时间大约会增加为四倍。
- 快速排序法 (Quick Sort) 使用枢纽来组织列表；它很高效，但在最差情况下为 \(O(n^2)\)。
- 打包算法 (Bin Packing) 使用启发式方法（FF 或 FFD）来寻找“不错”而非“完美”的解决方案。
- 证明： 使用穷举法证明小规模情况；使用反例证明一般规则是错误的。