李开复说算法

1、算法李开复：算法的力量算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在“开复学生网”上，有位同学生动地把这些基础课程比拟为呐功”，把新的语言、技术、标准比拟为“外功”。整天赶时髦

2、的人最后只懂得招式，没有功力，是不可能成为高手的。算法与我当我在1980年转入计算机科学系时，还没有多少人的专业方向是计算机科学。有许多其他系的人嘲笑我们说：“知道为什么只有你们系要加一个科学，而没有物理科学系或化学科学系吗？因为人家是真的科学，不需要画蛇添足，而你们自己心虚，生怕不科学，才这样欲盖弥彰。”其实，这点他们彻底弄错了。真正学懂计算机的人（不只是编程匠”）都对数学有相当的造诣，既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题而这种思维和手段的最佳演绎就是“算法”。记得我读博时写的Othello对弈软件获得了世界冠军。当时，得第二名的人认为我是靠侥幸才打赢他，不服气地问

3、我的程序平均每秒能搜索多少步棋，当他发现我的软件在搜索效率上比他快60多倍时，才彻底服输。为什么在同样的机器上，我可以多做60倍的工作呢？这是因为我用了一个最新的算法，能够把一个指数函数转换成四个近似的表，只要用常数时间就可得到近似的答案。在这个例子中，是否用对算法才是能否赢得世界冠军的关键。还记得1988年贝尔实验室副总裁亲自来访问我的学校，目的就是为了想了解为什么他们的语音识别系统比我开发的慢几十倍，而且，在扩大至大词汇系统后，速度差异更有几百倍之多。他们虽然买了几台超级计算机，勉强让系统跑了起来，但这么贵的计算资源让他们的产品部门很反感，因为“昂贵”的技术是没有应用前景的。在与他们探讨的

4、过程中，我惊讶地发现一个O(n*m)的动态规划(dynamicprogramming)居然被他们做成了O(n*n*m)。更惊讶的是，他们还为此发表了不少文章，甚至为自己的算法起了一个很特别的名字，并将算法提名到一个科学会议里，希望能得到大奖。当时，贝尔实验室的研究员当然绝顶聪明，但他们全都是学数学、物理或电机出身，从未学过计算机科学或算法，才犯了这么基本的错误。我想那些人以后再也不会嘲笑学计算机科学的人了吧！网络时代的算法有人也许会说：“今天计算机这么快，算法还重要吗？”其实永远不会有太快的计算机，因为我们总会想出新的应用。虽然在摩尔定律的作用下，计算机的计算能力每年都在飞快增长，价格也在不断

5、下降。可我们不要忘记，需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据(照片，视频，语音，文本等等)。日益先进的纪录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面，随着研究手段的进步，数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别，都需要极大的计算量。在网络时代，越来越多的挑战需要靠卓越的算法来解决。再举另一个网络时代的例子。在互联网和手机搜索，如果要找附近的咖啡店，那么搜索引擎该怎么处理这个请求呢？最简单的办法就是把整个城市的咖啡馆都找出来，然后计算出它们的所在位置与你之间的距离，再进

6、行排序，然后返回最近的结果。但该如何计算距离呢？图论里有不少算法可以解决这个问题。这么做也许是最直观的，但绝对不是最迅速的。如果一个城市只有为数不多的咖啡馆，那么这么做应该没什么问题，反正计算量不大。但如果一个城市里有很多咖啡馆，又有很多用户都需要类似的搜索，那么服务器所承受的压力就大多了。在这种情况下，我们该怎样优化算法呢？首先，我们可以把整个城市的咖啡馆做一次“预处理”。比如，把一个城市分成若干个“格子(grid)”，然后根据用户所在的位置把他放到某一个格子里，只对格子里的咖啡馆进行距离排序。问题又来了，如果格子大小一样，那么绝大多数结果都可能出现在市中心的一个格子里，而郊区的格子里只有极

7、少的结果。在这种情况下，我们应该把市中心多分出几个格子。更进一步,格子应该是一个“树结构”，最顶层是一个大格整个城市，然后逐层下降，格子越来越小，这样有利于用户进行精确搜索一一如果在最底层的格子里搜索结果不多，用户可以逐级上升，放大搜索范围。上述算法对咖啡馆的例子很实用，但是它具有通用性吗？答案是否定的。把咖啡馆抽象一下，它是一个点”，如果要搜索一个“面”该怎么办呢？比如，用户想去一个水库玩，而一个水库有好几个入口，那么哪一个离用户最近呢？这个时候，上述“树结构”就要改成“r-tree”，因为树中间的每一个节点都是一个范围，一个有边界的范围。通过这个小例子，我们看到，应用程序的要求千变万化，很

8、多时候需要把一个复杂的问题分解成若干简单的小问题，然后再选用合适的算法和数据结构。并行算法：Google的核心优势上面的例子在Google里就要算是小case了！每天Google的网站要处理十亿个以上的搜索，GMail要储存几千万用户的2G邮箱，GoogleEarth要让数十万用户同时在整个地球上遨游，并将合适的图片经过互联网提交给每个用户。如果没有好的算法，这些应用都无法成为现实。在这些的应用中，哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如，每天都有十亿以上的用户访问Google的网站，使用Google的服务，也产生很多很多的日志(Log)。因为Log每份每秒都在飞速增加，我们必须

9、有聪明的办法来进行处理。我曾经在面试中问过关于如何对Log进行一些分析处理的问题，有很多面试者的回答虽然在逻辑上正确，但是实际应用中是几乎不可行的。按照它们的算法，即便用上几万台机器，我们的处理速度都根不上数据产生的速度。那么Google是如何解决这些问题的？首先，在网络时代，就算有最好的算法，也要能在并行计算的环境下执行。在Google的数据中心，我们使用的是超大的并行计算机。但传统的并行算法运行时，效率会在增加机器数量后迅速降低，也就是说，十台机器如果有五倍的效果，增加到一千台时也许就只有几十倍的效果。这种事半功倍的代价是没有哪家公司可以负担得起的。而且，在许多并行算法中，只要一个结点犯错

10、误，所有计算都会前功尽弃。那么Google是如何开发出既有效率又能容错的并行计算的呢？Google最资深的计算机科学家JeffDean认识到，Google所需的绝大部分数据处理都可以归结为一个简单的并行算法：MapandReduce( HYPERLINK /papers/mapreduce.html /papers/mapreduce.html)。这个算法能够在很多种计算中达到相当高的效率，而且是可扩展的(也就是说，一千台机器就算不能达到一千倍的效果，至少也可以达到几百倍的效果)。MapandReduce的另外一大特色是它可以利用大批廉价的机器组成功能强大的serverfarm。最后，它的容错

11、性能异常出色，就算一个serverfarm宕掉一半，整个fram依然能够运行。正是因为这个天才的认识，才有了MapandReduce算法。借助该算法，Google几乎能无限地增加计算量，与日新月异的互联网应用一同成长。算法并不局限于计算机和网络举一个计算机领域外的例子：在高能物理研究方面，很多实验每秒钟都能几个TB的数据量。但因为处理能力和存储能力的不足，科学家不得不把绝大部分未经处理的数据丢弃掉。可大家要知道，新元素的信息很有可能就藏在我们来不及处理的数据里面。同样的，在其他任何领域里，算法可以改变人类的生活。例如人类基因的研究，就可能因为算法而发明新的医疗方式。在国家安全领域，有效的算法可

12、能避免下一个911的发生。在气象方面，算法可以更好地预测未来天灾的发生，以拯救生命。所以，如果你把计算机的发展放到应用和数据飞速增长的大环境下，你一定会发现；算法的重要性不是在日益减小，而是在日益加强。转自计算机科学论坛注:算法是计算机科学的核心,是程序的灵魂，它的基础性地位遍布计算机科学的各个分支领域.原文作者介绍：李开复博士现google中国总裁1998年7月加盟微软，当年11月出任微软中国研究院（现微软亚洲研究院）院长。李开复在语音识别、人工智能、三维图形及网络多媒体等领域享有很高的声誉。在他的带领下，微软中国研究院以新一代多媒体、新一代用户界面和新一代信息处理技术为主要方向开展基础研究

13、。后升任微软副总裁。加盟微软公司前，李博士曾担任SGI公司的多媒体软件子公司CosmoSoftware的总裁，负责多平台、互联网三维图形和多媒体软件方面的研发工作。此前他还曾在苹果公司工作了六年，主管该公司的多媒体部门。李博士在苹果公司任职六年中的最后一个职务是其交互式多媒体部门的副总裁，他们后来开发出QuickTime，QuickDraw3D，QuickTimeVR等产品。在加入苹果公司之前，李博士曾就读于美国卡内基梅隆大学，获计算机科学博士学位。后担任副教授。在他的博士课题研究工作中，首次创造性的提出基于统计学的语音识别方法，并在此基础上开发出了世界上第一个“非特定人连续语音识别”系统，使

14、识别率由原来的百分之三十提高到百分之九十六，该方法今天已成为计算机语音识别的技术主流，也奠定了李博士在该领域的权威地位。1988年，商业周刊授予该系统“最重要科学创新奖”。在校期间，李博士还开发了“奥赛罗”人机对弈系统，因为在1988年击败了国际象棋世界冠军而名噪一时。李开复同时还是美国电气电子工程协会的院士。常用算法&数据结构浙江大学微软技术俱乐部彭鹏ACM竞赛竞赛中常见的16种题型3,竞赛中基本的数据结构与算法时空复杂度的分析0,如何建立一支强队如何建立一支强队个人的能力理论（几何，数论，动态规划，图论等）技术（编程）队员能力上的互补某论坛，一无聊男yy的中国梦之队钱文杰（）反应奇快，擅长

15、随机化，贪心,NOI贪心王刘汝佳or吴嘉之见多识广,做过的题必别人见过的题多赵爽上海交大的割题手一支强队需要的角色Leader/Coordinato（协调比赛进程）Reader（发现题目隐讳的涵义）Thinker（逻辑能力强，收集其他队员意见）Programmer/Debugger（反应快/稳,细心）Helper（协助比赛，查错，验证数据等）参考书籍主要参考书籍C+PrimerC+标准程序库算法导论算法艺术与信息学竞赛组合数学计算几何历届国家集训队论文时空复杂度的分析时间复杂度的分析空间复杂度的分析函数增长和运行时间引用刘汝佳序列和字符串常见题型DynamicProgramming（动态规戈U

16、）Greedy（贪心）CompleteSearch（穷举）FloodFill（种子填充）常见题型ShortestPath（最短路径）RecursiveSearchTechniques（回溯）MinimumSpanningTree（最小生成树）Knapsack（背包）常见题型ComputationalGeometry（计算几何）NetworkFlow（网络流）EulerianPath（欧拉回路）Two-DimensionalConvexHull（二维凸包）常见题型BigNums（大数）HeuristicSearch（启发式搜索）ApproximateSearch（近似搜索）AdHocProble

17、ms（杂题）枚举法又叫穷举法,它利用了计算机计算速度快且准确的特点，是最为朴素和有效的一种算法.不是办法的办法但有时却是最好的办法PizzaAnyone(ZOJ1219)题目大意：你需要为你和你的朋友们订一个皮萨每个朋友都会告诉你他们想和不想放进皮萨里的东西.你是否能订一个皮萨，让他满足每个人至少一个条件.假设一共有16种东西可以放进皮萨.是个对计算机很小的数贪心法(Greedy)矩阵胚理论(详情请参考算法导论)枚举法的时间效率很低,贪心法恰恰与其相反并且贪心法的程序也很好实现.无数论文都指责贪心法往往得不到问题的最优解.绝世高手与普通高手的差距所在.栈和队列栈:后进先出(LIFO)队列:先进

18、先出(FIFO)字符串的输入与输出或chars100;scanf(%s,s);stringa(s);Stringa;cina;C+常用头文件字符串的读入哪种读入更快在输入数据达到1M时,cin,cout将比scanf,printf在速度上有明显的劣势排序排序的种类：交换排序，选择排序，插入排序,堆排序希尔排序，快速排序，归并排序,桶排序用C+实现排序#include数组asort(a,a+5);vectorasort(a.begin(),a.end();并查集并查集是一种树型的数据结构，用于处理一些不相交集合的合并问题.并查集的主要操作有合并两个不相交集合判断两个元素是否属于同一个集合路径压缩

19、Parity(ceoi99)有一个01序列，长度=1000000000，现在有n条信息，每条信息的形式是-abeven/odd.表示第a位到第b位元素之间的元素总和是偶数/奇数.你的任务是对于这些给定的信息,输出第一个不正确的信息所在位置-1.信息的数目不超过5000.如果信息全部正确,即可以找到一个满足要求的01序列，那么输出n.Parity(ceoi99)从整个01序列肯定是无法入手的，因为它的长度高达109.从范围比较小的n入手也就是说我们需要对信息进行一些特殊的处理.abeven/odd,那么将元素b指向a-1，边的权值是even/odd.下面我们由样例来说明一下这个处理方法.Pari

20、ty(ceoi99)(肖天)建立sum数组,sumi表示从1到i之和是奇(true)还是偶(false),sum0=false.这样题目中给的任意问题(a,b)的答案都可以用sumbxorsuma-1表示.开始我们并不知道suml.n的值，不妨设为false，这时任意suma,sumb都是独立的.对于每对问答（a,b,c），都可以知道sumbxorsuma-1=c，由此把sumb和suma-1联系起来.这步操作可以用并查集完成，对于问答（a,b,c）如果suma-1,sumb不属于一个集合就把它们并起来，否则如果suma-1xorsumb不等于c则说明出现矛盾,输出总句数,退出.对于不出现矛盾

21、的sum数组,对于每个集合分为两个部分，我们指定其中一个部分为true，另一个部分为false，则可以确定sum数组，利用sumixorsumi-1可以求出第i位的数字，由于不同集合之间没有问答出现，所以此数列是一可行解，证明算法正确.堆（优先队列）优点：实现简单动态维护一组数据中最小（大）的一个数组维护例题：积水一个长方形网格包含了n*m块地,每块地上面有1个长方体.每一个长方形盖住了一块地，地的面积是1平方英寸相邻的地上的长方体之间没有空隙一场大雨降临了这个建筑物，在建筑物的某些区域有积水产生.给各方格高度，求积水总量分析定义每块地上的长方体的高度称为原始高度积满水时的水面高度称为积水高度

22、（高于积水高度的水一定会流走,低于积水高度的水一定流不走）积水高度与原始高度之差为积水深度如果一个长方体上不可能有积水,那么它的积水高度就等于它的原始高度.最外圈不能积水，积水高度等于原始高度分析由外而内计算每次选取外围的格子中积水高度最低的一个格子X,考虑它周围所有在网格内部的格子y想象不断的往x和y里注水，但是x的积水高度固定(想象该高度处有一个小孔),因此如果y的原始高度不小于x的积水高度，那么它的积水高度就是它的原始高度如果y的原始高度小于x的积水高度，那么它的积水高度就等于x的积水高度每次用堆取出x进行计算,0(mnlogmn).哈希表(Hash)理论上查找速度最快的数据结构之一缺点

23、：需要大量的内存需要构造KeyHash表的实现数组冲突解决法开散列法闭散列法C+sgistl实现HashKey的选取数值：方法一:直接取余数(一般选取质数M最为除数)方法二:平方取中法，即计算关键值的平方，再取中间r位形成一个大小为的表是多少字符串：intELFhash(char*key)unsignedinth=0;while(*key)h=(h24;h&=-g；returnh%M;方法二:ELFhash函数方法一：折叠法:即把所有字符的ASCII码加起来二分搜索树普通的二分搜索树时间复杂度：缺点：容易出现不平衡的情况AVLTree,Splaytree,红黑树树堆(Treap)Treap=T

24、ree+heap每次插入/删除结点的时候,给结点随机分配一个优先级，让Treap关于优先级形成一个堆的同时，关于关键码形成BST跳跃表,B树跳跃表(Skiplists)线段树在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在0X轴上的线段由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等一个线段是对应于一个区间的，因此线段树也可以叫做区间树.Atlantis(ZOJ1128)一个平面被很多矩形覆盖,矩形之间会相互叠加输出矩形覆盖的总面积.Atlantis(ZOJ1128)线段树矩形切割矩形切割字典树(Trie)当关键字

25、是串的时候，理论上查找最快的数据结构定义:保存字符串用的树型数据结构(多叉树)，其中每个节点表示一个公共前缀，单词信息保存在相应的页节点里面.给如下几个单词，构造的单词树：An,Ant,All,AllotAlloy,Aloe,Are,Atebe版权归浙江大学ACM领队徐串所有转载需保留此字样T9(Z0J1038)题目描述:手机有智能英文输入法，他根据自己已有的词汇表，即使你每个数字只按一次也可以猜出你要按的是哪个单词(方法就是从所有可能的串中选出出现概率最高的一个).词汇表：hell3hello4idea8next8super3按435561是的响应显示iidhelhellhello动态规划动

26、态规划的时间效率极高.动态规划的算法简洁，一般只用边界和状态转移方程就可清晰地表示出进行规划的步骤;而因为有了这些用数学语言描述的天然材料，编程也较为方便.最重要的一点:动态规划不单是一种思想，也不单是一类算法，它是思想方法和具体算法的混合物.摘自徐静动态规划的算法与实现动态规划无后效性递推法和记忆化搜索深度优先搜索(DFS)按照深度优先的顺序遍历状态空间，通常用递归或者栈来实现.voiddfs(state，depth)讦(state=结束状态)退出；枚举所有可行状态更新全局变量；dfs(newstate,depth+1);还原全局变量宽度优先搜索(BFS)如果代价和搜索树深度成正比,那么可以

27、通过广度优先搜索得到解由于空间占用大，BFS用处不是很广，一般只用在路径寻找问题中，但是一旦使用,将比深度优先搜括看得多双向宽度优先搜索深度优先和宽度优先搜索比较PrimeRingProblem(ZOJ1457)Aringiscomposeofncirclesasshownindiagram.Putnaturalnumber1，2,.，nintoeachcircleseparately,andthesumofnumbersintwoadjacentcirclesshouldbeaprime.Note:thenumberoffirstcircleshouldalwaysbe1.n(0n20)wh

28、ile(!deque.empty()state=deque0;deque.pop();枚举所有可行状态tempstate=状态改变(state);deque.push_back(tempstate);宽度优先搜索(BFS)宽度优先搜索的框架Winlinez(ZOJ1591)Nowwehaveaboardof9*9grids,onwhichthereareseveralbeads.Thesebeadshaveonlysevencolors,wenumberthem1-7.Wedefinetheemptygridtobezero.Eachturnyoucanmoveanybeadontheboar

29、dtothedestinationwherethereisaroutebetweenthem.Theroutemeansthatthebeadcanmoveup,down,leftorrighttotheadjacentemptygridandmaygoonuntilitreachesthedestination.Afterthemoving,讦therearefiveormoresame-coloredbeadsinaline(row,column,diagonal),theywillallbeeliminated.博弈问题给定一个有向无环图(X,F),其中X是一个非空的点集(每个点表示一个

30、位置),F是一个在集合X上的函数，对于集合X中的任意一个元素x,F(x)返回一个集合X的子集，即,F(x)表示了由一个位置x可以到达的位置如果F(x)是空集，则称x是一个结束位置.现在两个人在这样的一个有向图上玩游戏，首先在一个初始位置x0上放置了一个棋子，然后他们将按照如下规则进行游戏：首先由选手I从初始位置x0进行移动.两个选手交替移动.在一个位置x,选手可以将棋子移到位置y上，其中yUx.如果轮到某一个选手移动时棋子处在一个结束位置,那么这个选手就会因为无法继续移动棋子而被判输掉这局游戏.对于给定的有向图和初始位置，请你判断出选手I与选手II谁会获胜.楼天城浅谈一类博弈问题的解法局面Ma

31、x局面Min局面终结局面局面估价函数Alpha-Beta剪枝AMultiplicationGame(ZOJ1893)Stan和Ollie一起做游戏.游戏的内容是将一个整数p乘上2到9中的任一个数.Stan总是从p=1开始，然后两个人交替相乘.在游戏开始前，两个人订了一个数n(1vN最大公约数最小公倍数欧几里得辗转相除intgcd(inta,intb)returnbgcd(b,a%b):a;intlcm(inta,intb)returna/gcd(a,b)*b;筛选法求质数表Eratosthenes(埃拉托色尼)筛选法：每次求出一个新的素数，就把n以内的它的所有倍数都筛去在实现的时候,对于-个素

32、数p,只需要筛去等就可以了，因为已经在q的第一个素因子被找到的时候被筛去了#defineN100#defineM100intpM,plist=0;intinit()memset(p,0,sizeof(p);for(inti=2;i=0)i-;讦(i0)return0;for(Min=i+1,j=i+2;jai&ajaMin)Min=j;swap(ai,aMin);for(intj=i+1;j=4),那么该图称为弦图FishingNet(ZOJ1015)判断一个图是否是弦图计算几何判两条线断相交判点在多边性内部二维凸包叉乘OJ是什么OnlineJudge的简称一种通过网络信息交互在线判题的系统它

33、模拟了ICPC比赛真实的情况当前世界上规模比较大的OJUVAZOJURALUSACOZhejianguniversityonlinejudge HYPERLINK 推荐使用：gcc+vivs2003/vs2005SubmissionError-提交使用了不正确的队名，题号等.NoSuchProblem-检查题号有没有填错CompileError-程序不能通过编译.RunTimeError-程序运行过程中出现非正常中断.MemoryLimitExceeded-内存使用量超过裁判规定的上限.OutputLimitExceeded-输出数据量过大,多半死循环了TimeLimitExceeded-运行超过时限还没有得到输出结果.WrongAnswer-答案错误.PresentationE