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

发表于:2011-4-11 10:06

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:July    来源:51Testing软件测试网采编

  最近,有人在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]最小花费、或最短路径的邻边。

  1. for k from 1 to n:  
  2.     for i from 1 to n:  
  3.       for j from 1 to n:  
  4.         d[i,j] = min(d[i,j], d[i,k] + d[k,j])

31/3123>
《2023软件测试行业现状调查报告》独家发布~

精彩评论

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号