欢迎来到决策数学 1：算法！
你好！如果你正在学习决策数学，算法就是整个学科的基石。别担心这个术语听起来很复杂；算法（algorithm）其实就是一套极其精确的指令。你可以把它想象成解决特定问题的“终极配方”！
在这一章中，我们将学习如何：
- 理解什么是优秀的算法。
- 逐步跟踪算法（这是考试中的一项关键技能！）。
- 比较不同的排序和搜索方法（例如冒泡排序 vs. 快速排序）。
- 评估算法的效率。
掌握这些概念将帮助你满怀信心地处理未来 D1 的所有课题，从图论到网络流，统统不在话下！
第 1 节：定义与理解算法
什么是算法？
算法是一组有限的、定义明确的指令序列，旨在完成特定任务或解决特定类型的问题。它们是计算机和决策者的“操作指南”。
有效算法的基本特征
要成为一个数学意义上的算法，它必须具备五个关键特征：
- 输入（Input）： 必须接受零个或多个外部量。（例如：一组待排序的数字。）
- 输出（Output）： 必须产生至少一个量。（例如：排序后的列表。）
- 确定性（Definiteness）： 每条指令必须清晰明确，没有歧义。（不留任何猜测空间！）
- 有限性（Finiteness）： 无论输入什么，算法都必须在有限的步骤后终止。（它不能无限运行下去。）
- 可行性（Effectiveness）： 每一步都必须是可行的，且能在有限时间内完成。
类比：想象一下烤蛋糕。如果食谱（算法）没有告诉你面粉具体要用多少（确定性），或者让你烤无限长的时间（有限性），那这就是一个糟糕的算法！
跟踪与流程图
要理解一个算法，特别是在考试中，你必须能够跟踪（trace）它。跟踪（或称“模拟运行”）涉及按照指令一步步执行，记录每个阶段的变量和决策。这通常使用跟踪表（Trace Table）来完成。
流程图中的关键符号
算法通常使用流程图直观地表示：
- 椭圆形： 过程的开始或结束。
- 平行四边形： 输入或输出（获取数据或显示结果）。
- 矩形： 过程或指令（一个动作，例如设定 \(x = 5\) 或计算总和）。
- 菱形： 决策或条件（一个带有两条路径的问题，通常是“是/否”或“真/假”）。
速记要点： 算法是一种精确、结构化且有限的问题解决方法。跟踪就是我们证明它有效的方法。
第 2 节：衡量算法性能（效率）
如果你有两个都能解决相同问题的算法，如何决定哪一个更好呢？你需要比较它们的效率（efficiency）。
效率衡量的是算法所需的资源（通常是时间或内存）如何随着输入数据量（\(n\)）的增加而变化。
时间复杂度的定性分析
在 D1 中，你需要理解一个算法所需的操作数量如何随着处理项的数量 \(n\) 而缩放。
效率（或称阶，Order）由当 \(n\) 变得非常大时在运行时间中占主导地位的项决定。
我们将性能大致分为以下几类（从最好到最差）：
- 对数时间 (\(\log n\))： 所需时间增长非常缓慢。每一步都将剩余的工作量减半。（极其优秀！）
- 线性时间 (\(n\))： 所需时间与项目数量成正比增长。如果你将输入翻倍，时间也翻倍。（良好。）
- 平方时间 (\(n^2\))： 随着输入的增长，所需时间呈指数（二次方）快速增长。如果你将输入翻倍，时间增加为原来的四倍 (\(2^2 = 4\))。（较差，对于大数据集来说简直是灾难。）
为什么这很重要？ 一个 \(n^2\) 的算法对于 10 个条目的列表可能很快，但对于 100 万个条目的列表，\(n\) 或 \(n \log n\) 的算法将远胜于前者。
记忆窍门：始终追求更低的指数或增长率。\(\log n\) 远小于 \(n\)，而 \(n\) 又远小于 \(n^2\)。
\(\log n\) (最快) < \(n\) (中等) < \(n^2\) (最慢)
速记要点： 效率是指随着列表规模增大，算法变慢的速度。我们希望算法具有良好的扩展性。
第 3 节：排序算法
排序算法将列表中的项目按特定顺序（升序或降序）进行排列。
1. 冒泡排序 (Bubble Sort)
冒泡排序是最容易理解的排序算法，但也是最慢的算法之一。它通过重复遍历列表，比较相邻元素，如果顺序错误就交换它们来工作。
冒泡排序过程（升序）
- 第 1 轮（Pass 1）： 从列表开头开始，比较前两项。如果第二项比第一项小，则交换。
- 向后移动一位，比较接下来的两项（第二项和第三项）。必要时交换。
- 继续直到到达列表末尾。最大项会像气泡一样“冒”到列表末尾的正确位置。
- 第 2 轮（Pass 2）： 重复该过程，但在最后停止位置提前一位（因为最后一项已经排好序了）。
- 重复此操作，直到某一轮中没有发生任何交换。
助记：想象一下苏打水里的气泡。最重的物体（最大的数字）会沉到杯底（列表末尾）。
性能： 冒泡排序是一个 \(n^2\)（平方）算法。这使得它在大数据集上非常低效。
常见错误： 学生常忘记在后续轮次中提前停止比较。每一轮都应将未排序部分的列表缩短一个元素。
2. 快速排序 (Quick Sort)
快速排序通常是该级别课程中讲授的最快排序算法。它使用“分而治之（divide and conquer）”的方法。
快速排序过程
- 选择枢轴（Pivot）： 从列表中选择一个元素（通常是第一项）作为枢轴。
- 分区（Partitioning）： 重新排列其余元素，使得所有小于枢轴的元素放在其左侧，所有大于枢轴的元素放在其右侧。此时枢轴已处于最终的正确位置。
- 递归（Recursion）： 对枢轴左侧的子列表和右侧的子列表递归执行上述过程，直到所有子列表包含零个或一个元素（这意味着它们已经排好序了）。
性能： 快速排序通常是 \(n \log n\)，这比冒泡排序快得多。但是，如果枢轴的选择始终很差（例如，每次都选到最大或最小的元素），其最坏情况会退化到 \(n^2\)。
你知道吗？在计算机科学实践中，快速排序常被使用，因为尽管有理论上的最坏情况，但它的平均性能非常出色。
速记要点： 快速排序速度快 (\(n \log n\))，因为它将问题分解；冒泡排序速度慢 (\(n^2\))，因为它反复检查相邻对。
第 4 节：搜索算法
搜索算法用于在列表中定位特定的目标项目。
1. 线性搜索（或顺序搜索，Linear Search）
这是最直观的搜索方法。它只需从头开始，逐一检查列表中的每一项，直到找到目标或列表检查完毕。
要求： 无。列表不需要排序。
过程：
- 从第一个元素开始。
- 将元素与目标进行比较。
- 如果匹配，停止并返回成功。
- 如果不匹配，移动到下一个元素。
- 重复直到列表遍历结束。
性能： 线性搜索是一个 \(n\)（线性）算法。在最坏情况下（目标在末尾或不存在），你必须检查每一项，使时间与 \(n\) 成正比。
类比：在大型超市的每个货架上寻找某一种特定的麦片。
2. 二分搜索 (Binary Search)
二分搜索比线性搜索快得多，但它有一个关键的前提条件。
关键要求：列表必须已经排好序。
二分搜索过程
- 寻找中点： 确定列表中的中间项。
- 比较： 将中间项与目标值进行比较。
- 决策：
- 如果中间项就是目标，停止。成功！
- 如果目标小于中间项，忽略列表的上半部分。
- 如果目标大于中间项，忽略列表的下半部分。
- 重复： 将剩余的一半列表当作新列表重复上述过程（寻找新中点、比较、排除一半）。
二分搜索非常有效，因为它在每一次比较后都能排除掉剩余数据的一半。
性能： 二分搜索是一个 \(\log n\)（对数）算法。这速度极快。如果你有一个 1,000 项的列表，你可以在约 10 步内找到目标 (\(\log_2 1000 \approx 10\))。
常见错误： 试图对未排序的列表使用二分搜索。如果列表未排序，二分搜索将会彻底失败。
排序算法
- 冒泡排序： 简单。比较相邻对。性能：\(n^2\)（慢）。
- 快速排序： 复杂。使用枢轴和递归。性能：\(n \log n\)（平均速度快）。
搜索算法
- 线性搜索： 简单。顺序检查所有项目。性能：\(n\)。
- 二分搜索： 高效。重复折半列表。要求列表有序。性能：\(\log n\)。
结论与最后建议
你已经掌握了算法的基础！请记住，决策数学的核心就是寻找解决问题的最佳方法。效率是关键！
理解这些概念的最佳方法是通过练习：
- 画出冒泡排序的跟踪表，直到它成为你的直觉。
- 练习为快速排序选择枢轴并对列表进行分区。
- 在被要求执行搜索任务时，确保检查“列表是否已排序”这一条件。
继续努力，做得好！