`
xbcoil
  • 浏览: 126274 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

最受人们重视的十大经典算法

阅读更多

转自:http://blog.csdn.net/v_JULY_v,结构之法、算法之道

 

当今世界,已经被发现或创造的经典算法数不胜数。如果,一定要投票选出你最看重的十大算法,你会作何选择列?
    最近,有人在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]最小花费、或最短路径的邻边。

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票。所以这个排名日后还会不断有所变化。但不管最终结果怎样,这前十名的算法已经基本敲定了。
    原投票网址http://cstheory.stackexchange.com/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。归并排序。
十五、Ford–Fulkerson算法。网络最大流算法。
十六辗转相除法
      在数学中,辗转相除法,又称欧几里得算法,是求最大公约数的算法,即求两个正整数之最大公因子的算法。此算法作为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

 

分享到:
评论
2 楼 xbcoil 2011-03-15  
v_JULY_v 写道
您好,我是此博客:http://blog.csdn.net/v_JULY_v,结构之法、算法之道的博主本人July,希望您在转载本人的原创文章时,请注明作者本人及文章出处。这涉及到一个版权的问题。谢谢。July、敬上。二零一一年三月十三日。



嗯。会的。
1 楼 v_JULY_v 2011-03-13  
您好,我是此博客:http://blog.csdn.net/v_JULY_v,结构之法、算法之道的博主本人July,希望您在转载本人的原创文章时,请注明作者本人及文章出处。这涉及到一个版权的问题。谢谢。July、敬上。二零一一年三月十三日。

相关推荐

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

    根据提供的信息,我们可以总结出以下有关“当今世界最受人们重视的十大经典算法”的知识点: ### 霍夫曼编码(Huffman Coding) - **定义**:霍夫曼编码是一种广泛应用于无损数据压缩领域的熵编码算法。该算法由...

    数学建模十大经典算法

    【数学建模十大经典算法详解】 数学建模是利用数学工具和方法解决实际问题的过程,其涉及多种算法,包括但不限于: 1. **蒙特卡罗算法**:此算法基于概率和统计,通过大量随机抽样来近似求解复杂问题。在建模中,...

    大数据十大经典算法

    大数据十大经典算法kNN讲解PPT,很详细哦!

    大数据十大经典算法讲解

    大数据十大经典算法讲解,大数据处理的入门级算法,受用!

    十大经典排序算法堆排序详细图解(通俗易懂)

    十大经典排序算法堆排序详细图解(通俗易懂)十大经典排序算法堆排序详细图解(通俗易懂)十大经典排序算法堆排序详细图解(通俗易懂)十大经典排序算法堆排序详细图解(通俗易懂)十大经典排序算法堆排序详细图解...

    数据挖掘领域的十大经典算法原理及应用.docx

    数据挖掘领域的十大经典算法在信息技术和互联网行业中具有广泛的应用,这些算法通过处理和解析大量数据,帮助企业和研究者发现潜在的模式、趋势和关联。以下是这些算法的详细说明: 1. **C4.5**:C4.5是ID3算法的...

    机器学习十大经典算法

    k-means算法简单、快速,但需要预先指定聚类的数目k,且对初始值的选择敏感,容易陷入局部最优解。 总结来说,机器学习中的决策树算法和聚类算法是数据分类和分割的两大核心技术。其中,决策树算法特别适用于分类...

    _大数据十大经典算法可视化实例教学系统研究与实现.caj

    _大数据十大经典算法可视化实例教学系统研究与实现.caj

    Java十大经典排序算法

    十种经典的排序算法,桶排序,快速排序,计数排序,插入排序,希尔排序,堆排序等的Java描述与动图示意

    机器学习十大经典算法总结

    在机器学习领域,有多种经典算法,每种算法都有其独特的原理和应用领域,本文将总结十个在机器学习领域广为人知的经典算法,并详细解释每个算法的核心思想、工作原理、适用情况及优缺点。 1. C4.5算法 C4.5算法是...

    matlab的十大经典算法

    数学建模竞赛必备教程 含程序

    十大经典算法机器学习及其程序实现

    十大经典算法机器学习及其程序实现,每个算法的核心思想、工作原理、适用情况及优缺点介绍的很详细。

    十大排序算法

    常见10大算法,从原理,动图解析到代码实现,逐步分析,让你轻松入门算法

    WORD版数据挖掘十大经典算法.doc

    WORD版数据挖掘十大经典算法.doc

    matlab经典算法的程序源码 数学建模算法汇总资料.zip

    十大算法讲义.pdf 排队模型.pdf 数学建模算法全收录.pdf 数学建模算法大全.pdf 算法大全第01章__线性规划.pdf 算法大全第02章_整数规划.pdf 算法大全第03章-非线性规划.pdf 算法大全第04章__动态规划.pdf 算法大全第...

    Matlab十大算法

    十大算法\Floyd算法\中国数学建模-数学工具-Floyd最短路算法的MATLAB程序.txt 十大算法\免疫算法.txt 十大算法\分治算法 十大算法\分治算法\c程序.txt 十大算法\分治算法\中国数学建模-编程交流-分治算法_1.txt ...

    机器学习的十大经典算法

    K-means算法简单有效,但在实际应用中也存在一些局限性,如需要预先设定簇的数量k,且算法结果容易受到初始簇中心选择的影响,可能会陷入局部最优解。为了克服这些问题,研究者们提出了多种改进算法,如K-means++...

Global site tag (gtag.js) - Google Analytics