十大经典算法.doc

最近，有人在StackExchange上发起了提问，向网友们征集当今世界最为经典的十大算法。众人在一大堆入围算法中进行投票，最终得出了呼声最高的以下十个算法。来自圣经的十大算法：发起人的描述：来自圣经的证明收集了数十个简洁而优雅的数学证明，迅速赢得了大批数学爱好者的追捧。如果还有一本来自圣经的算法，哪些算法会列入其中呢？现在，朋友们，以下是数十种候选算法，如果你觉得它是当今世界最经典的算法，就请您为它投一票.最终产生了下面得票数最高的十大经典算法（投票数统计截止到2011年3月7日）：声明：有一点，希望读者明白，以下票选出来的十大算法不等同于，也绝非就是当今世界最为经典的十大算法。-第十名：Huffman coding（霍夫曼编码）霍夫曼编码(Huffman Coding)是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的，并发表于一种构建极小多余编码的方法（A Method for the Construction of Minimum-Redundancy Codes）一文。第九名：Binary Search （二分查找）在一个有序的集合中查找元素，可以使用二分查找算法，也叫二分搜索。二分查找算法先比较位于集合中间位置的元素与键的大小，有三种情况（假设集合是从小到大排列的）：1. 键小于中间位置的元素，则匹配元素必在左边（如果有的话），于是对左边的区域应用二分搜索。 2. 键等于中间位置的元素，所以元素找到。 3. 键大于中间位置的元素，则匹配元素必在右边（如果有的话），于是对右边的区域应用二分搜索。 另外，当集合为空，则代表找不到。第八名：Miller-Rabin作的类似的试验测试这个想法是利用素数的性质(如使用费马大定理)的小概率寻找见证不数素数。如果没有证据是足够的随机检验后发现,这一数字为素数。第七名：Depth First Search、Breadth First Search（深度、广度优先搜索）它们是许多其他算法的基础。关于深度、广度优先搜索算法的具体介绍，请参考此文：教你通透彻底理解：BFS和DFS优先搜索算法。第六名：Gentrys Fully Homomorphic Encryption Scheme（绅士完全同态加密机制）算法。此算法很漂亮，它允许第三方执行任意加密数据运算得不到私钥（不是很了解）。第五名：Floyd-Warshall all-pairs最短路径算法关于此算法的介绍，可参考我写的此文：几个最短路径算法比较（/v_JULY_v/archive/2011/02/12/6181485.aspx）。d: 二维数组. di,j最小花费、或最短路径的邻边。1. forkfrom1ton: 2. forifrom1ton: 3. forjfrom1ton: 4. di,j=min(di,j,di,k+dk,j)第四名：Quicksort（快速排序）快速排序算法几乎涵盖了所有经典算法的所有榜单。它曾获选二十世纪最伟大的十大算法（参考这：细数二十世纪最伟大的10大算法）。关于快速排序算法的具体介绍，请参考我写的这篇文章：一之续、快速排序算法的深入分析。第三名：BFPRT 算法1973 年，Blum、Floyd、Pratt、Rivest、Tarjan集体出动，合写了一篇题为 “Time bounds for selection” 的论文，给出了一种在数组中选出第 k 大元素的算法，俗称中位数之中位数算法。依靠一种精心设计的 pivot 选取方法，该算法从理论上保证了最坏情形下的线性时间复杂度，打败了平均线性、最坏 O(n2) 复杂度的传统算法。一群大牛把递归算法的复杂度分析玩弄于骨掌股掌之间，构造出了一个当之无愧的来自圣经的算法。我在这里简单介绍下在数组中选出第k大元素的时间复杂度为O（N）的算法：类似快排中的分割算法：1. 每次分割后都能返回枢纽点在数组中的位置s,然后比较s与k的大小 2. 若大的话，则再次递归划分arrays.n， 3. 小的话，就递归arrayleft.s-1 /s为中间枢纽点元素。 4. 否则返回arrays，就是partition中返回的值。 /就是要找到这个s。 5. 找到符合要求的s值后，再遍历输出比s小的那一边的元素。 6. 各位可参考在：算法导论上，第九章中，以期望线性时间做选择一节中，我找到了这个 寻找数组中第k小的元素的，平均时间复杂度为O（N）的证明：上述程序的期望运行时间，最后证明可得O(n)，且假定元素是不同的。 第二名：Knuth-Morris-Pratt字符串匹配算法关于此算法的介绍，请参考此文：六、教你从头到尾彻底理解KMP算法。KMP算法曾经落选于二十世纪最伟大的十大算法，但人们显然不能接受，如此漂亮、高效的KMP算法竟然会落选。所以，此次最终投票产出生，KMP算法排到了第二名。第一名：Union-find严格地说，并查集是一种数据结构，它专门用来处理集合的合并操作和查询操作。并查集巧妙地借用了树结构，使得编程复杂度降低到了令人难以置信的地步；用上一些递归技巧后，各种操作几乎都能用两行代码搞定。而路径压缩的好主意，更是整个数据结构的画龙点睛之笔。并查集的效率极高，单次操作的时间复杂度几乎可以看作是常数级别；但由于数据结构的实际行为难以预测，精确的时间复杂度分析需要用到不少高深的技巧。并行查找，最终占据了此份榜单的第一名。补充：前三名的投票数，只相差4票，8票。所以这个排名日后还会不断有所变化。但不管最终结果怎样，这前十名的算法已经基本敲定了。原投票网址：/questions/189/algorithms-from-the-book。-怎么样，上文那些算法，你是否熟悉?如果，现在，我给你一个投票权，你会把票投给哪一个算法列?ok，咱们也来一次投票吧，请把你的意见，决定权写在本文下面的评论里：我把已经产生的前十名的算法，再写在下面，方便投票：一、Huffman coding（霍夫曼编码）。二、Binary Search （二分查找）。三、Miller-Rabin作的类似的试验测试。四、Depth First Search（深度优先搜索）。五、绅士完全同态加密机制六、Floyd-Warshall all-pairs最短路径算法。七、Quicksort（快速排序）。八、BFPRT 算法。九、Knuth-Morris-Pratt字符串匹配算法。十、Union-find。为了让大家有更多的选择，我再贴出其它几种同样经典但暂时未能排进上述榜单前十名的候选算法：十一、Cooley-Tukey FFT算法。快速傅里叶变换算法。关于傅里叶变换算法的介绍，请参考此文：十、从头到尾彻底理解傅里叶变换算法、上。十二、linear programming，线性规划。十三、Dijkstra算法。具体介绍，参考此文：二之续、彻底理解Dijkstra算法。十四、Merge Sort。归并排序。十五、FordFulkerson算法。网络最大流算法。十六、辗转相除法。在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法，即求两个正整数之最大公因子的算法。此算法作为TAOCP第一个算法被阐述，足见此算法被重视的程度。它是已知最古老的算法, 其可追溯至3000年前。辗转相除法首次出现于欧几里得的几何原本（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的九章算术。扩展的辗转相除法则构造性地证明了，对任意整数a和b ，存在一对x、y使得 ax + by = gcd(a, b) 。十七、RSA加密演算法。一种加密算法，日后再做详细介绍。十八、遗传算法。可参考本人写的关于GA 算法的这篇文章：七、遗传算法 透析GA本质。十九、最大期望（EM）算法。在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。二十、数据压缩数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度，达到增大数据密度，最终使数据的存储空间减少的技术。数据压缩在文件存储和分布式系统领域有着十分广泛的应用。数据压缩也代表着尺寸媒介容量的增大和网络带宽的扩展。二十一、Hash函数Hash Function是一种从任何一种数据中创建小的数字“指纹”的方法。该函数将数据打乱混合，重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。二十二、Dynamic Programming（动态规划）。关于动态规划的粗略介绍，请参考此文：三、dynamic programming