前久发了一个帖子(怎样才算熟练掌握数据结构、常用算法？)
好象发出了大家的心声,感兴趣的人比较多,相信很多人想从帖子里找到答案,
此帖子把比较好的几个总结出来方便大家学习.
散分
前20位都有分.
节约版
------------------------------------------------------
bigbug9002:
不可能都完全记住那么多的算法.
常用算法,拿过来就可以写出来
不常用的,拿起书来,看10分钟,就能理解算法(因为以前记过).
对以前没有记过的算法,就不好说了,难的可能要研究好几天.
这样就可以了. 应该熟练掌握的常用的算法应该有:
各种排序算法（插入排序、冒泡排序、选择排序，快速排序，堆排序，归并排序）
线性表(一般的线性表,栈,队列)的插入和删除
二叉树的遍历（前序，中序，后序）
图的遍历（深度优先，广度优先）
二分法查找，排序二叉树，Hash查找（处理冲突的方法）。 个人观点.
------------------------------------------------------***版
------------------------------------------------------
yeka
http://www.douban.com/review/2130819/ 数据结构和算法是程序的根本——为什么？！
2009-07-10 22:44:19 来自: BlueDavy (努力看书)
编程之美--微软技术面试心得的评论 转自博客。
应该是差不多两个月前收到了这本书，一直到最近才抽出时间来看了下，这本书的开篇的第一题现在基本已经成了经典中的经典了，相信很多人都因为这个控制CPU使用率的题从而买了这本书的，在我自己看过这本书后我同时相信买了这本书的人应该会觉得非常的值得，要写出合理实现需求、高性能以及大数据量的程序，数据结构和算法就成为关键要素了，这本书用简短的题目给大家回顾了一些经典的算法。
首先，这本书以微软面试题吸引了众多人的梦想，毕竟微软的技术强这是毋庸置疑的，面试过不少的人，自己也觉得面试题真的是非常的难出，毕竟面试要求的是面试官在短短的几十分钟或一个小时内考察面试者是否符合公司的要求，在看《编程之美》序中看到邹欣因为面试一个进行过CPU压力测试的面试者时，想到了那道经典的控制CPU使用率的问题，从这道题我们可以看到考察面试人员对一项技术掌握是否精通的考评标准，我觉得和我之前写的那几篇关于如何考察面试者是否达到了精通的一些题是差不多同样的道理，毕竟精通这两个字不是随便就能达到的，从《编程之美》这本书中也看到了微软在考察面试者能力时的要求是非常高的，彻底颠覆了我对微软亚洲研究院这边的看法，:)，另外从这本书列举的一些题目可以看出微软出的面试题的水准确实是相当高的，可以做到在短时间内充分的考察面试者在该方面的能力，我想这也是大部分面试官在出面试题时需要尽量达到的目标。
以上是从面试题的角度看这本书，接着来看看这本书的内容，估计现在书中的很多题目都已经成为了业界讨论的焦点话题了，像控制CPU使用率、双线程下载、数独游戏、24点、电梯调度、连连看等等一系列经典的题目，这些题目对于纠正目前很多业界从业人士对数据结构和算法不重视的看法应该是会有帮助的，当我在做中小型企业应用开发的时候，我也一直认为数据结构和算法即使不掌握也是没什么关系，而现在我也非常重视数据结构和算法了，现在在做面试的时候对于科班出身的同学，我会问问数据结构、算法的成绩，另外还有一个和书中同样的看法就是，数学非常重要，写程序和我们在学数学时解方程其实没有太大的差别，所以我认为数学学的好的人大部分是比较适合从事软件行业的，:)，仅为个人看法，书中在数学方面也列举了不少经典的题目，像寻找发帖“水王”、寻找数组中的最大值和最小值等等。
总体而言，这本书并不是说要告诉大家面试微软的技巧，去死记硬背这些答案，那没有多少意义的，毕竟面试官更多的其实考察的是面试者的逻辑思维能力以及对相关知识的掌握程度，何况面试官通常都是会调整题目的，并不是说每次问的都是一样的,我想这本书能够给大家带来的最多的参考就是理解什么才是真正的精通，另外也给大家呈现了数据结构和算法为什么会是程序的根本，而对于要实现高性能以及海量数据处理的程序这些就更为关键了，因此个人觉得除了这本书之外，数据结构和算法相关的书即使不是科班出身的人也是应该仔细学习学习的。
------------------------------------------------------
好象发出了大家的心声,感兴趣的人比较多,相信很多人想从帖子里找到答案,
此帖子把比较好的几个总结出来方便大家学习.
散分
前20位都有分.
节约版
------------------------------------------------------
bigbug9002:
不可能都完全记住那么多的算法.
常用算法,拿过来就可以写出来
不常用的,拿起书来,看10分钟,就能理解算法(因为以前记过).
对以前没有记过的算法,就不好说了,难的可能要研究好几天.
这样就可以了. 应该熟练掌握的常用的算法应该有:
各种排序算法（插入排序、冒泡排序、选择排序，快速排序，堆排序，归并排序）
线性表(一般的线性表,栈,队列)的插入和删除
二叉树的遍历（前序，中序，后序）
图的遍历（深度优先，广度优先）
二分法查找，排序二叉树，Hash查找（处理冲突的方法）。 个人观点.
------------------------------------------------------***版
------------------------------------------------------
yeka
http://www.douban.com/review/2130819/ 数据结构和算法是程序的根本——为什么？！
2009-07-10 22:44:19 来自: BlueDavy (努力看书)
编程之美--微软技术面试心得的评论 转自博客。
应该是差不多两个月前收到了这本书，一直到最近才抽出时间来看了下，这本书的开篇的第一题现在基本已经成了经典中的经典了，相信很多人都因为这个控制CPU使用率的题从而买了这本书的，在我自己看过这本书后我同时相信买了这本书的人应该会觉得非常的值得，要写出合理实现需求、高性能以及大数据量的程序，数据结构和算法就成为关键要素了，这本书用简短的题目给大家回顾了一些经典的算法。
首先，这本书以微软面试题吸引了众多人的梦想，毕竟微软的技术强这是毋庸置疑的，面试过不少的人，自己也觉得面试题真的是非常的难出，毕竟面试要求的是面试官在短短的几十分钟或一个小时内考察面试者是否符合公司的要求，在看《编程之美》序中看到邹欣因为面试一个进行过CPU压力测试的面试者时，想到了那道经典的控制CPU使用率的问题，从这道题我们可以看到考察面试人员对一项技术掌握是否精通的考评标准，我觉得和我之前写的那几篇关于如何考察面试者是否达到了精通的一些题是差不多同样的道理，毕竟精通这两个字不是随便就能达到的，从《编程之美》这本书中也看到了微软在考察面试者能力时的要求是非常高的，彻底颠覆了我对微软亚洲研究院这边的看法，:)，另外从这本书列举的一些题目可以看出微软出的面试题的水准确实是相当高的，可以做到在短时间内充分的考察面试者在该方面的能力，我想这也是大部分面试官在出面试题时需要尽量达到的目标。
以上是从面试题的角度看这本书，接着来看看这本书的内容，估计现在书中的很多题目都已经成为了业界讨论的焦点话题了，像控制CPU使用率、双线程下载、数独游戏、24点、电梯调度、连连看等等一系列经典的题目，这些题目对于纠正目前很多业界从业人士对数据结构和算法不重视的看法应该是会有帮助的，当我在做中小型企业应用开发的时候，我也一直认为数据结构和算法即使不掌握也是没什么关系，而现在我也非常重视数据结构和算法了，现在在做面试的时候对于科班出身的同学，我会问问数据结构、算法的成绩，另外还有一个和书中同样的看法就是，数学非常重要，写程序和我们在学数学时解方程其实没有太大的差别，所以我认为数学学的好的人大部分是比较适合从事软件行业的，:)，仅为个人看法，书中在数学方面也列举了不少经典的题目，像寻找发帖“水王”、寻找数组中的最大值和最小值等等。
总体而言，这本书并不是说要告诉大家面试微软的技巧，去死记硬背这些答案，那没有多少意义的，毕竟面试官更多的其实考察的是面试者的逻辑思维能力以及对相关知识的掌握程度，何况面试官通常都是会调整题目的，并不是说每次问的都是一样的,我想这本书能够给大家带来的最多的参考就是理解什么才是真正的精通，另外也给大家呈现了数据结构和算法为什么会是程序的根本，而对于要实现高性能以及海量数据处理的程序这些就更为关键了，因此个人觉得除了这本书之外，数据结构和算法相关的书即使不是科班出身的人也是应该仔细学习学习的。
------------------------------------------------------
------------------------------------------------------
baihacker转一个搞ACM需要的掌握的算法.
要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.
适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,
发挥自己的长处,这才是重要的.
第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，
因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打
出来.
1.最短路(Floyd、Dijstra,BellmanFord)
2.最小生成树(先写个prim,kruscal要用并查集，不好写)
3.大数（高精度）加减乘除
4.二分查找. (代码可在五行以内)
5.叉乘、判线段相交、然后写个凸包.
6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)
7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.
8. 调用系统的qsort, 技巧很多，慢慢掌握.
9. 任意进制间的转换 第二阶段：练习复杂一点，但也较常用的算法。
如：
1. 二分图匹配（匈牙利），最小路径覆盖
2. 网络流，最小费用流。
3. 线段树.
4. 并查集。
5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp
6.博弈类算法。博弈树，二进制法等。
7.最大团，最大独立集。
8.判断点在多边形内。
9. 差分约束系统.
10. 双向广度搜索、A*算法，最小耗散优先.
相关的知识 图论 路径问题
0/1边权最短路径
BFS
非负边权最短路径（Dijkstra）
可以用Dijkstra解决问题的特征
负边权最短路径
Bellman-Ford
Bellman-Ford的Yen-氏优化
差分约束系统
Floyd
广义路径问题
传递闭包
极小极大距离 / 极大极小距离
Euler Path / Tour
圈套圈算法
混合图的 Euler Path / Tour
Hamilton Path / Tour
特殊图的Hamilton Path / Tour 构造 生成树问题
最小生成树
第k小生成树
最优比率生成树
0/1分数规划
度限制生成树 连通性问题
强大的DFS算法
无向图连通性
割点
割边
二连通分支
有向图连通性
强连通分支
2-SAT
最小点基 有向无环图
拓扑排序
有向无环图与动态规划的关系 二分图匹配问题
一般图问题与二分图问题的转换思路
最大匹配
有向图的最小路径覆盖
0 / 1矩阵的最小覆盖
完备匹配
最优匹配
稳定婚姻 网络流问题
网络流模型的简单特征和与线性规划的关系
最大流最小割定理
最大流问题
有上下界的最大流问题
循环流
最小费用最大流 / 最大费用最大流 弦图的性质和判定
组合数学 解决组合数学问题时常用的思想
逼近
递推 / 动态规划
概率问题
Polya定理
计算几何 / 解析几何 计算几何的核心：叉积 / 面积
解析几何的主力：复数 基本形
点
直线，线段
多边形 凸多边形 / 凸包
凸包算法的引进，卷包裹法 Graham扫描法
水平序的引进，共线凸包的补丁 完美凸包算法 相关判定
两直线相交
两线段相交
点在任意多边形内的判定
点在凸多边形内的判定 经典问题
最小外接圆
近似O(n)的最小外接圆算法
点集直径
旋转卡壳，对踵点
多边形的三角剖分
数学 / 数论 最大公约数
Euclid算法
扩展的Euclid算法
同余方程 / 二元一次不定方程
同余方程组 线性方程组
高斯消元法
解mod 2域上的线性方程组
整系数方程组的精确解法 矩阵
行列式的计算
利用矩阵乘法快速计算递推关系 分数
分数树
连分数逼近 数论计算
求N的约数个数
求phi(N)
求约数和
快速数论变换
…… 素数问题
概率判素算法
概率因子分解
数据结构 组织结构
二叉堆
左偏树
二项树
胜者树
跳跃表
样式图标
斜堆
reap 统计结构
树状数组
虚二叉树
线段树
矩形面积并
圆形面积并 关系结构
Hash表
并查集
路径压缩思想的应用 STL中的数据结构
vector
deque
set / map
动态规划 / 记忆化搜索 动态规划和记忆化搜索在思考方式上的区别 最长子序列系列问题
最长不下降子序列
最长公共子序列
最长公共不下降子序列 一类NP问题的动态规划解法 树型动态规划 背包问题 动态规划的优化
四边形不等式
函数的凸凹性
状态设计
规划方向
线性规划 常用思想 二分 最小表示法 串 KMP Trie结构
后缀树/后缀数组 LCA/RMQ
有限状态自动机理论 排序
选择/冒泡 快速排序 堆排序 归并排序
基数排序 拓扑排序 排序网络
中级:
一.基本算法:
(1)C++的标准模版库的应用. (poj3096,poj3007)
(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
二.图算法:
(1)差分约束系统的建立和求解. (poj1201,poj2983)
(2)最小费用最大流(poj2516,poj2516,poj2195)
(3)双连通分量(poj2942)
(4)强连通分支及其缩点.(poj2186)
(5)图的割边和割点(poj3352)
(6)最小割模型、网络流规约(poj3308, )
三.数据结构.
(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)静态二叉检索树. (poj2482,poj2352)
(3)树状树组(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)并查集的高级应用. (poj1703,2492)
(6)KMP算法. (poj1961,poj2406)
四.搜索
(1)最优化剪枝和可行性剪枝
(2)搜索的技巧和优化 (poj3411,poj1724)
(3)记忆化搜索(poj3373,poj1691)
五.动态规划
(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)
(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)
六.数学
(1)组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.
(2)数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
(3)计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)随机化算法(poj3318,poj2454)
(5)杂题.
(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.
(1)坐标离散化.
(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多边形的内核(半平面交)(poj3130,poj3335)
(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高级:
一.基本算法要求:
(1)代码快速写成,精简但不失风格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保证正确性和高效性. poj3434
二.图算法:
(1)度限制最小生成树和第K最短路. (poj1639)
(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最优比率生成树. (poj2728)
(4)最小树形图(poj3164)
(5)次小生成树.
(6)无向图、有向图的最小环
三.数据结构.
(1)trie图的建立和应用. (poj2778)
(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法
(RMQ+dfs)).(poj1330)
(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的
目的). (poj2823)
(4)左偏树(可合并堆).
(5)后缀树(非常有用的数据结构,也是赛区考题的热点).
(poj3415,poj3294)
四.搜索
(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)
五.动态规划
(1)需要用数据结构优化的动态规划.
(poj2754,poj3378,poj3017)
(2)四边形不等式理论.
(3)较难的状态DP(poj3133)
六.数学
(1)组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
(2)博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.
(1)半平面求交(poj3384,poj2540)
(2)可视图的建立(poj2966)
(3)点集最小圆覆盖.
(4)对踵点(poj2079)
八.综合题.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263) 初期:
一.基本算法:
(1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法. (4)递推.
(5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.图算法:
(1)图的深度优先遍历和广度优先遍历.
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓扑排序 (poj1094)
(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
(6)最大流的增广路算法(KM算法). (poj1459,poj3436)
三.数据结构.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
(3)简单并查集的应用.
(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼树(poj3253)
(6)堆
(7)trie树(静态建树、动态建树) (poj2513)
四.简单搜索
(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.动态规划
(1)背包问题. (poj1837,poj1276)
(2)型如下表的简单DP(可参考lrj的书 page149):
1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学
(1)组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
(2)数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
(3)计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.
(1)几何公式.
(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)
------------------------------------------------------
要求的编程语言五花八门就产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习最新的语言、
技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学，但是学习计算机算法和理
论更重要，因为计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算
法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在“开复学生网”上，有位
同学生动地把这些基础课程比拟为“内功”，把新的语言、技术、标准比拟为“外功”。整天赶时髦的人最后只懂
得招式，没有功力，是不可能成为高手的。算法与我
当我在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的核心优势
上面的例子在Google里就要算是小case了！每天Google的网站要处理十亿个以上的搜索，GMail要储存几千
万用户的2G邮箱，Google Earth要让数十万用户同时在整个地球上遨游，并将合适的图片经过互联网提交给
每个用户。如果没有好的算法，这些应用都无法成为现实。在这些的应用中，哪怕是最基本的问题都会给传统的
计算带来很大的挑战。例如，每天都有十亿以上的用户访问Google的网站，使用Google的服务，也产生很多很
多的日志(Log)。因为Log每份每秒都在飞速增加，我们必须有聪明的办法来进行处理。我曾经在面试中问过关
于如何对Log进行一些分析处理的问题，有很多面试者的回答虽然在逻辑上正确，但是实际应用中是几乎不可行
的。按照它们的算法，即便用上几万台机器，我们的处理速度都根不上数据产生的速度。那么Google是如何解决
这些问题的？首先，在网络时代，就算有最好的算法，也要能在并行计算的环境下执行。在Google的数据中心，
我们使用的是超大的并行计算机。但传统的并行算法运行时，效率会在增加机器数量后迅速降低，也就是说，十
台机器如果有五倍的效果，增加到一千台时也许就只有几十倍的效果。这种事半功倍的代价是没有哪家公司可以
负担得起的。而且，在许多并行算法中，只要一个结点犯错误，所有计算都会前功尽弃。那么Google是如何开发
出既有效率又能容错的并行计算的呢？Google最资深的计算机科学家Jeff Dean认识到，Google所需的绝大
部分数据处理都可以归结为一个简单的并行算法：Map and Reduce
(http://labs.google.com/papers/mapreduce.html。这个算法能够在很多种计算中达到相当高的效率，
而且是可扩展的（也就是说，一千台机器就算不能达到一千倍的效果，至少也可以达到几百倍的效果）。
Map and Reduce的另外一大特色是它可以利用大批廉价的机器组成功能强大的server farm。最后，它的容
错性能异常出色，就算一个server farm宕掉一半，整个fram依然能够运行。正是因为这个天才的认识，才有了
Map and Reduce算法。借助该算法，Google几乎能无限地增加计算量，与日新月异的互联网应用一同成长。算法并不局限于计算机和网络
举一个计算机领域外的例子：在高能物理研究方面，很多实验每秒钟都能几个TB的数据量。但因为处理能力和存
储能力的不足，科学家不得不把绝大部分未经处理的数据丢弃掉。可大家要知道，新元素的信息很有可能就藏在
我们来不及处理的数据里面。同样的，在其他任何领域里，算法可以改变人类的生活。例如人类基因的研究，就可
能因为算法而发明新的医疗方式。在国家安全领域，有效的算法可能避免下一个911的发生。在气象方面，
算法可以更好地预测未来天灾的发生，以拯救生命。所以，如果你把计算机的发展放到应用和数据飞速增长的大
环境下，你一定会发现；算法的重要性不是在日益减小，而是在日益加强。