当今世界最受人们重视的十大经典算法

csdnfelix 2011-05-17

当今世界,已经被发现或创造的经典算法数不胜数。如果,一定要投票选出你最看重的十大算法,你会作何选择列?

最近,有人在StackExchange上发起了提问,向网友们征集当今世界最为经典的十大算法。众人在一大堆入围算法中进行投票,最终得出了呼声最高的以下十个算法。

来自圣经的十大算法:

发起人的描述:《来自圣经的证明》收集了数十个简洁而优雅的数学证明,迅速赢得了大批数学爱好者的追捧。如果还有一本《来自圣经的算法》,哪些算法会列入其中呢?现在,朋友们,以下是数十种候选算法,如果你觉得它是当今世界最经典的算法,就请您为它投一票.....

最终产生了下面得票数最高的十大经典算法:

第十名: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优先搜索算法。

第六名:Gentry's Fully Homomorphic Encryption Scheme(绅士完全同态加密机制)算法。

此算法很漂亮,它允许第三方执行任意加密数据运算得不到私钥(不是很了解)。

第五名:Floyd-Warshall all-pairs最短路径算法

关于此算法的介绍,可参考我写的此文:几个最短路径算法比较

d[]: 二维数组. d[i,j]最小花费、或最短路径的邻边。

for k from 1 to n:  



for i from 1 to n:  




for j from 1 to n:  



d[i,j] = min(d[i,j], d[i,k] + d[k,j]) 

第四名:Quicksort(快速排序)

快速排序算法几乎涵盖了所有经典算法的所有榜单。它曾获选二十世纪最伟大的十大算法(参考这:细数二十世纪最伟大的10大算法)。关于快速排序算法的具体介绍,请参考我写的这篇文章:一之续、快速排序算法的深入分析。

第三名:BFPRT 算法

1973 年,Blum、Floyd、Pratt、Rivest、Tarjan集体出动,合写了一篇题为 “Time bounds for selection” 的论文,给出了一种在数组中选出第 k 大元素的算法,俗称"中位数之中位数算法"。依靠一种精心设计的 pivot 选取方法,该算法从理论上保证了最坏情形下的线性时间复杂度,打败了平均线性、最坏 O(n^2) 复杂度的传统算法。一群大牛把递归算法的复杂度分析玩弄于骨掌股掌之间,构造出了一个当之无愧的来自圣经的算法。

我在这里简单介绍下在数组中选出第k大元素的时间复杂度为O(N)的算法:

类似快排中的分割算法:

每次分割后都能返回枢纽点在数组中的位置s,然后比较s与k的大小

若大的话,则再次递归划分array[s..n],

小的话,就递归array[left...s-1] //s为中间枢纽点元素。

否则返回array[s],就是partition中返回的值。 //就是要找到这个s。

找到符合要求的s值后,再遍历输出比s小的那一边的元素。

各位可参考在:算法导论上,第九章中,以期望线性时间做选择,一节中,

我找到了这个 寻找数组中第k小的元素的,平均时间复杂度为O(N)的证明:上述程序的期望运行时间,最后证明可得O(n),且假定元素是不同的。

第二名:Knuth-Morris-Pratt字符串匹配算法

关于此算法的介绍,请参考此文:六、教你从头到尾彻底理解KMP算法。KMP算法曾经落选于二十世纪最伟大的十大算法,但人们显然不能接受,如此漂亮、高效的KMP算法竟然会落选。所以,此次最终投票产出生,KMP算法排到了第二名。

第一名:Union-find

严格地说,并查集是一种数据结构,它专门用来处理集合的合并操作和查询操作。并查集巧妙地借用了树结构,使得编程复杂度降低到了令人难以置信的地步;用上一些递归技巧后,各种操作几乎都能用两行代码搞定。而路径压缩的好主意,更是整个数据结构的画龙点睛之笔。并查集的效率极高,单次操作的时间复杂度几乎可以看作是常数级别;但由于数据结构的实际行为难以预测,精确的时间复杂度分析需要用到不少高深的技巧。并行查找,最终占据了此份榜单的第一名。

补充:前三名的投票数,只相差4票,8票。所以这个排名日后还会不断有所变化。但不管最终结果怎样,这前十名的算法已经基本敲定了。

相关推荐

优化算法 / 0评论 2020-11-13