最近,有人在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优先搜索算法。
第六名:Gentry's Fully Homomorphic Encryption Scheme(绅士完全同态加密机制)算法。
此算法很漂亮,它允许第三方执行任意加密数据运算得不到私钥(不是很了解)。
第五名:Floyd-Warshall all-pairs最短路径算法
关于此算法的介绍,可参考我写的此文:几个最短路径算法比较(http://blog.csdn.net/v_JULY_v/archive/2011/02/12/6181485.aspx)。
d[]: 二维数组. d[i,j]最小花费、或最短路径的邻边。
|