高效算法：聪明地工作，而非努力地工作

欢迎！这一章非常重要，因为它让我们从“写出能运行的程序”，进阶到“写出优质的程序”。你可以这样想：任何人都能开车从伦敦到曼彻斯特，但一位高效的司机知道最快的路线，能避开交通拥堵，并节省时间。

在本节中，我们将学习在解决同一个问题时，如何衡量一个算法是否比另一个“更好”或更有效率。


1. 什么是算法效率？

当我们谈论算法的效率 (Efficiency of an Algorithm) 时，我们是在描述算法使用计算步骤来解决问题的有效程度。

一个高效的算法，是指能用尽可能最少的步骤或运算，达到预期结果的算法。

类比： 想象你需要在巨大的图书馆中找到特定的一本书。

• 低效率的方法： 从第一个书架开始，检查每一本书，直到找到为止。
• 高效的方法： 查看图书馆目录，找到准确的区域和书架编号，然后直接前往。

高效的方法使用的步骤更少，节省了大量时间！

重点总结： 在考试中，算法效率侧重于时间效率 (Time Efficiency)（将执行步骤的数量降至最低）。


2. 衡量时间效率

时间效率衡量的是算法的执行时间如何随着输入数据量的增加而增长。

关键在于，我们不会用秒来衡量时间效率，因为所花费的时钟时间会随计算机硬件速度（CPU）的不同而改变。

相反，我们通过计算算法相对于输入数据量所执行的基本运算或步骤 (steps) 数量（例如比较、计算或赋值）来衡量时间效率。

例子：如果一个算法需要比较两个数字 100 次才能将一个小列表排序，那么它执行了 100 个步骤。如果列表大小增加了 10 倍，它可能需要 1,000 个步骤。

为什么我们计算“步骤”而不是“秒”：

• 如果算法 A 在超级计算机上运行需 5 秒，而算法 B 在基础的学校笔记本电脑上运行需 10 秒，这样的比较并不公平。
• 通过计算步骤（比较、加法、赋值），我们得到了一种与硬件无关的度量标准。我们仅仅是在评估算法本身的质量与逻辑。


3. 影响算法效率的关键因素

可以使用多于一个算法来解决完全相同的问题，但它们的效率可能大相径庭。

A. 输入数据的大小 (The Size of the Input Data)

这通常是决定效率最重要的因素。

定义： 输入大小 (Input Size) 是指算法必须处理的数据量（例如：列表中的项目数量、数据库中的记录数量）。

例子： 在联系人列表中寻找特定姓名。

• 在包含 10 个项目的列表中找名字非常快速，且只需要极少步骤（输入大小小）。
• 在包含数百万个项目的数据库中找名字则需要多得多的步骤（输入大小大）。

一个好的算法即使在输入大小变得极大时，也能妥善管理其步骤。

B. 算法设计的质量

不同的算法方法会导致不同数量的步骤。考虑在列表中寻找项目的两种搜索方法：

1. 线性（顺序）搜索 (Linear (Sequential) Search)： 逐个检查每一项。如果列表有 \(N\) 个项目，在最坏的情况下，它需要 \(N\) 个比较步骤。

2. 二分搜索 (Binary Search)： 这需要列表已排序，但它在每次比较时都会将剩余项目减半。在 100 个项目的列表中找到一个项目最多只需 7 个步骤。

对于已排序的列表，选择二分搜索而不是线性搜索，是瞬间显著提升效率的捷径，因为其算法设计需要的运算少得多。

C. 外部因素（硬件与软件）

虽然我们严格通过计算步骤来衡量算法效率，但在现实环境的执行中，实际耗时（以秒为单位）也会受到以下影响：

• 处理器速度 (CPU)： 更快的计算机能更快执行每个步骤。
• 内存可用性 (RAM)： RAM 不足可能会在执行期间导致延迟。
• 编程语言： 编译型语言执行机器码的速度通常比解释型语言更快。

💡 避免常见错误

不要将计算机的速度与算法的效率混为一谈！无论是在超级计算机还是基础笔记本电脑上运行，高效的算法执行的步骤永远比低效算法少。


4. 为什么选择高效算法很重要？

你可能会问：“我的代码能瞬间完成 10 个数字的排序，为什么还要费心去优化它？”答案是规模！

A. 处理海量数据

现代应用程序需要处理海量数据集——数百万甚至数十亿条信息（例如搜索引擎、社交媒体动态或银行系统）。

如果一个低效的算法处理 1,000 个项目需要 1 秒，那么处理 100,000 个项目可能需要 1,000 秒（超过 16 分钟）。选择更高效的算法能保持处理过程快速且实用。

B. 资源管理与响应速度

• 节省能源： 执行较少指令的算法消耗较少的处理器功耗和电力，从而延长移动设备的电池寿命并减少数据中心的能源消耗。
• 更好的用户体验： 用户期望得到响应灵敏的程序。高算法效率能确保快速的响应时间，并防止应用程序冻结。


5. 关键概念速览

• 多于一个算法可以解决同一个问题。
• 时间效率是通过比较执行步骤/运算的数量来评估的，而不是以秒为单位的原始时钟时间。
• 所需步骤的数量在很大程度上由输入大小和算法设计决定（例如：二分搜索与线性搜索）。