不插电的计算思维之“为对话而搜索”（下）

算法有多快

让我们回到鲍比的算法上。我们肯定使事情得到了改善，新的算法肯定比我们最初的办法要好，可是一个显而易见的问题是——这个算法到底有多快，用它来写那本书要花多长时间。这是我们有可能做到的的最佳方式吗？还是我们能想到更好的算法，能帮鲍比更容易的把那本书写出来。

我们需要一个测量方法去试验一下一个算法有多好。也许我们可以通过用不同的算法来传达一些特定的文字来测试每种算法需要的时间，我们可以花大量的时间找不同的人进行测试得出平均值，但是这会花费大量时间和精力。

有一个更好的办法。我们可以运用“分析思维”来做这件事，我们会运用简单的数学方法解出答案。

我们先不考虑时间，我们来想一想我们要做的事情。如果我们数清楚每猜出一个字母助手需要说的字母的数量，我们就可以把“猜出一个字母需要多少时间”这个问题变成“猜出一个字母需要说多少个字母”这个新问题了。

这样做，我们其实是运用了“抽象思维”，这也是计算思维的一部分，通常被用来简化问题。抽象的意思其实是“隐藏部分细节”，这种想法被用于计算的各个环节来使问题变得更容易。在这里，我们用“猜出一个字母需要说的字母的数量”来抽象代替“猜出一个字母需要花费的时间”。

所以我们要做的事情是弄清猜出一个字母到底需要说多少个字母。我们需要问几个问题，最简单的就是：看一下最好的情况是什么样，为了把书写出来，助手最少可能要说多少个字母。还要看看最差的情况是什么样，如果我们很不幸，情况会有多糟糕。最后我们看一下平均情况是什么样，这可以让我们对实际花费的时间有一个真实的估计。

最好和最差

为了便于讨论，我们这里只讨论字母表上的26个字母，不讨论阿拉伯数字、标点符号等等。如果这本书的内容是“ZZZZZZZ……”,那么用“按从A-Z的顺序让助手读字母”的算法，每猜出一个字母都需要说25个字母，这是最糟糕的情况。最好的情况是书的内容是“AAAAAA……”,那么每猜出一个字母只需说1个字母就可以了。当然书的内容不会是最好的情况也不会是最差的情况，也就是说实际每猜出1个字母平均需要说的字母数量在1-25之间。

“1-25”这个范围似乎过于大了，其实情况可以变得更简单。我们可以把26个字母分成13组字母，“A-Z”“B-Y”“C-X”等等。想一想在一段长长的文字中，每有一个“A”,都能在接下来的文字中找到一个“Z”，猜出一个“A”(需要说的字母数量是1)和一个“Z”（需要说的字母数量是25），所以每猜出一组“A和Z”需要说的字母数量总共是26，其他字母组“B和Y”“C和X”“D和W”等也是这样，那么这样算的话，平均猜出一个字母的需要说的字母数量是13。用全书内容包含的字母数乘以13，再乘以助手每说一个字母花费的时间，就能得出写完整本书所需的大致时间了。

鲍比的改进，先问常见单词的做法，使事情得到了改善。按鲍比的做法，每猜出一个字母需要说的字母大概是9-10个。通过使用字母出现的频率，我们能更精确地猜出鲍比要说的字母，但是最糟糕的情况依然还是要说25个字母才能猜对。

然而正如任何一个计算机科学家了解的，我们可以做得好的多。仅用5个问题猜出一个字母是可能的。可以保证，不是平均需要问5个问题，而是最多需要问5个问题。

五次之内猜出字母

无论你能否想出问题的答案，我保证你一定知道问题所属的正确类别。来做一个“20个问题”的儿童游戏，游戏内容是我想出一个名人，你来猜这个名人是谁。难点在于我每次只会告诉你“Yes”或“No”。和朋友一起玩一玩这个游戏。

这个游戏可能的过程是这样的：

A：是女性吗？

B：No

A: 还活着吗？

B：No

A：是电影明星吗？

B:  No

A：是来自亚洲吗？

B：No

A：是来自印度吗？

B：Yes

A：是甘地吗？

B：Yes

机会就是当你在玩这个游戏的时候，你也问类似的问题。你当然不太可能会问这样的问题：是阿黛尔吗？是博尔特吗？是女王吗？ 那样的话你永远不能在20个问题内猜对答案。你应该问“问完之后你能更清楚这个人是谁”这一类的问题。所以你该先问“是女性吗”这种问题。

为什么这种问题是好问题呢？因为无论答案如何，它都能排除一半的可能性。假设我们从100万名人中选一个，那问完第一个问题后，还剩50万人。问完第二个，剩250000;第3个，剩125000，第4个大约剩64000，这样问下去，问完第10个问题，就只剩1000人了，问完第19个问题，就只剩大约2人了，所以最多问20个问题就能猜出正确的答案。因此，如果你能问出完美的二等分式的问题，你肯定能赢。

通过正确的提问，最多用20个问题就可以从100万个选项中找到答案。想一想，“是不是A” “是不是B”这类问题和“是不是阿黛尔” “是不是博尔特”这类问题是一样的。

一种新算法

“问题转化思维”又来啦，如果是同样的问题，那同样的策略就能让我们想出更好的解决方案。对于字母表里的字母来说，什么是等效的方法呢？我们需要每次把字母表等分。显而易见第一个问题是“是在N之前吗？“，下一个问题取决于前一个问题的回答。如果第一个回答是“Yes”,接下来我们就问“是在F之前吗？”如果第一个回答是“No”,接下来我们就问“是在T之前吗”，依次类推，无论答案是哪个字母，我们都能只用5个问题就一定可以得到答案。

我们还可以运用频率分析的技巧让速度变得更快。我们可以英文字母把按照使用频率的高低，分为高频词（使用频率最高的7个字母ETAONRI）和低频词（频率较低的19个字母SHD LFCMU GYPWB VKJXQ Z）。那么按照二等分的算法去问，第一次提问“是高频词吗”，如果回答是“Yes”，第二次提问“是在O之前吗”，如果回答是“Yes”第三次提问“是在T之前么”，如果回答是“Yes”,答案就是E。

通过把字母分为高频词和低频词后，任意一个高频词只需提问3次就能得到答案，任意一个低频词需要提问5次就能得到答案。算法速度再次得到了提升。

搜索算法

我们的算法能够起作用是因为猜人名和猜字母这两个问题的本质相同，本质上它是一个“搜索问题”：在一系列给定的东西中，找到我们想找的那个特定的东西。解决这个问题的方法叫“搜索算法”。这是一个找东西的必定成功的方法。第一种方法，按照逐一核对的形式（是不是A？是不是B？是不是C？……）去核实每个可能答案，这是一种叫作“线性搜索”的算法。有时候这是你能采取的最好的做法。例如，如果你目睹了一次抢劫，警方安排了一次列队认人，那你最好的做法就是线性搜索——依次核对每张脸直到在队伍中找到那个你看到的抢劫犯。

当你在一堆无序的东西中搜索时，线性算法非常好用。如果你要在一列抽屉里找一件针织衫的话，那就从最上面的抽屉开始一个个地翻吧。

我们的另一种算法涉及发现二等分问题：是在N之前吗？他是女性吗？发现二等分问题是一个通用的问题解决策略，叫“分治”，也就是分而治之。如果你能想出一个问题的分治解决办法，那就很有可能像用重复等分的办法得到一个答案那样快，会比一次核对一个东西的方法快得多得多。

最简单的分治搜索算法被称为“对分搜索”。试想一下，把你要从中进行搜索的东西们按顺序排列好，一头是最小的，另一头是最大的。对分搜索是先去核对目标搜索对象是在中间那个东西的前面还是后面，排除一半的可能性，接下来在剩下的东西中再重复这种做法，一直重复到只剩一个东西——这个东西就是你要找的。这和你从一个超大的电话号码簿里找一个特定的名字类似，你肯定不会从第一页开始一个个地查下去，一直查到你要找的名字。

搜索算法不只“线性搜索”和“对分搜索”这两种。例如， Google是如何在一秒之内搜索完全球每个网页页面的？它当然要有一个更好的算法。搜索算法充分利用了另一种抽象方法，我们从特定问题中抽象出细节并将这个问题视为一个搜索问题。这样我们的搜索算法就成了一个可用于解决很多问题的现成方案。

换个方式思考这个问题，一旦我们能想出一个策略在“用20个问题猜出任意一个名人的名字”这个问题上取胜，我们也就能够把这个策略概括为分治法,这样一来，我们就有了一个适用于其他问题的通用策略。

算法思维优先

然而需要注意的事情是我们我们根本没有着眼于科技。我们一直在讨论两个人的“对话”。我们想出来了一个好办法，一个好算法，现在我们可以思考如何使用适当的科技将算法自动化。我们可以搭建一个眼球追踪系统，用来观察眨眼的次数，也许可以用一个电极帽来检测鲍比想说“Yes”还是“No”。

关键是无论我们使用什么科技，在科技背后都要有一个算法。选错了算法，无论使用的科技有多好，交流都会很慢，解决同样的问题要问13次而不是5次。无论助手是一个计算机还是人类。 如果我们没有先考虑算法，我们可能会设计出一个很糟糕的慢吞吞的系统。计算并不是关于科技的，而是关于计算思维的，计算思维是用来想出一个很棒的解决方案的。

​