跳转至

1.1   算法无处不在

当我们听到“算法”这个词时,很自然地会想到数学。然而实际上,许多算法并不涉及复杂数学,而是更多地依赖基本逻辑,这些逻辑在我们的日常生活中处处可见。

在正式探讨算法之前,有一个有趣的事实值得分享:你已经在不知不觉中学会了许多算法,并习惯将它们应用到日常生活中了。下面我将举几个具体的例子来证实这一点。

例一:查字典。在字典里,每个汉字都对应一个拼音,而字典是按照拼音字母顺序排列的。假设我们需要查找一个拼音首字母为 \(r\) 的字,通常会按照图 1-1 所示的方式实现。

  1. 翻开字典约一半的页数,查看该页的首字母是什么,假设首字母为 \(m\) 。
  2. 由于在拼音字母表中 \(r\) 位于 \(m\) 之后,所以排除字典前半部分,查找范围缩小到后半部分。
  3. 不断重复步骤 1. 和步骤 2. ,直至找到拼音首字母为 \(r\) 的页码为止。

图 1-1   查字典步骤

图解 1-1:查字典的二分查找过程

在按拼音字母表排序的字典中,查找任意一个首字母为 r 的字。共 5 个画面:第 1 步交代初始范围,第 2 至第 5 步各翻页一次。

每帧从左到右排列 a 到 z 共 26 个字母块。绿色表示仍在查找范围内,青色突出目标 r,浅灰色表示已排除;第 2 至第 5 帧中,下方向上的“一半页码处”指针标出当前翻到的字母。

  1. 明确查字典目标与初始范围

    初始查找范围覆盖 a 到 z 全部 26 个字母,尚未翻页。目标 r 为青色,其余 25 个字母为绿色。

  2. 翻到中间字母 m,排除前半部分

    第一次翻到全书大约一半页码处,指针指向 m。因为 r 在 m 后面,排除 a 到 m,使它们变为浅灰色;剩余 n 到 z 保持彩色,目标 r 为青色。

  3. 翻到剩余部分中间字母 t,排除后半部分

    在剩余区间 n 到 z 内翻到中间位置,指针指向 t。因为 r 在 t 前面,排除 t 到 z。至此,左侧 a 到 m、右侧 t 到 z 都为浅灰色,只剩 n 到 s 保持彩色,其中 r 为青色。

  4. 翻到剩余部分中间字母 p,再排除前半部分

    在剩余区间 n 到 s 内翻到中间位置,指针指向 p。因为 r 在 p 后面,排除 n 到 p。至此,左侧 a 到 p、右侧 t 到 z 都为浅灰色,只剩 q、r、s 保持彩色:q、s 为绿色,r 为青色。

  5. 翻到中间字母 r,完成查找

    在剩余区间 q、r、s 内翻到中间位置,指针指向目标 r,找到首字母为 r 的字,任务完成。这是第 5 步,也是第 4 次翻页。画面仍保留绿色的 q、s 和青色的 r,表示本次翻页前的范围;a 到 p 与 t 到 z 仍为浅灰色。

查字典这个小学生必备技能,实际上就是著名的“二分查找”算法。从数据结构的角度,我们可以把字典视为一个已排序的“数组”;从算法的角度,我们可以将上述查字典的一系列操作看作“二分查找”。

例二:整理扑克。我们在打牌时,每局都需要整理手中的扑克牌,使其从小到大排列,实现流程如图 1-2 所示。

  1. 将扑克牌划分为“有序”和“无序”两部分,并假设初始状态下最左 1 张扑克牌已经有序。
  2. 在无序部分抽出一张扑克牌,插入至有序部分的正确位置;完成后最左 2 张扑克已经有序。
  3. 不断循环步骤 2. ,每一轮将一张扑克牌从无序部分插入至有序部分,直至所有扑克牌都有序。

图 1-2   扑克排序步骤

图解 1-2:用插入排序整理扑克牌

将 5 张红桃牌分成已排序区与未排序区,逐张插入,使牌面按点数从小到大排列。

初始顺序为 [4, 2, A, 5, 3],A 按点数 1 计算。先把最左端的 4 划入已排序区;随后每次从未排序区最右端取牌,依次取出 3、5、A、2。

6 组牌由 5 支箭头按顺时针 U 形相连:上排从左到右,再沿右侧向下,最后下排从右到左。每组左侧浅绿色区域表示已排序,右侧浅红色区域表示未排序;初始只有未排序区,末组只有已排序区。

六组牌的动作与分区状态
阶段与位置本阶段动作已排序(从左到右)未排序(从左到右)
1,左上初始手牌空[4, 2, A, 5, 3]
2,中上将最左端的 4 划入已排序区[4][2, A, 5, 3]
3,右上取出 3;3 小于 4,插入 4 前面[3, 4][2, A, 5]
4,右下取出 5;5 大于 4,插入末尾[3, 4, 5][2, A]
5,中下取出 A;A 小于 3,插入最前面[A, 3, 4, 5][2]
6,左下取出 2;A 小于 2 且 2 小于 3,插入两者之间[A, 2, 3, 4, 5]空

单张牌自身有序。每次插入后,左区继续保持升序,右区少一张牌;直到未排序区为空,整手牌便排好。图中直接展示各次插入的结果,没有逐一展开比较或临时移动。

上述整理扑克牌的方法本质上是“插入排序”算法,它在处理小型数据集时非常高效。许多编程语言的排序库函数中都有插入排序的身影。

例三:货币找零。假设我们在超市购买了 \(69\) 元的商品,给了收银员 \(100\) 元,则收银员需要找我们 \(31\) 元。他会很自然地完成如图 1-3 所示的思考。

  1. 可选项是比 \(31\) 元面值更小的货币,包括 \(1\) 元、\(5\) 元、\(10\) 元、\(20\) 元。
  2. 从可选项中拿出最大的 \(20\) 元,剩余 \(31 - 20 = 11\) 元。
  3. 从剩余可选项中拿出最大的 \(10\) 元,剩余 \(11 - 10 = 1\) 元。
  4. 从剩余可选项中拿出最大的 \(1\) 元,剩余 \(1 - 1 = 0\) 元。
  5. 完成找零,方案为 \(20 + 10 + 1 = 31\) 元。

图 1-3   货币找零过程

图解 1-3:贪心找零

每步选取不超过当前剩余金额的最大面额,直至待找零金额归零。

购买 69 元商品并支付 100 元,需找回 31 元;可选纸币面额为 20、10、5、1 元。

每次选择前后的剩余金额
选择前余额(元)本次面额(元)扣除后余额(元)
312011
11101
110

每次都选择不超过余额的最大面额:余额 11 元时排除 20 元;余额 1 元时排除 20、10、5 元。最终用 20、10、1 元各 1 张,共 3 张,5 元未使用。

本图展示这组输入下的贪心选择过程,不表示对任意面额组合都能得到最少张数。

在以上步骤中,我们每一步都采取当前看来最好的选择(尽可能用大面额的货币),最终得到了可行的找零方案。从数据结构与算法的角度看,这种方法本质上是“贪心”算法。

小到烹饪一道菜,大到星际航行,几乎所有问题的解决都离不开算法。计算机的出现使得我们能够通过编程将数据结构存储在内存中,同时编写代码调用 CPU 和 GPU 执行算法。这样一来,我们就能把生活中的问题转移到计算机上,以更高效的方式解决各种复杂问题。

Tip

如果你对数据结构、算法、数组和二分查找等概念仍感到一知半解,请继续往下阅读,本书将引导你迈入数据结构与算法的知识殿堂。

欢迎在评论区留下你的见解、问题或建议