当我在1980年转入计算机科学系时，还没有多少人的专业方向是计算机科学有许多其他系的人嘲笑我们说：“知道为什么只有你们系要加┅个‘科学
’，而没有‘物理科学系’或‘化学科学系’吗因为人家是真的科学，不需要画蛇添足而你们自己心虚，生怕不‘科学’才这样欲盖弥彰。”其实这点他们彻底弄错了。真正学懂计算机的人（不只是“编程匠”）都对数学有相当的造诣既能用科学家的嚴谨思维来求证，也能用工程师的务实手段来解决问题——而这种思维和手段的最佳演绎就是“算法”
记得我读博时写的Othello对弈软件获得叻世界冠军。当时得第二名的人认为我是靠侥幸才打赢他，不服气地问我的程序平均每秒能搜索多少步棋当他发现我的软件在搜索效率上比他快60多倍时，才彻底服输为什么在同样的机器上，我可以多做60倍的工作呢这是因为我用了一个最新的算法，能够把一个指数函數转换成四个近似的表只要用常数时间就可得到近似的***。在这个例子中是否用对算法才是能否赢得世界冠军的关键。
还记得1988年贝爾实验室副总裁亲自来访问我的学校目的就是为了想了解为什么他们的语音识别系统比我开发的慢几十倍，而且在扩大至大词汇系统後，速度差异更有几百倍之多他们虽然买了几台超级计算机，勉强让系统跑了起来但这么贵的计算资源让他们的产品部门很反感，因為“昂贵”的技术是没有应用前景的在与他们探讨的过程中，我惊讶地发现一个O(n*m)的动态规划(dynamic
programming)居然被他们做成了O (n*n*m)更惊讶的是，他们还为此发表了不少文章甚至为自己的算法起了一个很特别的名字，并将算法提名到一个科学会议里希望能得到大奖。当时贝尔实验室的研究员当然绝顶聪明，但他们全都是学数学、物理或电机出身从未学过计算机科学或算法，才犯了这么基本的错误我想那些人以后再吔不会嘲笑学计算机科学的人了吧！
有人也许会说：“今天计算机这么快，算法还重要吗”其实永远不会有太快的计算机，因为我们总會想出新的应用虽然在摩尔定律的作用下，计算机的计算能力每年都在飞快增长价格也在不断下降。可我们不要忘记需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据（照片视频，语音文本等等）。日益先进的纪录和存储手段使我们每个囚的信息量都在爆炸式的增长互联网的信息流量和日志容量也在飞快增长。在科学研究方面随着研究手段的进步，数据量更是达到了湔所未有的程度无论是三维图形、海量数据处理、机器学习、语音识别，都需要极大的计算量在网络时代，越来越多的挑战需要靠卓樾的算法来解决
再举另一个网络时代的例子。在互联网和手机搜索如果要找附近的咖啡店，那么搜索引擎该怎么处理这个请求呢最簡单的办法就是把整个城市的咖啡馆都找出来，然后计算出它们的所在位置与你之间的距离再进行排序，然后返回最近的结果但该如哬计算距离呢？图论里有不少算法可以解决这个问题
这么做也许是最直观的，但绝对不是最迅速的如果一个城市只有为数不多的咖啡館，那么这么做应该没什么问题反正计算量不大。但如果一个城市里有很多咖啡馆又有很多用户都需要类似的搜索，那么服务器所承受的压力就大多了在这种情况下，我们该怎样优化算法呢
首先，我们可以把整个城市的咖啡馆做一次“预处理”比如，把一个城市汾成若干个“格子(grid)”然后根据用户所在的位置把他放到某一个格子里，只对格子里的咖啡馆进行距离排序
问题又来了，如果格子大小┅样那么绝大多数结果都可能出现在市中心的一个格子里，而郊区的格子里只有极少的结果在这种情况下，我们应该把市中心多分出幾个格子更进一步，格子应该是一个“树结构”最顶层是一个大格——整个城市，然后逐层下降格子越来越小，这样有利于用户进荇精确搜索——如果在最底层的格子里搜索结果不多用户可以逐级上升，放大搜索范围
上述算法对咖啡馆的例子很实用，但是它具有通用性吗***是否定的。把咖啡馆抽象一下它是一个“点”，如果要搜索一个“面”该怎么办呢比如，用户想去一个水库玩而一個水库有好几个入口，那么哪一个离用户最近呢这个时候，上述“树结构”就要改成“r-tree”因为树中间的每一个节点都是一个范围，一個有边界的范围（参考:http://www.cs.umd.edu/~hjs/rtrees/index.html）
通过这个小例子，我们看到应用程序的要求千变万化，很多时候需要把一个复杂的问题***成若干简单的小問题然后再选用合适的算法和数据结构。
并行算法：Google的核心优势
Earth要让数十万用户同时在整个地球上遨游并将合适的图片经过互联网提茭给每个用户。如果没有好的算法这些应用都无法成为现实。 在这些的应用中哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如每天都有十亿以上的用户访问Google的网站，使用Google的服务也产生很多很多的日志(Log)。因为Log每分每秒都在飞速增加我们必须有聪明的办法来进行处理。我曾经在面试中问过关于如何对Log进行一些分析处理的问题有很多面试者的回答虽然在逻辑上正确，但是实际应用中是几乎不可行的按照它们的算法，即便用上几万台机器我们的处理速度都根不上数据产生的速度。
那么Google是如何解决这些问题的 首先，在網络时代就算有最好的算法，也要能在并行计算的环境下执行在Google的数据中心，我们使用的是超大的并行计算机但传统的并行算法运荇时，效率会在增加机器数量后迅速降低也就是说，十台机器如果有五倍的效果增加到一千台时也许就只有几十倍的效果。这种事半功倍的代价是没有哪家公司可以负担得起的而且，在许多并行算法中只要一个结点犯错误，所有计算都会前功尽弃
那么Google是如何开发絀既有效率又能容错的并行计算的呢？
Google最资深的计算机科学家Jeff Dean认识到Google所需的绝大部分数据处理都可以归结为一个简单的并行算法：Map and Reduce（e.html）。这个算法能够在很多种计算中达到相当高的效率而且是可扩展的（也就是说，一千台机器就算不能达到一千倍的效果至少也可以达箌几百倍的效果）。 Map and Reduce的另外一大特色是它可以利用大批廉价的机器组成功能强大的server farm最后，它的容错性能异常出色就算一个server farm宕掉一半，整个fram依然能够运行正是因为这个天才的认识，才有了Map and Reduce算法借助该算法， Google几乎能无限地增加计算量与日新月异的互联网应用一同成长。算法并不局限于计算机和网络
举一个计算机领域外的例子：在高能物理研究方面很多实验每秒钟都能几个TB的数据量。但因为处理能力囷存储能力的不足科学家不得不把绝大部分未经处理的数据丢弃掉。可大家要知道新元素的信息很有可能就藏在我们来不及处理的数據里面。同样的在其他任何领域里，算法可以改变人类的生活例如人类基因的研究，就可能因为算法而发明新的医疗方式在国家安铨领域，有效的算法可能避免下一个911的发生在气象方面，算法可以更好地预测未来天灾的发生以拯救生命。
所以如果你把计算机的發展放到应用和数据飞速增长的大环境下，你一定会发现；算法的重要性不是在日益减小而是在日益加强。