MIT花生酱三明治实例深入浅出学算法

今日份知识你摄入了么？

什么是算法？

作为一名程序员，拥有大量可使用的工具非常重要的。其中可能会包括编程语言、文本编辑器、程序包等。而最重要的是，要对现有的各种类型的算法有深刻的了解。这些都会成为技术面试和工作中最重要的一套工具。

对于那些不了解的人来说，算法并不是一个很难理解的概念。算法就是一种定义简单明确、逐步解决问题的方法。比如，在很多计算机科学的课上都有一个练习，要求学生解释怎样制作一个花生酱和果酱三明治。可能你会震惊，这个练习过程就是一种算法。

麻省理工学院(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)  

总结

以上就是本文的全部内容！现在你应该也了解了两种字典搜索方法，以及如何计算它们的效率。感谢你花时间阅读这篇文章。如果你发现这有帮助，或者如果你有任何关于计算机科学的建议，请在下方留言。

Happy hacking!

原文作者：Evan Wireman

翻译作者：Lea

美工编辑：过儿

校对审稿：Jiawei Tong

原文链接：https://medium.com/codex/an-intuitive-introduction-to-algorithms-39afcb1c36e7

往期精彩回顾

点「在看」的人都变好看了哦

点击“阅读原文”查看数据应用学院核心课