算法简介-怎样让电脑查字典？

大家应该都听说过“算法（Algorithm）“这个词，从字面理解，就是“计算的方法“。我们之前的文章 --《

3.14 π日 - 用少儿编程工具计算圆周率

》描述的计算圆周率的方法就是算法的一个例子，它是解决一类问题的机械化过程（在文章例子里的问题是计算圆周率）。

我们再从一个简单的例子里来说明一下什么是算法。

大家应该小学开始都会背上面的99乘法表，这时候，你其实只是记住了一组答案，这种知识并不是算法。但是如果你比较“懒”，发现了一些小技巧，比如，计算一个个位数和9的乘积n x 9，它的结果的十位数等于n-1，个位数等于10-n。这种小技巧就是一个算法了！

算法的定义是指一个解决方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

算法的一个特点就是它不需要特别的聪明才智就能执行。它是一个机械化的过程，每一步都按照一个简单的规律接着上一步进行。这个特点看起来是为计算机量身定做的，因为所有的计算机指令分解成最后就是简单的对于数值0或1的运算。执行算法的过程很枯燥，但设计算法的过程却充满趣味和智力挑战，它是计算机科学的一个核心部分。

一些人们自然而然、下意识所做的事情，用算法表达却最为困难。就像我们识别不同的人的本领：婴儿呱呱坠地没多久就能记得谁是妈妈；我们可以毫不费力地分辨出一个熟人和陌生人。但是要用算法来解释这种能力却是非常困难– 当然不是不可能。这种研究人脑思维模式，并使用计算机语言来模拟人脑思维的领域就是人工智能，人工智能算法也是该领域要研究的核心内容。人工智能算法比传统的计算机算法复杂得多，因为它需要应用很多高等数学的内容，但是其本质和一般算法是一样的。

今天我们先来通过学习简单的查找算法，来感受一下算法的特点和作用：

想象一下你现在遇到一个不认识的英语新单词sprung需要查找字典了解它的语义。你有一本41131页的字典，每个单词占一页（这只是个例子，当然真正的字典不会这样）。每个单词都按照字母的先后顺序排列。现在让你写一个小程序去找到这个sprung单词所在的页数。

如果是刚接触计算机的人，自然而然想到的一个方法是从头到尾每一页都检查一遍，看看该页的单词是否等于要查的单词。如果是就结束并返回页数；否则查下一页。指令也很简单，用scratch也很容易做出来：

上面这种方法也是一种算法，姑且无论效率问题，它实实在在地使得我们能够用计算机解决“查找单词”这个问题，并且在很多种情况下这种顺序查找法都能解决问题。

但是，如果我们要查找的东西的数据库很大的话，这种算法的效率显然是很低。一个包含41131个单词的词典，如果要查找最后一个单词的话要执行41131次运算！

大家可以在scratch里实际执行一次上面的代码体验一下查找的速度： 大家可以先从这里（http://qianlima.love:8899/reg_words.txt）下载一个包含41131个英文单词的文件，然后在scratch里建立一个列表，再右键点击列表，选择“导入”，把该文件数据导入到列表里，这样你就在scratch里建立了一个有41131个并且按字母顺序排列的单词组成的列表：

如果你在scratch里执行上面的“顺序查找”程序来查找sprung的话，你会发现它运行非常慢，在我的电脑里它运行了快16分钟才找到sprung！这样的查找算法叫做简单查找，更准确的说法是傻找。它的实用性显然是很有问题的。有没有更好的算法呢？

想象一些你现在手里真的有一本字典，你要查sprung这个单词，你是怎么样翻字典的？你不会真的是从a开始查的对吧，更大可能是直接翻开字典中间的某一页。你打开字典的中间，看到的可能是一个N开头的单词。你知道sprung在N的后面，所以接下来你会从N这一页到字典最后一页中间部分查，依次类推直到最后查到sprung。因为我们知道，这种跳跃式的查找无论如何都比顺序查找快得多。

计算机算法里也有一个很著名的跳跃式查找方法，叫做二分查找法。它的原理如下：

假设现在两个孩子玩一个猜数字的游戏，一个孩子想一个 1到100之间的整数（比如68）让另一个孩子猜。用二分查找法的过程就是：

猜题孩子说：50； 出题孩子说：小了

猜题孩子说：75； 出题孩子说：大了

猜题孩子说：62； 出题孩子说：小了

猜题孩子说：68； 出题孩子说：中了

二分查找法就是每次都从列表的中间位置开始查，如果查找结果比要找的对象小，就先把中间之前的部分排除（上面例子第一步后排除了0-50），再从后面部分的中间位置（50-100的中位数是75）查，依次类推，每次查找都把数据的一半排除掉。

上面的例子里我们找68总共只运行了4次查找；用顺序查找法的话要68次，是不是快多了。

事实上对于1-100之间的任一个整数，用二分查找法都可以在7次之内找到，因为2的7次方 2^7=128(>100)。有同学可能问为什么是7次 -- 你可以用二分查找法尝试2（2^1）以内的所有整数、4（2^2）以内的所有整数，8（2^3）以内的所有整数…来理解这个规律。

每次讨论算法的时候，我们都应该考虑它的效率，就是计算速度的问题。但不同的计算机计算速度不一样，所以不能直接用计算时间来对比。算法效率按习惯一般用大O表示法来表示。这里的O就是Operation(操作)的缩写，代表了操作次数的意思。就是说你这个算法要执行多少次操作。

大O表示法的例子有O(n)，O(log n)，O(n^2)等等。n代表要处理的数据量，对于上面这个例子n就是100：

顺序查找法的运行效率是O(n)，它代表了算法的操作次数和数据量正相关，或者说操作次数随着n线性增长。在上面的例子里，n=10的时候最差情况下需要执行10次操作；n=100的时候最差要执行100次。n和O(n)是1:1的正比关系。在直角坐标系上，O(n)可以用一条直线表示它的增长规律，它的增长速度是不变的。

二分查找法的运行效率是O(log n)，一般省略对数基数，直接用O(log n)表示。它代表了算法的操作次数和数据量对数相关，或者说操作次数随着n对数增长。在上面的例子里，n=10的时候最差情况下需要执行“log 10再向上取整=4“次操作；n=100的时候最差要执行“log 100再向上取整=7“次。对数曲线如下图所示。其特点是随着n的增大其增长却越来越慢。

O(n)和O(log n)的运行效率相差到底有多大呢？

回到我们一开始查字典的例子，如果字典只有10个单词：那么顺序查找的运行次数O(n)就是10；二分查找的运行次数O(log n)是4，顺序查找运行次数只是多一倍而已，看起来相差不大嘛。

但如果是41131个单词的情况呢？顺序查找的运行次数O(n)就是41131；二分查找的运行次数O(log n)是16。顺序查找运行次数多了快2570倍。

想象一下如果现在要在一个保存了全中国14亿人的身份证信息的数据库里查找：顺序查找的运行次数O(n)是1,400,000,000；二分查找的运行次数O(log n)是31。顺序查找运行次数多了45,161,290倍。如果执行一次操作的时间是100毫秒，那么二分查找的最长运行时间是3.1秒，而顺序查找法的最长运行时间是4.44年！

通过这些例子同学们应该可以理解算法效率的重要性了。但是二分查找法的一个问题是它要求数据表必须是按顺序排列的；而顺序查找法就没有这个要求。有没有一种查找算法既不需要数据表按序排列又比较快呢？答案当然是有的，比如哈希表。这个以后有机会再和大家分享。

最后附上用scratch实现的二分查找算法，以及一个小动画来说明用它在41131个单词中查找sprung的过程。

总结一下今天的要点：

算法是指一个解决方案的准确而完整的描述，是解决一类问题的机械化过程。

顺序查找算法和二分查找算法都是查找算法。但是他们的效率相差很远。

算法的运行效率用执行次数来比较，一般用大O表示法来表示。顺序查找算法的运行效率是O(n)，二分查找法是O(log n)。随着n的增大，顺序查找法的运行次数比二分查找法大得越来越多。

算法的学习和研究是非常锻炼逻辑思维和培养解决问题能力的过程，亲手用奇妙的算法解决问题也是非常好玩和有成就感的事情。人工智能领域的算法研究现在还处于初始阶段，需要大量人才。希望热爱科技、热爱编程的同学们能体会到算法的魅力，并在这个领域发光发热。