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

大家应该都听说过“算法(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的增大,顺序查找法的运行次数比二分查找法大得越来越多。

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180614G25FJD00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券