第 2 章 积跬步,致千里

第 2 章 积跬步,致千里

我做的第一件事情,

是查看什么东西被糟蹋了,

什么东西没有被损坏。

——《鲁滨逊漂流记》

 

2.1 高中

2.1.1 泰朵拉

“学长!”

我回头望向这响亮又清脆的声音的源头。

这里是我就读的高中,现在已经放学,我走在墙面写有“肃静”的走廊的正中间。

“泰朵拉,声音太大了。”我提醒道。

泰朵拉上高二,是比我低一年级的学妹。她身材娇小、充满活力,非常可爱。就是有时候会活跃得过了头,显得冒冒失失的。

“啊,是哦,抱歉。”她不好意思地抓了抓自己的短发。和平时一样的交谈,和平时一样的泰朵拉,和平时一样的 —— 啊不对,在她的身后,站着一位素未谋面的红发少女。

红色的头发。

我的视线瞬间被她的头发吸引,它像火焰一样红,长度刚好及肩。发型简单利落没有过分修饰,给人一种野生动物的感觉。

“学长,这位是今年刚入学的理纱。”泰朵拉说道。

哦哦,原来是四月份 1 刚入学的新生呀。

1日本四月、九月开学,其中四月为升学季。—— 译者注

那就比泰朵拉还低一级,是学妹的学妹。嗯……泰朵拉总给人一种“永远都是一年级”的印象,两人站在一起,有种说不出来的违和感。

面对泰朵拉的介绍,红发新生毫无反应,没有露出微笑,也没有点头。面孔虽然俊俏却毫无表情。她没有戴眼镜。我看着她心想:真是个奇怪的女生。

“请多关照。”我冲她打招呼,“你的名字是?”

红发少女依旧面无表情,用微微沙哑的声音回答道:

“双仓理纱。”

2.1.2 理纱

图书室。

理纱、泰朵拉,还有我,我们三人并排坐着。理纱面对着轻薄型的笔记本电脑,手指在键盘上敲打个不停。她的电脑有着鲜红的外壳,像是为了搭配自己的红发而特意挑选的。理纱自始至终一言不发,即便泰朵拉“嗨!”地上去搭话,她也只是朝这边看一眼,马上又把头转向屏幕,其间敲打键盘的手指也没有停歇。不看屏幕也可以继续打字,真厉害呀。

“话说回来,‘双仓’是‘双仓图书馆’的‘双仓’吗?”我问理纱。

理纱默不作声地点了点头。

“就是那个‘双仓’!”回答我的是泰朵拉,“理纱可是那个双仓图书馆的双仓博士家的大小姐呀。”

“是这样啊。”我说着又重新开始打量理纱,但理纱并没有理睬我们,只是继续着她和电脑的对话。话题依然没有展开,尴尬的沉默弥漫在空气中。

“……对了,上高二的心情是怎样的?”我问泰朵拉。

“嗯……想在新的学期,开始一个新的计划!”泰朵拉“唰”地握紧双拳。

“新的计划?”

“嗯,我决定开始学习算法了。”

“算法?”我向泰朵拉确认,“算法,好像是指计算机进行运算的步骤来着?”

“嗯,是的。算法指的是为了通过输入求得需要的输出而制定的明确的步骤。这个步骤在大多数情况下是由‘计算机先生’通过程序运行的。”

泰朵拉兴致勃勃地继续解释。

“算法有以下几个特征:有输入、有输出、步骤明确。还有……还有……诶?抱歉,应该还有两个特征来着,我忘记了……总、总之,算法最重要的就是有明确的步骤。”

“这样啊。”我不是很了解算法,虽然读过几本与程序相关的书,但都不太对我的胃口,“所以,你要学习算法喽?”

“是的,其实之前就已经学习过一些程序相关的知识了,然后前几天村木老师问我要不要试着接触算法,他还给了我‘顺序查找’的卡片呢。”

“顺序查找?”

我顺口一问,泰朵拉就调皮地笑了出来。

“原来我也有被学长请教的时候呀。顺序查找是……”

2.1.3 顺序查找

顺序查找是查找算法中的一种,可以按顺序查找数列中是否存在特定的数。呃……虽然能查找的东西并不局限于数,但为了说明方便,这里我们来进行数的查找。

嗯,现在我来举个例子,比如说有这样一个数列。

{31,41,59,26,53\}

在这 5 个数中……就假设我们要查找 26 这个数吧。要是由人来查找,只要看一眼就能够找到 26。但是计算机先生只能一个一个地检查。顺序查找指的就是“从第一个开始按顺序来查找”这样一种算法。

遵循顺序查找算法来查找 26 的情形是这样的。

◎  ◎  ◎

“但是,这不是一目了然的嘛。”我说。

“没错,我一开始也是这么认为的。但是 —— ”说到这,泰朵拉噗嗤一声笑了出来,“我们要从理所当然的地方开始思考问题……对吧?”

“……说得对。”

  “我们要从理所当然的地方开始思考问题。”

这是我曾对泰朵拉说过的话,她记得真牢啊。

以前总是我给泰朵拉学妹讲课、回答数学疑问、协助解数学题。但是今天反了过来,我向泰朵拉请教,这让我有种新鲜的感觉。

“比如说,我们有 100 万个数。”泰朵拉像喷泉那样将双手“哗”地打开,“要是有那么多的数,即使是按顺序一个个检查这种简单的工作,人类也只能束手无策。但是,只要将算法转化为程序并输入到计算机中,计算机先生就能胜任这份工作。”

“诶……泰朵拉你学得好认真呐。说起来,泰朵拉你说过想从事计算机相关的工作呢 —— 不过,我对算法的印象还是很模糊呀。”我说。

“那我们把顺序查找算法好好地总结归纳一下……”

泰朵拉一边说着,一边拿出一张卡片。

顺序查找算法(输入与输出)

输入

  • 数列 A={A[1],A[2],A[3],\cdots,A[n]\}
  • 数列的大小 n
  • 要查找的数 v

 

输出

A 中找到与 v 相同的数时,

  输出“能找到”。

A 中未找到与 v 相同的数时,

  输出“无法找到”。

“我们进行顺序查找时……”泰朵拉解释说,“只要提供 n 个数组成的数列 A={A[1],A[2],A[3],\cdots,A[n]\} 以及数 v,便可以利用顺序查找算法从数列 A 中找出 v。也就是说,输入是 An 还有 v。”

“嗯嗯。”我点点头,紧接着问道,“A[1],指的就是 A_1 吗?”

“是的,没错。在这里代替数学上

A_1,A_2,A_3,\cdots,A_n

的写法,改用

A[1],A[2],A[3],\cdots,A[n]

这样的写法。A[1] 表示数列 A 中的第 1 个数。”

“嗯,我明白了。”我说。

“向顺序查找算法中输入数列 A、数列大小 n,以及要寻找的数 v。接下来……如果算法在 A 中发现了与 v 相等的数,则输出‘能找到’,未能发现时则输出‘无法找到’。也就是说,输出是‘能找到’或者‘无法找到’。”

“原来如此。输出是表示算法运算的结果呀。”

“嗯,是的。因此,顺序查找算法的流程 2 就可以像这样表示。”

2流程,在程序设计语言中也叫“过程”“函数”或“方法”。—— 译者注

泰朵拉又拿出一张卡片。

顺序查找算法(流程)

“这里使用伪代码表示算法的流程。”

“伪代码?”

“嗯。伪代码不是真正的代码,而是一种形似程序的语言,英文是 pseudocode。虽然计算机先生不能直接运行这种用伪代码表示的流程,但是用伪代码就可以以程序的形式表示算法了。”

“哦?”

“村木老师说‘不同的书表示算法的方法千差万别,但无论哪一种表示方法,都必须能明确表示出从输入到输出的各个步骤。’”

“原来如此……那么,这就是顺序查找算法了吧。”

“是的。用一句话来表示顺序查找算法就是‘按照 A[1],A[2],A[3],\cdots,A[n] 的顺序判断是否有与 v 相等的元素’。”

“从行 L1 开始看这个流程对吧?”

“嗯嗯。”泰朵拉不住地微微点头,并接着说道,“老师是这样说的,‘请运行行 L1 至行 L10 的各个步骤’。”

“运行……?”

泰朵拉重新看了看笔记本,慢慢地继续话题。

“嗯,按照村木老师的说法,先想象自己变成了计算机先生,然后再去运行代码会更好。

  • 大喊‘我是计算机’
  • 想象自己被给予了算法与输入
  • 然后,按照流程笨拙、踏实地一步一步运行

不得不说这很麻烦,但据说这样是理解算法最快的方法。”

“是吗……”

“我要试试老师说的,我特别喜欢这种毅力定胜负的比拼。接下来,人家要变成计算机了!”

“真是台干劲十足的计算机呀。”我说道。

“泰朵拉计算机,启动。”理纱轻轻说道。

2.1.4 逐行调试

从现在开始,我们要利用一个测试用例 —— 具体的输入 —— 来一步一步地运行顺序查找算法的流程,这叫作逐行调试该算法。逐行调试的英文为 walk through,也就是“一步一步运行”的意思。

测试用例如下,算法的输入为:

\begin{cases}A={31,41,59,26,53\}\\n=5\\v=26\end{cases}

也就是从

A[1]=31,A[2]=41,A[3]=59,A[4]=26,A[5]=53

这 5 个数中通过顺序查找算法来查找 26 这个数。

 

  从行 L1 开始运行顺序查找算法的流程。

\underline{\textcircled{1}~{\rm L1}:\mathbf{precedure}~{\rm LINEAR-SEARCH}(A,n,v)}

  这一行的意思是:名为 LINEAR-SEARCH 的流程即将开始。流程用英语表示为 procedure。此外,这一行还表示该流程被给予了输入 Anv

  接着运行下一行 L2。

\underline{\textcircled{2}~{\rm L2}:k\leftarrow 1}

  在这一行,我们将变量 k 赋值为 1。运行这一行后,变量 k 的值变为 1。

    变量 k 表示我们正在注视数列中的第 k 个数。

  接着运行下一行 L3。

\underline{\textcircled{3}~{\rm L3}:\mathbf{while}~k\leqslant n~\mathbf{do}}

  在这一行,我们将判断循环的条件。关键字 \mathbf{while} 表示,在满足条件期间,循环运行从 \mathbf{while}\mathbf{end-while} 的各行。此处的条件为“k\leqslant n”。

    因为变量 n 表示数列的大小,所以条件 k\leqslant n 表示“将注视的位置限定在数列的范围内”。严格来说条件应该为 1\leqslant k\leqslant n,但因为变量 k 从 1 开始增加,所以只要将 k 的上限设为 n 即可。

  此时,因为 k=1,n=5,所以满足条件 k\leqslant n

  因为满足条件,接着运行下一行 L4。

\underline{\textcircled{4}~{\rm L4}:\mathbf{if}~A[k]=v~\mathbf{then}}

  在这一行,我们将判断条件。关键字 \mathbf{if} 表示,只有满足条件时,流程才会运行从 \mathbf{if}\mathbf{end-if} 的各行。此处的条件为 A[k]=v

    条件 A[k]=v 表示“正在注视的数与要查找的数相等”。

因为此时 k=1,根据输入的数列得出 A[k]=A[1]=31,即 A[k]=31,而 v=26,不满足条件 A[k]=v

    数列的第 1 个数并不是我们想要查找的数。

  因为不满足条件,所以直到 \mathbf{end-if} 的所有行都要跳过。

  这样,我们“嘣”地就跳到了行 L7。

\underline{\textcircled{5}~{\rm L7}:k\leftarrow k+1}

  在这一行,我们将式子 k+1 赋值给变量 k。当前 k=1,因此式子 k+1 的值为 2,变量 k 的值由 1 变为 2。

    这样,我们注视的位置就向后移动了一位。

  接着运行下一行 L8。

\underline{\textcircled{6}~{\rm L8}:\mathbf{end-while}}

  这一行的 \mathbf{end-while} 与行 L3 的 \mathbf{while} 相对应。

  现在返回至行 L3。

◎  ◎  ◎

“泰朵拉,你真是用心学习了啊。”我佩服地说。

“有、有吗……”泰朵拉支支吾吾,脸红红的。

“你穿插着解释了形式和含义,也就是程序字面上的意思和算法的思想,这样的讲解方式非常有趣。”

“啊……”面对突如其来的夸奖,泰朵拉好像不知道说什么好。

“但是,还是觉得好麻烦啊。”我一边说,一边看着泰朵拉的笔记本,上面详细记录着伪代码的说明。

“确实呢。不过只要下定决心,一边记录变量的值,一边按部就班地运行,也没有那么麻烦啦……”

“Continue。”理纱说。

◎  ◎  ◎

\underline{\textcircled{7}~{\rm L3}:\mathbf{while}~k\leqslant n~\mathbf{do}}

  回到行 L3,重新判断循环条件。

  现在,因为 k=2,n=5,所以满足条件 k\leqslant n

  接着运行下一行 L4。

\underline{\textcircled{8}~{\rm L4}:\mathbf{if}~A[k]=v~\mathbf{then}}

  再一次判断条件,现在变量 k 的值等于 2,不满足条件 A[k]=v,因为此时 A[2] 作为输入其值为 41,而 v 的值为 26。

    数列的第 2 个数也不是我们想要查找的数。

  因此,我们跳过行 L5 和行 L6,直接转到行 L7。

\underline{\textcircled{9}~{\rm L7}:k\leftarrow k+1}

  变量 k 的值再次增加 1,现在变量 k 的值变为 3。

  接着运行下一行 L8。

\underline{\textcircled{10}~{\rm L8}:\mathbf{end-while}}

  再一次回到行 L3。

◎  ◎  ◎

“重复做同一件事情呢。”我说。

“嗯。”泰朵拉接着说,“但是 k 的值增加了吧。”

“Continue。”理纱的语气毫无起伏。

◎  ◎  ◎

\underline{\textcircled{11}~{\rm L3}:\mathbf{while}~k\leqslant n~\mathbf{do}}

  现在,因为 k=3,n=5,所以满足条件 k\leqslant n

  接着运行下一行 L4。

\underline{\textcircled{12}~{\rm L4}:\mathbf{if}~A[k]=v~\mathbf{then}}

  现在 k=3,不满足条件 A[k]=v,因为此时 A[3] 作为输入其值为 59,而 v 的值为 26。

  跳转至行 L7。

\underline{\textcircled{13}~{\rm L7}:k\leftarrow k+1}

  变量 k 的值变为 4。

  接着运行下一行 L8。

\underline{\textcircled{14}~{\rm L8}:\mathbf{end-while}}

  再一次回到行 L3。

◎  ◎  ◎

“还在重复做同一件事情呢。”我说。

“嗯。”泰朵拉接着说,“但是,k 的值在增加啊。”

“Continue。”理纱的语气依旧毫无起伏。

◎  ◎  ◎

\underline{\textcircled{15}~{\rm L3}:\mathbf{while}~k\leqslant n~\mathbf{do}}

  现在 k=4,满足条件 k\leqslant n

  接着运行下一行 L4。

\underline{\textcircled{16}~{\rm L4}:\mathbf{if}~A[k]=v~\mathbf{then}}

  现在 k=4,条件 A[k]=v 成立!因为 A[4] 的值与 26 相等,我们终于满足了 \mathbf{if} 的条件。

  向行 L5 前进。

\underline{\textcircled{17}~{\rm L5}:\mathbf{return}}“能找到”

  \mathbf{return} 是表示本流程输出的关键字。我们将运行结果设置为“能找到”,然后跳转至行 L10:\mathbf{end-procedure}

\underline{\textcircled{18}~{\rm L10}:\mathbf{end-procedure}}

  至此,LINEAR-SEARCH 流程结束。

好,就像这样,经过从 \textcircled{1} \textcircled{18} 总共 18 个步骤,算法运行完成。由输入的值 A={31,41,59,26,53\},n=5,v=26 得到的输出为“能找到”。

◎  ◎  ◎

“真是辛苦啊。”我说。

“呼……是啊。”泰朵拉说,“仅仅是为了判断‘在 {31,41,59,26,53\} 中是否存在 26’,就要下这么一番工夫,变量 k 的值也在流程运行过程中改变了很多次,真是烦琐。”

“那么具体的动作是怎样的呢?”

“嗯,现在我们按逐行调试时的运行顺序给各行标上序号,就像这样。这便是旅行的足迹,对吧!”

逐行调试顺序查找算法

(输入为 A={31,41,59,26,53\},n=5,v=26

“原来如此……”

“计算机先生真厉害!无论重复多少遍相似的工作也不会厌倦。”

“呃,其实我觉得泰朵拉你的毅力也很值得钦佩。”我说。

“泰朵拉计算机。”理纱说。

2.1.5 顺序查找算法分析

“话说回来……村木老师是不是想让你把这个当作研究课题呢?”

“啊!说得对呀!”泰朵拉迅速回应了我的疑问。

村木老师经常给我们卡片。卡片上有时会有“请求解 ○○”这样的问题,但大多数卡片上写的不是问题,而是数学相关的素材。老师的意思是让我们自由思考,去发现有趣的性质。这和课堂作业里出现的试题完全不同,我们在卡片的引导下自己出题,自己解题。

我从高一开始就一直和村木老师进行着这样的交流,久而久之养成了自己动手动脑解决问题的习惯 —— 不只是解决现有问题,还会尝试自己出题。

但是泰朵拉这次给我讲解的卡片与以往都不同,我完全找不到数学素材,只能找到像 k\leqslant nA[k]=v 这种简单的数学公式而已。

“那个……”我问泰朵拉,“我已经明白了顺序查找算法,可接下来要做什么呢?这张卡片能让我们提出怎样的问题呢?”

我无意识地望向理纱那边。在我和泰朵拉谈话的过程中,她的手一直没有离开键盘,灵巧的手指在键盘上飞舞。

“嗯……”泰朵拉眨着水灵的眼睛,“我们试着提高算法的运行速度怎么样?算法的目的是得到输出,速度当然是越快越好。”

“原来如此。”我点着头,“但是泰朵拉……顺序查找算法就是从数列的第 1 个数开始按顺序比较的方法,我们真的能让它运行得更快吗?而且怎样才能测出写在纸上的步骤的运行速度呢?”

“啊,说的也是呢……”泰朵拉小声嘟囔着。

“运行次数。”理纱说。

我和泰朵拉看向理纱,而理纱转过脸,没有表情地看着我们,敲键盘的手指依然没有停歇。

“运行次数……是什么?”我问理纱。

“按行计算。”

红发少女继续敲打着键盘。理纱的言语细微处混杂着些沙哑的音色,但不会让人觉得不舒服,反而有一种富有质感的魅力。她略带沙哑的嗓音,让我对她所说的一字一句都感到印象深刻。

“是指可以按行计算出运行次数么?”泰朵拉说,“嗯……因为刚才 \mathbf{end-procedure} 的标号是 \textcircled{18} ,一共运行了 18 步,运行步数为 18。”

“但是,18 这个结果仅局限于刚才的测试用例,对吧。”

“什么意思?”

“看,根据输入的不同,在数列 A 中存在可以查找到 v 的情况,也存在查找不到 v 的情况。可以查找到的情况又分为:在数列前端找到,在数列末端找到。这么多的情况,我们没有办法明确分出来呀。”

“啊……”

“而且,输入中的 n 也是一样。就像泰朵拉刚才说的那样,n 可能等于好几百万,再加上数列中未必存在 v,这么多情况下的运行步数我们怎么数得过来呢。”

“说、说的也是……”

2.1.6 顺序查找算法分析(能找到 \boldsymbol{v} 的情况)

理纱默不作声地将电脑转向我们,屏幕上显示着如下所示的伪代码,每一行都标着用 1 或 M 表示的运行次数。

能找到 \boldsymbol{v} 时顺序查找算法的运行次数

M 是什么?”泰朵拉问理纱。

v 的位置。”理纱简洁地回答。

“原来如此。”我看着整理好的算法说道,“原来是标注了从 L1 到 L10 每一行各自运行的次数啊……”

是啊!

在数学上经常应用这个方法啊。如果存在多种情况无法确定循环次数,用变量来表示就好了呀。导入变量 M 也就是

  通过导入变量进行一般化。

“但是接下来该怎么做呢?”泰朵拉问。

“只要将各行的运行次数求和,不就可以求得整体的运行步数了嘛!”我说,“这个式子应该含有变量 M。”

能找到 v 时顺序查找算法的运行步数

\begin{aligned}&={\rm L1+L2+L3+L4+L5+L6+L7+L8+L9+L10}\\&=1+1+M+M+1+0+(M-1)+(M-1)+0+1\\&=M+M+M+M+1+1+1+1-1-1\\&=4M+2\end{aligned}

“也就是说,在能找到 v 的情况下,只要运行 4M+2 步就可以得到输出!”泰朵拉说。

“没错。比如说,泰朵拉提到的测试用例要查找 26,这时……”

“我来我来!我来算!”泰朵拉一下子提高了音量,“验算,对吧!”

“嗯,没错。”我和泰朵拉都清楚,推导出普遍公式后应该做的事情 —— 用具体的例子验算。

“在刚才的测试用例 {31,~41,~59,~26,~53\} 中,我们已经验证了能找到 26 这个数。26 为数列中第 4 个数,所以 M=4。”

“哦哦。”

“不出所料,结果为运行 4M+2=18 步后流程结束吧。”

“嗯,这样就求出了:在能找到 v 的情况下流程的运行步数为 4M+2。那么下一个问题自然是,在数列中—— ”

“无法找到 v 的情况下,流程的运行步数是多少?”

泰朵拉接着我的话说道。

问题 2-1(顺序查找算法的运行步数)

在数列 A={A[1],A[2],A[3],\cdots,A[n]\} 中无法找到 v 时,顺序查找算法的运行步数是多少呢?

2.1.7 顺序查找算法分析(无法找到 \boldsymbol{v} 的情况)

理纱再一次将电脑屏幕转向我们。

无法找到 \boldsymbol{v} 时顺序查找算法的运行次数

“啊,这次没出现 M 呢。”泰朵拉说。

“这个……各行的运行次数正确吗?”

我思考着。

显而易见,行 L1 与行 L2 的运行次数是一次。

但是,行 L3 的运行次数真的是 n+1 次吗?不应该是 n 次吗?—— 不不,确实是 n+1 次。因为首先在 k\leqslant n 成立的情况下,k 能取到 1,2,3,\cdots,n,一共要运行 n 次。接着,在 k\leqslant n 不成立的情况下还有 k=n+1 时的 1 次。相加得 n+1 次,这就是行 L3 的运行次数 —— 理纱脑筋转得真快啊。

“L3 = L2 + L8。”理纱说。

这是什么意思……算了,接着往下看吧。

行 L4 呢?在找不到 v 的情况下,必须比较从 A[1]A[n]n 个数。因为比较操作要在行 L4 进行,所以这一行的运行次数为 n 次,的确合情合理。

行 L5 的话……嗯,因为没有输出“能找到”,所以行 L5 和行 L6 的运行次数都是 0 次。

行 L7 和行 L8 的运行次数与行 L4 的运行次数相等,都是 n 次。

行 L9 则一目了然。因为输出“无法找到”后流程结束,所以行 L9 和行 L10 的运行次数都是 1 次。

嗯,全部正确。

泰朵拉开始在纸上计算。

无法找到 v 时顺序查找算法的运行步数

\begin{aligned}&={\rm L1+L2+L3+L4+L5+L6+L7+L8+L9+L10}\\&=1+1+(n+1)+n+0+0+n+n+1+1\\&=n+n+n+n+1+1+1+1+1\\&=4n+5\end{aligned}

“这样就完成了分情况讨论,对吧?”泰朵拉总结道。

原来如此。用数学公式表示会让人心里踏实呢……是啊,只要能像这样用数学公式来表示运行步数,就可以利用思考数学问题的方法去思考计算机问题了。我曾一度认为计算机和程序与数学毫不相关,现在看来未必是那样的。

解答 2-1(顺序查找算法的运行步数)

在数列 A={A[1],A[2],A[3],\cdots,A[n]\} 中无法找到 n 时,顺序查找算法的运行步数是 4n+5

2.2 算法分析

2.2.1 米尔嘉

“呀!”

一直保持高冷,不停敲打键盘的理纱突然像小狗一样发出了可爱的叫声。

紧接着传来干净清澈的声音。

“理纱,好久不见。”

少女的长发乌黑亮丽。

身材高挑修长。

脸上架着金属框眼镜。

指尖像指挥家一样挥动着。

那是聪明机敏又健谈的数学少女 —— 米尔嘉。

米尔嘉是我的同班同学。自高中入学时那个“樱花树下的邂逅”3以来,我们便一同学习。话虽如此,我完全琢磨不透她的数学功底到底有多深厚。

3见《数学女孩》1.1 节。—— 译者注

她懂得很多,是一位靠得住的队长,领导我们在名为数学的旅途上前进。但她的魅力远不止于此。

我……

我看着米尔嘉,心里有些难受。

无论是我,还是她,都已经高三了。这是我们在高中的最后一年。

米尔嘉毕业后……算了,还是别去想了。

“快停下啦。”理纱说。

米尔嘉站在那里,用手来回揉理纱的头发,理纱的头发已经变得乱蓬蓬的。

“快停下,米尔嘉学姐。”理纱拨开米尔嘉的手,稍微清了下嗓子。

“啊,米尔嘉,这位是小理纱。”泰朵拉说。

“不要加‘小’。”理纱又摆回一张扑克脸。

“我知道的。”米尔嘉说,“理纱是双仓博士的女儿。”

2.2.2 算法分析

“嗯……算法分析吗?”

米尔嘉从理纱身后探出头来,看着屏幕。

理纱无声地点头。

“求解算法的运行步数……”米尔嘉一边环视着我们一边说,“它的确是算法分析的第一步。但是……”

理纱抬起头。

米尔嘉顿了顿,继续说道。

“但是,用它来求解算法的运行时间,必须要明确前提条件。为了能根据运行步数来判断算法的速度,前提条件中必须给出运行每一步要花费的时间。否则怎么谈论速度快慢都没有意义。”

原来如此,的确是这样。

“这是为了确定计算模型。”米尔嘉继续说明,“在理纱使用的计算模型中,运行各行所消耗的时间都相等。也就是说,前提条件为:无论是‘k\leftarrow 1’还是‘\mathbf{if}~A[k]=v~\mathbf{then}’,其所花费的时间都相等。这个计算模型虽然简单,但却很实用。”

“计算模型……”我小声嘀咕。

“米尔嘉学姐!”泰朵拉提了提音量,“话说回来,您清楚算法的特征吗?有输入、有输出、步骤明确,还有两个是……”

“输入、输出、确定性、可行性、有穷性。”米尔嘉立刻回答道,“不过,也存在没有输入的情况。”

“确定性指的是步骤有明确定义是吧。可行性指的是?”

“可行性指的是该算法的操作 4 可以实际运行。”

4直译是“步骤”,此处按照计算机教材的用法写作“操作”。—— 译者注

“哦哦……那么有穷性是?”

“有穷性指的是算法的运行时间是有限的。”

“原来如此。输入、输出、确定性、可行性、有穷性……”泰朵拉记在了笔记本上。

2.2.3 不同情况的归纳

米尔嘉重新检查泰朵拉的笔记本。

“嗯……”

“我们通过分情况讨论求得了运行步数!”泰朵拉说。

听了泰朵拉的说明,米尔嘉轻轻合上眼睛。这时大家也都安静下来,连容易冒冒失失的泰朵拉也不出声地看着米尔嘉,而理纱 —— 从一开始就很安静。过了一会儿,米尔嘉左右摆动着食指睁开眼睛。

“在这里 —— ”不知为什么,米尔嘉好像很开心,“在这里,你们分情况分析了顺序查找算法。将情况分为在数列 A 中能找到 v 的情况,以及在数列 A 中无法找到 v 的情况。这没有问题。但是,我们可以将这两种情况归纳为一种情况。”

“将两种情况……归纳?”我有些疑惑。

泰朵拉见缝插针地举手。即便对方就在眼前,她也会举手提问。

“请、请问,归纳指的是归纳能找到 v 的情况与无法找到 v 的情况吗?”

“对。”米尔嘉说。

“但是,这两种情况下的输出也不一样,即便说要归纳也……”泰朵拉一边看着笔记本一边说。

“正因为无法归纳,才要分情况讨论的啊。”我补充道。

米尔嘉走到理纱旁边,悄声耳语几句。理纱露出一副嫌麻烦的表情,过了一会儿才在键盘上敲打起来。

“这并不是什么难以理解的问题,是这么一回事。”配合着米尔嘉的话,理纱把红色笔记本电脑的屏幕转向我们。

归纳能找到 \boldsymbol{v} 与无法找到 \boldsymbol{v} 两种情况后顺序查找算法的运行步数

“出现了新的变量 S 呢。”泰朵拉谨慎地说道。

“这是‘通过导入变量进行一般化’。”米尔嘉说,“一般化指的是将多种特殊情况归纳为一种情况。我们在这里导入变量 S,根据两种情况,取不同的值定义该变量。”

  • S=1,表示能找到 v 的情况。

    此时 M 等于 v 在数列中的位置。

  • S=0,表示无法找到 v 的情况。

    此时 M 等于 n

“为什么用 S 这个字母来表示呢?”泰朵拉问。

“变量取任何名字都没问题,不过这里的 S 是‘Successful’的‘S’,表示成功找到了 v。对应于‘在数列 A 中能找到 v’这一命题的真与伪,变量 S 的取值分别为 1 比特的 1 与 0。”

“原来如此……变量 S 的值为 1 时表示‘能找到 v’,S 的值为 0 时表示‘无法找到 v’。”我说。

“通过增加一个变量,可以归纳多种情况。”米尔嘉说。

“我们归纳了多种情况……换句话说,我们就能用一个式子来表示顺序查找算法的运行步数了!”我说。

泰朵拉立刻开始计算。

顺序查找算法的运行步数

\begin{aligned}&={\rm L1+L2+L3+L4+L5+L6+L7+L8+L9+L10}\\&=1+1+(M+1-S)+M+S+0+(M-S)+(M-S)+(1-S)+1\\&=4M-3S+5\end{aligned}

2.2.4 思考意义

泰朵拉认真地在笔记本上计算,过了一会儿,抬起头说:“4M-3S+55 的验算也没问题。”接着又说:“嗯……我还有个可能有些奇怪的问题,像 S 这种变量,是可以随意决定的吗?总感觉有点……机会主义的味道。”

“可以。”米尔嘉立即回答。

“变量的意义并非含糊不清,也没有产生什么矛盾。”我对泰朵拉说,“我们只是将其定义为一个表示特定值的变量。”

“与其介意增加了一个变量,不如来讨论变量的‘意义’,后者有趣得多。”米尔嘉说。

“变量的……意义?”泰朵拉露出惊讶的表情。

“你去那边。”米尔嘉指着对面的座位,示意我把泰朵拉旁边的位置空出来。

“好的。”我立刻给米尔嘉大人让出座位。

“请听题。S=1M 的值代表什么?”米尔嘉提问。

“我来答。M 是要查找的数 v 的位置。”泰朵拉回答。

“不够严谨。”米尔嘉说。

“诶!”泰朵拉吃了一惊。

“诶!”我也吃了一惊

“……”理纱毫无反应。

“比如说,要是在 {31,\underline{26},59,\underline{26},53\} 这样一个数列中查找 v=26 呢?”

“哦哦……原来要查找的数 v 未必只在一个地方出现。”泰朵拉恍然大悟地点点头。

“没错。如果断言 Mv 的位置,就等于先入为主地假定 v 只会在数列中出现一次。正确的说法是,M 为‘v 的位置中最小的一个’。”

“但是,反复强调‘最小的一个’很麻烦呀。”我说。

“的确。”米尔嘉承认,“重要的是,我们绝对不能忘记‘实际上有存在多个 v 的可能性’。”

“嗯。”泰朵拉说。

“下一题。S 的意义是什么?”米尔嘉向泰朵拉问道。

“我知道!这刚刚说过。S 是表示‘能否在数列中找到 v’的变量。”

“答成这样就可以了。我们一般把用‘1 或 0’来表示‘某命题是否成立’的变量或式子称为指示器。变量 S 就是指示器。”

“是 indicator 吗?”

“是的,也可以说 indicator variable。”

“‘indicate 的东西’……也就是‘指示的东西’,它究竟指示什么呢?”泰朵拉来回晃着食指问道。

S 指示‘能找到 v’这个命题。”

“……”泰朵拉陷入了思考。

“下一题。1-S 的意义是什么?”

1-S 吗?呃……对了,它是表示‘能找到 v 时为 0,无法找到 v 时为 1’的式子,对吧?你看,1-S 这个式子在 S=0 时为 1,在 S=1 时为 0。1 与 0 正好颠倒过来,就像这样。”泰朵拉将手掌来回翻转。

“很好。1-S是‘无法找到 v’的指示器。”

“啊!”泰朵拉恍然大悟,“这也是指示器!”

“下一题。M+1-S 的意义是什么?”

M+1-S 吗?”

泰朵拉麻利地在笔记本上写下来,然后开始思考。

我也开始思考。

  • S=1 时,M+1-S 等于 M

    也就是等于 v 的位置 —— 严格来说,是 v 的位置中最小的一个。

  • S=0 时,M+1-S 等于 M+1

    指的是……

指的是……嗯,究竟该怎么说比较好呢?

S=1 时,M+1-S 表示 v 的位置。”米尔嘉说,“但是在 S=0 的情况下呢?”

v 后面的位置吧。”我说。

“学长……”泰朵拉说,“‘v 后面的位置’这种说法不合理吧,因为在 S=0 的情况下根本找不到 v 呀。”

“啊,是哦。”被泰朵拉指出疏忽了条件一事,是我大意了。

S=0 时,M+1-S 表示什么?”泰朵拉反复念叨。

n+1。”理纱小声说。

“没错。”米尔嘉对理纱说,“S=0 时,M 等于 n。因此,M+1-S 等于 n+1。”

“抱歉!你们现在在做什么呢……我有点被绕晕了。”泰朵拉说。

“呼……”

米尔嘉站起身来,慢慢走过我们的座位。春天温暖轻柔的风吹过,数学少女的长发摇曳不停,柑橘系的芳香沁人心脾。

M+1-S 这个式子很有趣。”米尔嘉一边走一边说,“M+1-S,在 S=1 时与 v 的位置相等,在 S=0 时等于 n+1。那么,能否将这两种情况归纳为一种呢。也就是说,能否认为式子 M+1-S 在任何情况下都等于 v 的位置呢?”

“但是米尔嘉,在 S=0 时,v —— ”我提醒着。

“没错,在 S=0 时,v 不存在于 A[1],A[2],A[3],\cdots,A[n] 中。既然这样,我们强行 v 存在A[n+1] 就好了。”

“强行……让 v 存在?”我搞不明白。

“这样一来,M+1-S 便总是与 v 的位置相等。”米尔嘉接着淡淡地解释,我依旧一头雾水。

“其实 M+1-S 的两种形态可以表示为一个事物。”

“一个事物啊……”泰朵拉说。

我的记忆被勾了起来……那到底是什么时候的事情啊。

  当我们注意到两种不同的表现在本质上是一个事物时,便会有绝妙的事情发生。

哨兵。”理纱的发言打断了我的回忆。

“是的,如理纱所说,就是哨兵。理纱快,来这边。”米尔嘉向理纱招手示意。

“不。”理纱简洁地拒绝。

“呃……哨兵,到底指的是什么呀。”泰朵拉还是一头雾水。

2.2.5 带有哨兵的顺序查找算法

米尔嘉对理纱耳语几句,理纱随即开始敲击键盘。说起来理纱打字真是快啊,而且打字的时候基本没有什么声音 —— 无声地输入。

过了一会儿,完成输入的理纱给我们展示“带有哨兵的顺序查找算法”。

带有哨兵的顺序查找算法(流程)

我们全都盯着笔记本电脑屏幕,苦苦思索着。

看了好一会儿,泰朵拉叫道:“不动笔的话怎么也弄不明白!”接着就在笔记本上写了起来。看来泰朵拉计算机启动了。

“通过测试用例来具体算一下吧。”米尔嘉说。

逐行调试带有哨兵的顺序查找算法

(输入为 A={31,41,59,26,53\},n=5,v=26

“通过逐行调试发现,S4 → S5 → S6 这三行在不断地循环。”泰朵拉说,“感觉带有哨兵的顺序查找算法在判断条件时比普通的顺序查找算法简单很多啊……对了,哨兵到底指什么?”

“指的是在 S2 行放在 A[n+1] 中的数。”米尔嘉回答,“只要把 v 放在 A[n+1] 中,当 k=n+1 时就一定能找到 v,因此,查找就不可能越过这里继续进行。为了防止不小心运行过头而设置的数,这就是哨兵,英文为 sentinel。有哨兵存在的话,在 S4 的 \mathbf{while} 处便不再需要确认 k 的范围。”

“之前的 LINEAR-SEARCH 算法的运行步数是 18,这次的 SENTINEL-LINEAR-SEARCH 算法的运行步数是 16。可以说是稍微……变快了点吧,但是仅仅节约了两步呀……”

“这只是个示例。我们需要将行 S4 的运行次数设为 M,将 S 设为‘能找到 v’的指示器,一般化地求带有哨兵的顺序查找算法的运行步数。”

带有哨兵的顺序查找算法的运行步数

  • S=1,表示能找到 v 的情况。

    此时 M 等于 v 在数列中的位置

  • S=0,表示无法找到 v 的情况。

    此时 M 等于 n

带有哨兵的顺序查找算法的运行步数

\begin{aligned}&={\rm S1+S2+S3+S4+S5+S6+S7+S8+S9+S10+S11}\\&=1+1+1+(M+1-S)+(M-S)+(M-S)+1+S+0+(1-S)+1\\&=3M-3S+7\end{aligned}

“普通的顺序查找算法的运行步数是 4M-3S+5。”泰朵拉一边看着笔记本一边说,“而带有哨兵的顺序查找算法的运行步数是 3M-3S+7 !”

“原来如此!”我喊出声来,“只要用数学公式来表示运行步数,就能比较算法的速度了。”

“要比较对吧!我来写不等式!”泰朵拉说。

“用不等式直接比较二者的大小当然没有问题。”我说,“不过还可以采用一种常规方法 : 计算‘左边 - 右边’这个式子,判断它的结果是否大于 0。”

顺序查找算法的运行步数 - 带有哨兵的顺序查找算法的运行步数

\begin{aligned}&=(4M-3S+5)-(3M-3S+7)\\&=4M-3S+5-3M+3S-7\\&=M-2\end{aligned}

“哦哦……”泰朵拉说。

“因此,只要 M-2>0,我们就能认为带有哨兵的顺序查找算法更快。”我说。用数学公式表达思路,真是让人放心啊。

M-2>0 等价于 M>2。如果 v 在数列 A 中第一次出现的位置在 3 之后,带有哨兵的顺序查找算法就会更快。”

“原来用数学公式表达后还能有这样的发现呀!”泰朵拉豁然开朗。

“‘无法找到 v’的情况是最耗时间的,顺序查找算法的运行步数是 4M-3S+5=4n+5,带有哨兵的顺序查找算法的运行步数是 3M-3S+7=3n+7。这就是各个算法的最大运行步数吧。”我说。

2.2.6 创造历史

米尔嘉一边转着我的自动铅笔一边说:

“顺序查找算法的运行步数是 4M-3S+5,带有哨兵的顺序查找算法的运行步数是 3M-3S+7。也就是说,加上哨兵后,运行步数变为原来的 \frac{3}{4} 左右。”

\frac{3}{4} 是怎么得出的呢?”

M 的系数的比值。”米尔嘉说,“当 M 变得很大时,可以将 4M-3S+5 看作 4M,将 3M-3S+7 看作 3M。”

“快了大约 25%。”理纱补充道。

米尔嘉接着说:

“先明确前提条件,再求算法的运行步数,这样我们就能够定量评估算法的速度。如果能定量评估,便能得出像‘快了大约 25%’这样的具体数值,而不是仅仅停留在‘很快’的层面上。通过定量评估,我们就能够有理有据地区分算法的优劣。”

“原来如此。”我说。

“明确了前提条件的定量评估,不仅能被某一个人利用,还能被其他人利用、验证、改良,甚至可以用于其他算法的分析。”米尔嘉说。

“‘明确了前提条件的定量评估’……这、这就像创造历史一样啊。”泰朵拉想入非非,“即便评估的人不在了,其他人……未来的人也可以使用。自己的思想,超越自己留存下去 —— 这是对人类的贡献啊!”

“泰朵拉,真了不起啊。”我不由得感叹泰朵拉思想的广度。

“只是,有一点需要注意。”米尔嘉竖起食指说,“要是像用显微镜那样将注意力全部放在算法的细微差异上,就会忽视大的共同点。要妥善处理这个问题,可以使用渐近分析的方法。分析复杂问题的时候,我们要—— ”

“顺序查找算法是 O(n) 5的。”理纱打断了米尔嘉。

5O(n)) 的读法有:欧·恩、大欧·恩、big o en、order en,等等。

“你是理解了 O(n) 的意思才这么说的吗?”米尔嘉紧接着问道。

理纱沉默了一会儿,小声回答:

“……不是。”

米尔嘉面前的理纱像小狗一样。

“不过是说出了一知半解的单词啊。”

噢哟,这挑衅的话语。

理纱紧紧地瞪着米尔嘉。

米尔嘉用冰冷的眼神回应。

“那、那个……”泰朵拉不知所措。

无声地对视了好一会儿,理纱咂了咂舌,错开了视线。

几乎没人能瞪得过米尔嘉。

“放学时间到了。”

噢,拳击场的铃声响了……啊不,是图书管理员瑞谷老师的提醒。瑞谷女史 6总是在放学时间准时通知学生回家。通知完后,女史朝我们这边瞄了一眼,回到了管理员办公室。

6女史,我国古代记录皇后礼仪、后宫事务的女官,日本古时从事文书工作的女官。日本今天还在使用这个词,是对知识女性的尊称。—— 译者注

2.3 自己家

笨拙的一步

夜晚,我在家里独自思考。

今天,我觉得自己稍稍抓住了算法的诀窍。能通过明确可运行的操作在有限的步数内根据输入求得输出,这就是算法。

非常有毅力的泰朵拉仔细地帮我逐行调试了顺序查找算法。踏踏实实地一步一步运行算法虽然笨拙,但对于理解算法是非常有帮助的。今天还学到了通过利用数学公式表示运行步数来分析算法。

米尔嘉教会了我“明确了前提条件的定量评估”和“通过导入变量归纳多种情况”。即便是结果一目了然的算法,仔细研究还是会有新的发现啊。

话说回来,数学公式的力量真是强大。数学公式支撑着定量评估,只要能落实到数学公式上,无论是评估、比较还是判断都能迎刃而解。

还有,红发少女理纱 —— 双仓博士的女儿,擅长无声快速打字。她今天用“哨兵”回答了米尔嘉的问题。理纱之前就知道哨兵这回事,想必一定是自学了很多东西吧。

啊啊,学校教给我们的还是太少了,必须自己学习才行,必须自己主动去吸收知识。

泰朵拉、米尔嘉,还有理纱。

她们都各有各的长处。

和她们相比,我 —— 自惭形秽。

不!不行!我不能这样胡思乱想!

快想起和米尔嘉的约定!

我……摘下眼镜,左手轻轻扶住脸颊。

我现在上高三,准备读大学。

  我想学一些真真正正的知识。

  我想踏踏实实地做一番事情。

我笨拙的努力将被名为

“高考”的测试用例定量评估,合格为 1,不合格为 0。这个指示器是多么沉重的 1 比特啊。

我一边想着,一边重新戴上眼镜,展开笔记本。

那么,今晚也 ——

踏出笨拙的一步吧。

 

有幸为自己的毕生事业起名的人屈指可数。

但是,在 20 世纪 60 年代,

我认为有必要创造“算法分析”这一名字,

因为现存的任何用语都无法贴切表达我想做的事情。

—— 高德纳 7

7出自 Selected Papers on Analysis of Algorithms 第 ix 页。

泰朵拉的笔记(伪代码)

定义流程

用 〈流程名〉 定义以 〈参数列表〉 为输入的流程。

赋值语句

将 〈表达式〉 的值赋值给 〈变量〉。

赋值语句(交换值)

交换 〈变量 1〉 与 〈变量 2〉 值。

if 语句(1)

  1. 判断 〈条件〉 是否成立。
  2. 〈条件〉 成立时,运行 〈操作〉,前进至 \mathbf{end-if} 行。
  3. 〈条件〉 不成立时,直接跳转到 \mathbf{end-if} 的下一行。

if 语句(2)

  1. 判断 〈条件〉 是否成立。
  2. 〈条件〉 成立时,运行 〈操作 1〉 ,跳转到 \mathbf{end-if} 行。
  3. 〈条件〉 不成立时,运行 〈操作 2〉 ,前进至 \mathbf{end-if} 行。

换言之,〈操作 1〉 和 〈操作 2〉 中必有且只有一个被运行。

if 语句(3)

  1. 判断 〈条件 A〉 是否成立。
  2. 〈条件 A〉 成立时,运行 〈操作 1〉,跳转到 \mathbf{end-if} 行。
  3. 〈条件 A〉 不成立时,判断 〈条件 B〉 是否成立。
  4. 〈条件 B〉 成立时,运行 〈操作 2〉,跳转到 \mathbf{end-if} 行。
  5. 当 〈条件 A〉 和 〈条件 B〉 都不成立时,运行 〈操作 3〉,前进至 \mathbf{end-if} 行。

换言之,〈操作 1〉〈操作 2〉〈操作 3〉 中必有且只有一个被运行。

while 语句

  1. 判断 〈条件〉 是否成立。
  2. 〈条件〉 成立时,运行 〈操作〉,前进至 \mathbf{end-while} 行,然后回到 \mathbf{while} 〈条件〉 \mathbf{do} 行。
  3. 〈条件〉 不成立时,直接跳转到 \mathbf{end-while} 的下一行。

return 语句(运行结果)

  1. 求 〈表达式 〉 的值,将其作为流程的运行结果(输出)。
  2. 跳转到 \mathbf{end-procedure} 行,结束流程的运行。

目录