算法初探（上）

                    (function(){
                        var cover = "http://mmbiz.qpic.cn/mmbiz/dcEP2tDMibceCp9hpttgy7rhmRb3mhyDDsl9r6wh6tvPAOI2TMTCIqDoIxMVXGajcG8wcVeXh9l7og9iaOW8tpyg/0?wx_fmt=jpeg";
                        var tempImg = document.createElement('img');
                        tempImg.setAttribute('class', 'rich_media_thumb');
                        tempImg.setAttribute('id', 'js_cover');
                        tempImg.setAttribute('data-backsrc', cover);
                        tempImg.setAttribute('src', cover);
                        tempImg.setAttribute('onerror', 'this.parentNode.removeChild(this)');
                        
                        document.getElementById('media').appendChild(tempImg);

                    })();

本文选自《世界是数字的》，介绍了计算机算法的本质

什么是软件？一个通俗的比喻是做菜用的菜谱。菜谱会列出做某个菜所需的原材料、烹饪步骤以及预期结果。类似地，程序也要描述待操作的数据，讲清楚要对数据做什么，以及产出什么结果。不过，菜谱与任何程序都不能比，因为它含糊，容易产生歧义。所以这个比喻并不是非常恰当。比如，我家那本《烹饪的快乐》（ Joy of Cooking）在说到打鸡蛋时，说要“放在一个小碗里： 1 个鸡蛋”，但没说必须先把蛋磕开，把壳去掉。

用税申报表来作比喻更准确一些：这些表格极其详尽地说明了你应该做什么（“从第 29 行减去第 30 行。如果结果是 0 或更小，则输入 0。给第 31 行乘上 25%，……”）。

虽然这个比喻也不完美，但与菜谱相比，纳税申报表在说明计算过程方面更胜一筹：数学计算必不可少，数据从一个位置被复制到另一个位置，后续的计算取决于之前计算的结果。对于纳税来说，这个过程应该是完整的，无论什么情况下都应该得出一个结果，即应纳税额。应该是毫无疑义的，只要开始的数据相同，任何人都应该得到相同的最终结果。而且应该在有限的时间内完成。从我个人经验来看，这几条都是理想化的，因为术语并不总是很明了，计算说明也比税务机关的说法含糊很多，而且要使用什么数据经常也不好确定。

算法，就是保证特定计算过程正确执行的一系列步骤，它是计算机科学中的菜谱或纳税申报表，只不过编制得更仔细、更准确、更清楚。算法的每一步都表达为一种基本操作，其含义都是完全确定的，如“两个数相加”。任何事物都没有歧义，输入数据的性质也是既定的。所有可能的情况都会涵盖，而算法绝不会遇到一种它不知道接下来该做什么的情况。（计算机科学家有时候也不免书生气，因此通常会给算法多加一个限定条件：任何算法最终必须停止。根据这个标准，经典的洗发水使用说明“起泡、冲洗、重复”就不能说是算法了。）

设计、分析和实现高效的算法是学院派计算机科学的工作核心，而在现实世界中也有很多算法意义重大。我没有打算滴水不漏地解释或说明各种算法，但我想让大家了解相关的思想，即详尽地描述一系列操作步骤，不管执行这些步骤的实体有没有智能或创造力，都能对这些步骤是什么意思以及如何执行做到毫无疑义。另外，我还想谈一谈算法的效率，也就是计算时间与要处理的数据量之间存在什么关系。为此，我会分析几个常见且容易理解的基本算法。

虽然不必把本章中的每一句话或者偶尔出现的公式都搞明白，但其中的思想还是值得读者深入研究的。

4.1 线性算法

假设我们想找出谁是房间里个子最高的人。我们可以四下里看看，然后猜一猜会是谁。

然而，算法则必须精确地列出每一个步骤，从而让不会说话的计算机都能遵照执行。最基本的做法就是依次询问每个人的身高，并记住到目前为止谁最高。于是，我们可能会问“约翰，你多高？玛丽，你呢？”等等。如果我们第一个问的是约翰，那么当时他是最高的。如果玛丽更高，则现在她是最高的人，否则，约翰仍然最高。无论如何，我们都会接着问第三个人。在问完每个人之后，我们就会知道究竟谁最高以及到底有多高。类似的方法还可以找出最有钱的人，或者名字在字母表中最靠前的人，或者谁的生日最接近年底，谁在 5 月出生，以及谁叫克里斯。

会遇到一些复杂的情况。比如如何处理重复的数据，或者说要是有两三个人的身高一样怎么办？我们可以决定只记录第一个人、只记录最后一个人，或者随机记录其中某一个人，再或者记录他们所有人。请注意，找出同样身高的所有人是比较困难的。因为必须记住所有这些人的名字，不问完最后一个人，我们是无法知道这些信息的。这个例子涉及数据结构，即如何表示计算过程中所需的信息。数据结构对很多算法而言都是非常重要的，但在这里我们不会谈太多。

怎么计算所有人的平均身高？可以询问每个人的身高，每问完一个就加一个（或许可以使用玩具程序来进行累计），最后用累计和除以人数。假设一张纸上写着 N 个人的身高，那这个例子更像“算法”的表达方式如下：

把累计和 sum 设置为 0

对这张纸上的每一个身高值 height

把 height 加到 sum 上

平均身高等于 sum/N

但是，如果让计算机来做这件事，就必须多加小心。例如，要考虑到假如纸上没有身高值怎么办？这对人来说不是问题，因为我们知道这意味着什么也不用做。但对计算机来说，我们必须告诉它如何测试这种情况，出现这种情况该怎么办。假如不事先测试，那它就会尝试用零去除 sum，而这个操作是未定义的。算法和计算机必须处理所有可能的情况。如果你看到过“0 美元 00 美分”的支票，或者收到过尚欠余额为 0 元的账单，那就是因为计算机系统没有全面测试所有可能的情况。

如果我们事先不知道有多少个数据项怎么办（这种情况很常见）？那就得重写算法，让它在累计和的同时计算有多少项。

把累计和 sum 设置为 0

把项数 N 设置为 0

只要有剩下的身高值要处理

把下一个 height 加到 sum 上

给 N 加 1

如果 N 大于 0

平均身高是 sum/N

否则

就说没有给出身高值

这是避免出现除数为零的问题一种方式，即明确地测试极端情况。

算法的一个关键属性是其效率有多高——对于给定的数据量，它们的处理速度是快还是慢，要花多长时间？对于上面给出的例子，计算机要执行多少步，或者需要花的时间有多长，与它必须处理的数据量成正比：如果房间里的人多出一倍，就要多花一倍时间才能找到最高的人，或者才能计算出平均身高；如果人数是现在的十倍，就要花十倍的时间。如果计算时间与数据量成正比或叫线性比例，那该算法就叫做线性时间算法或线性算法。以数据量为横坐标，以时间为纵坐标画一条线，得到的将是一条向右上方延伸的直线。我们平时遇到的大多数算法都是线性的，因为它们对某些数据所执行的基本操作是相同的，数据越多工作量也会同比例增加。线性算法的基本形式都一样。可能需要进行一些初始化，如把累计和的初值设置为 0，

或者把最大的身高值设置为一个较小的值。然后依次检查每一项，对它完成一次简单的计算，如计数、与上一个值比较，或进行简单的变换。最后，可能需要再做一些计算，如计算平均值、打印累计和或最大的身高值。如果对每一项执行操作所花的时间相同，那么总时间与数据项数就是呈正比的关系。

4.2 二分搜索

那我们还可以做得更好一些吗？假设我们面前有一大堆打印出来的人名和电话号码，或者一沓名片。如果名字并没有特定的顺序，而我们想找到迈克·史密斯（ Mike Smith）的号码，那就必须一个名字一个名字地找，直至找到他的名字为止（或者没找到，因为根本就没有这个人）。如果名字是以字母顺序排列的，我们就可以做得更好。

想想我们是怎么从老式的电话簿中查人名的。 首先， 我们会从接近中间的地方开始查。如果要找的名字比中间页上的名字在字母表中靠前，那后半本就不用看了，直接翻到前半本的中间（整本电话簿的四分之一处）；否则，前半本就不用看了，直接翻到后半本的中间（整本电话簿的四分之三处）。由于名字按字母顺序排列，每一步我们都知道接下来到哪一半里去找。最终，我们一定会找到那个名字，或者可以断定电话簿里根本就没有这个人。

这个搜索算法被称为二分搜索，因为每次检查或比较都会把数据项一分为二，而其中一半今后就不会再理会了。这其实也是常见的分而治之策略的一个应用。它的速度有多快？每一步都会舍弃一半数据项，因此所需要的步数就等于在处理最后一项之前，最初的项数被 2 除开的次数。

假设最初有 1024 个名字（这个数容易计算）。一次比较，就可以舍弃 512 个。再比较一次，还剩 256 个，然后是 128 个、 64 个、 32 个，接着是 16 个、 8 个、 4 个、 2 个，最后剩下 1 个。总共比较了 10 次。显然， 210等于 1024 并非巧合。比较次数作为 2 的指数就能得到最初的数，而从 1 到 2 到 4……到 1024，每次都是乘以 2。

如果你还记得学校里讲过的对数（没有多少人会记得——谁还记得？），那你应该知道一个数的对数就是底数（这里是 2）要得到该数需要自乘的次数。 1024（以 2 为底）的对数等于 10，就是因为 210等于 1024。对于我们而言，这里的对数就是要把一个数变成 1，反复除以 2 的次数；或者让 2 反复自乘，得到那个数所需的次数。本书不需要考虑精度或者小数，近似的数字和整数值足矣，纯粹是一种简化。

二分搜索的关键是数据量的增长只会带来工作量的微小增长。如果有 1000 个名字按字母顺序排列，那为了找到其中一个必须检查 10 个名字。如果有 2000 个名字，也只要检查 11 个名字，因为看完第一个名字立即就能舍弃 2000 个中的 1000 个，而这又回到了从 1000 个中查找的情形（检查 10 次）。 如果有 1 000 000 个名字，也就是 1000 的 1000倍，那么前 10 次测试就能减少到 1000，另外 10 次测试即可减少到 1，总共 20 次测试。

1 000 000 是 106，约等于 220，因此 1 000 000（以 2 为底）的对数约等于 20。

由此，你就可以知道，在包含 10 亿个名字的名录（全地球的电话簿）中找 1 个名字，也只需要 30 次比较，因为 10 亿约等于 230。这就是为什么我们说数据量的增长只会带来工作量的微小增长——数据量增长到 1000 倍，只需要多比较 10 次。

我们来验证一下，假设我要从一本旧的哈佛通讯录中找到我的朋友 Harry Lewis，这本224 页的通讯录中有大约 20 000 个人名。我首先翻到 112 页，看到了 Lawrence。 Lewis在它后面，所以我又翻到 168 页，即 112 页和 224 页中间，找到了 Rivera。 Lewis 在它前面，于是我翻到 140 页（ 112 页和 168 页中间），看到了 Morita。再向前翻到 126页（ 112 页和 140 页中间）找到 Mark。随后是 119 页（ Little）、 115 页（ Leitner）、 117页（ Li），最后翻到 116 页。这一页大约有 90 个名字，在同一页上又经过 7 次比较，我从几十位 Lewis 中找到了 Harry。这个实验总共比较了 14 次，跟我们预期差不多，因为 20 000 介于 214（ 16 384）和 215（ 32 768）之间。

分而治之在现实当中也广泛应用于很多比赛的淘汰赛。比赛开始一般都有很多的选手，比如温布尔登网球公开赛男子单打比赛一开始有 128 位选手，每轮比赛都会淘汰一半，最后一轮剩下两个人，决出一名冠军。这并非巧合， 128 是 2 的幂（ 27），所以温布尔登网球公开赛要打七轮。甚至可以想象举办一次全球规模的淘汰赛，即便有 70亿个参赛者，也只要 33 轮就可以决出冠军。（如果你还记得第 2 章讨论过的 2 和 10的幂，通过心算也很容易验证这一点）。

★喜欢这篇文章？

欢迎转发至朋友圈或您的好友。

★对本文有想法？

回到首页，在“发送”栏输入观点。

长按该图片，扫描二维码，即可以一键关注本公众号。

欢迎加小编铁哥个人微信562763765