Algorithms

👋 欢迎来到算法的世界！

各位未来的决策数学家（Decision Mathematicians）们，你们好！本章将带你进入“算法”这一激动人心且实用性极强的领域。别担心“算法”这个词听起来很深奥，它其实就是一个结构化的方案或一套指令的“高级说法”。

在决策数学（D1）中，我们使用算法来高效地解决复杂的现实问题——比如寻找最快路线、安排任务计划，或是组织处理海量数据。掌握这些概念对于我们后续要处理的所有网络和优化问题至关重要。

---

第1节：定义算法

到底什么是算法？

你可以把算法想象成一份食谱。如果你想烤一个蛋糕（这是“输出”），你需要特定的配料（这是“输入”），以及一套清晰、有序的步骤（这就是“算法”）来将这些配料转变成最终产品。

用数学和计算的术语来说：

• 算法是一系列有限且定义明确的指令，旨在执行特定任务或解决特定问题。

优秀算法的特征

要成为一个合格的算法，必须具备以下四个核心属性：

1. 有限性（Finiteness）： 算法必须在执行有限步之后停止。它不能无限循环下去。
2. 清晰性/精确性（Clarity/Precision）： 每一个步骤都必须清晰、无歧义且定义准确。（不能出现像“烤到看起来不错为止”这种模糊的指令。）
3. 输入（Input）： 算法必须接受零个或多个指定的量作为输入数据。
4. 输出（Output）： 算法必须产生一个或多个指定的结果作为输出数据。

你知道吗？ “Algorithm”（算法）一词源自9世纪波斯数学家花拉子米（Muḥammad ibn Mūsā al-Khwārizmī）的名字。

---

第2节：衡量效率

在决策数学中，算法能用还不够，还必须运行得快。效率指的是算法解决问题的速度，通常用相对于输入规模的操作数或比较次数来衡量。

时间复杂度和数量级

我们通常使用数量级（Order of Magnitude，即大O符号/Big O Notation，你只需要理解其基本分类即可）来衡量效率。它描述了当数据集大小 \(n\) 增加时，所需时间是如何增加的。

情况1：线性时间复杂度 — \(O(n)\)

如果一个算法与输入规模 \(n\) 呈线性关系，我们就说它是 \(O(n)\) 的。

• 含义： 如果你将输入数据的大小翻倍（例如从10个增加到20个），所耗费的时间大致也会翻倍。
• 例子： 如果你有一个包含 \(n\) 个名字的列表，需要逐一检查每个名字来找到特定的人，那么步骤数就与 \(n\) 成正比。

情况2：二次时间复杂度 — \(O(n^2)\)

如果一个算法的运行时间与输入规模的平方成正比，我们就说它是 \(O(n^2)\) 的。

• 含义： 如果你将输入数据的大小翻倍（从10个增加到20个），所耗费的时间会增加 \(2^2 = 4\) 倍。对于大型数据集，这种算法会变得非常缓慢。
• 例子： 如果你有一个包含 \(n\) 个项目的列表，并且对于每一个项目，你都要将其与列表中所有其他项目进行比较。

类比： 想象一下整理图书馆。
如果你使用 \(O(n)\) 的方法，你只需要看每本书一次。
如果你使用 \(O(n^2)\) 的方法，对于每一本书，你都要反复将其位置与*所有其他书*进行核对。

输入规模 (\(n\))	\(O(n)\) 的步骤数	\(O(n^2)\) 的步骤数
10	10 步	100 步
100	100 步	10,000 步
1000	1,000 步	1,000,000 步

关键结论： 当处理大数据集时，\(O(n)\) 效率的算法要远比 \(O(n^2)\) 的算法好得多。

---

第3节：排序算法

排序算法用于将项目列表（数字、名称等）排列成特定顺序（升序或降序）。你需要能够执行并分析以下两种方法。

1. 冒泡排序（Bubble Sort）

冒泡排序是最简单的排序算法，但也是处理大型列表时最慢的。它的原理是反复遍历列表，比较相邻元素，如果顺序错误就交换它们。当某次完整的遍历过程中没有发生任何交换时，算法停止。

冒泡排序流程（升序排列）

1. 从列表开头开始，进行第1轮遍历（Pass 1）。
2. 比较第一个元素和第二个元素。如果顺序错误，则交换它们。
3. 移向下一对（第二个和第三个元素），重复比较和交换。
4. 重复此过程直到到达列表末尾。最大的未排序元素会像气泡一样“浮”到列表末尾的正确位置。
5. 记录该轮遍历中总共进行的交换次数。
6. 如果交换次数为零，说明列表已排好序，算法终止。
7. 如果发生了交换，则开始第2轮遍历，重复步骤2-5，但不需要再次检查列表末尾已排好序的项目。

示例：对列表 [4, 1, 3, 2] 进行排序

• 开始： [4, 1, 3, 2]
• 第1轮：
  • (4, 1) -> 交换 -> [1, 4, 3, 2]
  • (4, 3) -> 交换 -> [1, 3, 4, 2]
  • (4, 2) -> 交换 -> [1, 3, 2, 4]（4已归位）
  总交换次数：3。
• 第2轮：
  • (1, 3) -> 无交换 -> [1, 3, 2, 4]
  • (3, 2) -> 交换 -> [1, 2, 3, 4]（3已归位）
  总交换次数：1。
• 第3轮：
  • (1, 2) -> 无交换 -> [1, 2, 3, 4]
  总交换次数：0。停止。

效率说明： 在最坏和平均情况下，冒泡排序通常是 \(O(n^2)\) 的算法，因为它通常需要嵌套循环（一个循环用于轮数，另一个用于每轮内部的比较）。

2. 快速排序（Quick Sort）

对于大规模数据，快速排序是一种高效得多的方法，它使用了“分而治之（divide and conquer）”的策略。

快速排序流程

1. 选择基准（Pivot）： 从列表中选择一个元素，称为基准（pivot）。（在D1考试中，基准通常选择中间项，或三个数中的中位数）。
2. 分区（Partition）： 重排列表，使得所有小于基准的元素排在左边，所有大于基准的元素排在右边。
3. 子排序： 对基准左侧和右侧的子列表递归应用快速排序算法，直到每个子列表只剩下一个元素。

使用指针的分区步骤（D1标准方法）

我们通常使用两个指针，一个从左侧开始（L），一个从右侧开始（R）。

示例：排序 [5, 1, 8, 3, 9, 2]（基准=8，即中间元素）

1. 设置：
   列表：[5, 1, 8, 3, 9, 2]
   L从5开始，R从2开始，基准=8。
2. 寻找L和R：
   • L向右移动，直到找到大于或等于基准的元素。（L停在8）。
   • R向左移动，直到找到小于或等于基准的元素。（R停在2）。
3. 比较L和R：
   • 如果L的位置在R的左侧（\(L < R\)），则交换L和R指向的元素。
   • 如果 \(L \ge R\)，说明该轮遍历完成，基准已处于正确位置。
   在示例中，虽然从数值上看L(8)大于R(2)，但从位置上看：L处于第3位，R处于第6位。
   让我们重新运行指针逻辑：L找 \(\ge 8\)，R找 \(\le 8\)。
   [5, 1, 8, 3, 9, 2]
   L从5开始，R从2开始，基准=8。
   L越过5, 1，停在8。
   R越过2, 9, 3，停在2。
   由于L的位置（第3位）小于R的位置（第6位），交换它们：
   列表变为：[5, 1, 2, 3, 9, 8]。
4. 重复： 继续寻找L和R并交换，直到 \(L \ge R\)。

快速排序的效率说明

快速排序在平均情况下通常是 \(O(n \log n)\) 的算法，是速度最快的排序算法之一。在最坏情况下（例如基准总是列表中的最大或最小值），它会退化为 \(O(n^2)\)。这就是为什么选择一个好的基准非常重要。

---

第4节：搜索算法

搜索算法帮助我们在列表（项目集合）中找到特定的项（目标项）。

二分查找（Binary Search）

二分查找是一种在列表中查找目标项的高效方法，但它有一个关键前提：列表必须已经排好序。

二分查找流程（折半原理）

该算法通过反复将搜索区间折半来工作。

1. 寻找中间值： 确定列表的开始、结束和中间位置的元素。
2. 比较： 将目标项与中间元素进行比较。
3. 决策：
   • 如果目标等于中间元素，停止（成功！）。
   • 如果目标小于中间元素，舍弃列表的后半部分（从中间元素及其之后的全部）。将新的终点设为中间元素之前。
   • 如果目标大于中间元素，舍弃列表的前半部分。将新的起点设为中间元素之后。
4. 重复： 使用新的、更小的列表段重复上述步骤，直到找到目标或搜索区间为空（即目标不在列表中）。

示例：在有序列表 [5, 10, 15, 20, 25, 30, 35] 中查找 25

• 第1步： 起点=5，终点=35。中间元素是20。
• 第2步： 25大于20。舍弃 [5, 10, 15, 20]。
• 第3步： 新列表段：[25, 30, 35]。新中间元素是30。
• 第4步： 25小于30。舍弃 [30, 35]。
• 第5步： 新列表段：[25]。新中间元素是25。
• 第6步： 目标(25)等于中间元素(25)。找到了！

二分查找的效率说明

二分查找效率极高，分类为 \(O(\log n)\)。因为搜索空间每一步都会减半，即使对于庞大的列表，它也只需要很少的步骤。

类比： 如果你在500页的字典里查一个词，你不会从第1页开始翻。你会大致翻开中间位置（第250页）。根据首字母，你立刻排除掉了一半的字典，从而在很少的尝试中找到单词。