深入浅出学算法: MIT花生酱三明治实例
什么是算法?
作为一名程序员,拥有大量可使用的工具非常重要的。其中可能会包括编程语言、文本编辑器、程序包等。而最重要的是,要对现有的各种类型的算法有深刻的了解。这些都会成为技术面试和工作中最重要的一套工具。如果你想了解更多数据分析相关内容,可以阅读以下这些文章:
评估机器学习算法的指标
推荐系统(Recommender Systems)各算法原理概述
算法教练谈谈码工面试
对于那些不了解的人来说,算法并不是一个很难理解的概念。算法就是一种定义简单明确、逐步解决问题的方法。比如,在很多计算机科学的课上都有一个练习,要求学生解释怎样制作一个花生酱和果酱三明治。可能你会震惊,这个练习过程就是一种算法。
麻省理工学院(MIT)的夏令营课中提供了这个算法的答案:
- 1. 拿起一片面包
- 2. 逆时针方向打开花生酱罐的盖子
- 3. 抓起一把刀的刀柄
- 4. 把刀放进花生酱罐子
- 5. 把刀从罐子里拿出来,把花生酱抹在面包片上
- 6. 拿起第二片面包
- 7. 重复第2到5步,但这次用果酱
- 8. 重叠两片面包,让花生酱那面碰到果酱那一面
可以看到,每个步骤都非常明确,没有错误的余地。这是因为算法往往都是用电脑实现的,而电脑从客观上来说就是死板的。举个例子,你给电脑一个含有7个事项的列表,并要求得到第8个事项。机智的人类会回答说:“单子上只有七件事,所以我不能给你第八件。”然而,电脑多半就会崩溃。
但好的一面是,计算机的速度很快,这让它们能够比人类更高效地运行真正复杂的算法。例如,一台计算机可以在几分之一秒内对一个包含100个项目的列表进行排序,当然,前提是它收到了明确的指令,而且有如何执行此操作的详细说明。
有哪些类型的算法?
计算机被要求做各种各样的任务,而且要很快地完成。比如一边根据每个人的姓氏对联系人列表进行排序,一边在YouTube上搜索某个特定视频,等等。在第一台计算机发明之前,学者们就已经在研究算法了:他们尝试设计新颖、有效的方法来解决问题。下面,我将介绍两种比较著名的算法范例:
- 暴力破解法(The brute force approach)
想象你在字典里找“enigma”这个词。聪明的人类会直接翻到包含字母e的单词部分,然后从那里开始找。很有效,对吧?不幸的是,计算机并不太懂英语。所以,有人提出可以使用暴力破解法来解决这个问题。
暴力破解法需要查看每一页上的每一个单词,直到单词enigma出现为止。这是一件效率相当低的工作。事实上我们可以这样理解,如果在单词enigma之前有n个单词,那么在找到正确的单词之前,我们必须重复执行n次操作(在这种情况下执行的操作,就是检查我们有没有找到单词enigma)。
让我们想象一下最坏的情况。假设你想找“zzzzzz”这个词。显然,这个词是并不存在的,但如果你想再找一次该怎么办?暴力破解法就要你浏览每一页,查看每个单词,直到找到字典中的最后一个单词(Zyzzyva),才能确定“zzzzzz”并不是一个单词。与enigma这个例子类似,如果我们假设字典中有n个单词,这会需要n次重复操作。所以,一定有一个更好的办法来解决这个问题。
- 分治法(Divide and conquer)
现在,假设你正在查看的字典与大多数字典一样,都是有序的。这说明你能将字典拆分成几段,并确定每段中的单词按字母顺序是出现在“ zzzzzz”之前还是之后。
工作流程如下所示:
- 1. 找到字典的正中心
- 2. 判断正中心的单词是不是“zzzzzz”,如果是,查找完成
- 3. 如果不是,判断“zzzzzz”这个单词的首字母会在字典前半部分还是后半部分出现
- 4. 如果“ zzzzzz”会在中心之前出现,对字典的前半部分重复以上步骤。否则,对字典的后半部分重复以上步骤
最终,你会多次拆分字典,直到只剩下一个或两个单词。无论哪一种情况,判断剩余单词是否是“zzzzzz”的过程都会非常简单。与暴力破解方法不同,你可以跳过字典的很大一部分达到这一点。
将工作量划分为越来越小的部分的方法被称为分治法。这种算法案例利用了递归,根据问题自身的最简模式来定义该问题。在这种情况下,问题是要在整个字典中搜索“zzzzzz”。而“最简模式”是在字典的一个更小的部分中搜索“zzzzzz”。
分解法的效率到底能提高多少?为了找到答案,我们需要计算总共执行了多少个运算。为简单起见,我们把上述工作流中的步骤1到4视为一项运算。我们之所以可以这样做,是因为在步骤中执行的琐碎运算并不会对效率造成很大的负面影响:使代码运行缓慢的源头是操作的总数量。
所以在每个步骤中,我们看做执行一项运算。那要总共需要多少个步骤呢?也就是说,在每个步骤中,我们要么找到“ zzzzzzzz”,要么将字典的大小减半。因此,如果完整词典包含n个单词,那么在每个步骤中被省去的单词数量应为:
n/2 -> n/4 -> n/8 -> n/16 -> n/32 -> …. -> 1
通过少量的数学计算,我们可以意识到,与最坏的情况下要求的操作量n不同,我们现在只需要log n次操作。所以,如果字典里有一百万个单词,暴力破解法在最坏的情况下需要计算一百万次,而分治法只需要大约20次。非常不错!
注意,上面的log是以2为底的。然而,就像我们可以忽略每个步骤里执行的操作量一样,这里的底也是可以忽略的。
为什么我们只关心最坏的情况?
在讨论了这么多最坏情况之后,计算机科学家给人的感觉就像一群长期的悲观主义者一样。然而事实并非如此。
我们担心最坏的情况,是因为我们希望将负面影响(或经历最坏情况的可能性)最小化。负面影响包括过多的内存消耗、长时间运行、或潜在的无限延迟。
在分析最坏情况下的运行时,有一种相关的特定符号。它被称为Big O表示法。阅读完这个文章,你应该会知道上面两种主要搜索算法的Big O效率:
- 暴力搜索策略的技术名称是顺序搜索(Sequential Search)。 回想一下,在最坏的情况下,该算法将需要n个步骤/运算。因此,该算法的Big O效率为O(n)
- 分治法的技术名称是二分法检索(Binary Search)。由于在最坏的情况下需要log n次运算,所以它的Big O效率是O(log n)
总结
以上就是本文的全部内容!现在你应该也了解了两种字典搜索方法,以及如何计算它们的效率。感谢你花时间阅读这篇文章。如果你发现这有帮助,或者如果你有任何关于计算机科学的建议,请在下方留言。你还可以订阅我们的YouTube频道,观看大量数据科学相关公开课:https://www.youtube.com/channel/UCa8NLpvi70mHVsW4J_x9OeQ;在LinkedIn上关注我们,扩展你的人际网络!https://www.linkedin.com/company/dataapplab/
Happy hacking!
原文作者:Evan Wireman
翻译作者:Lea
美工编辑:过儿
校对审稿:Jiawei Tong
原文链接:https://medium.com/codex/an-intuitive-introduction-to-algorithms-39afcb1c36e7