当今世界最为经典的十大算法--投票进行时
作者:July、二零一一年三月七日。
内容说明:
I、 本文原名为:当今世界最受人们重视的十大经典算法,后改为如上题目。
II、本文分为俩部分:
第一部分、来自圣经的十大算法:为某网友票选出来的十个来自圣经的算法。
第二部分、当今世界最为经典的十大算法--投票进行时:是恳请本文的读者为您心目中当今世界最为经典的算法投上一票,最终在本BLOG内票选产生当今世界最为经典的十大算法(投票截止日期,后年此刻,即二零一三年三月七日)。非常感谢大家。
----------------------------------------
第一部分、来自圣经的十大算法
当今世界,已经被发现或创造的经典算法数不胜数。如果,一定要投票选出你最看重的十大算法,你会作何选择列?
曾有人在StackExchange上发起了提问,向网友们征集当今世界最为经典的十大算法。众人在一大堆入围算法中进行投票,最终得出了票数最高的以下十个算法。
来自圣经的十大算法:
发起人的描述:《来自圣经的证明》收集了数十个简洁而优雅的数学证明,迅速赢得了大批数学爱好者的追捧。如果还有一本《来自圣经的算法》,哪些算法会列入其中呢?现在,朋友们,以下是数十种候选算法,如果你觉得它是当今世界最经典的算法,就请您为它投一票.....
最终在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,那么,现在,我给你一个投票权,你会把票投给哪一个算法列?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。
二十三、堆排序算法。
堆排序算法作为一种快速稳定的算法,其平均时间复杂度(最坏也为)O(n*lgn)。当然,在实际应用中,一个实现的好的快速排序算法仍然要优于堆排序算法。不过,堆数据结构还可以作为高效的优先级队列。对堆排序算法作简单了解,可参考这:堆排序算法。
二十四、递归与回溯算法。此俩个算法,相信各位比较熟悉,在此不做赘述。
二十五、最长公共子序列
最长公共子序列,英文缩写为LCS(Longest Common Subsequence)。其定义是,一个数列 S ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。
动态规划的一个计算最长公共子序列的方法如下:
以两个序列 X、Y 为例子:
设有二维数组 f[i][j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有:
f[1][1] = same(1,1)
f[i][j] = max{f[i-1][j-1]+same(i,j),f[i-1][j],f[i][j-1]}
其中,same(a,b)当 X 的第 a 位与 Y 的第 b 位完全相同时为“1”,否则为“0”。
此时,f[i][j]中最大的数便是 X 和 Y 的最长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。
该算法的空间、时间复杂度均为O(n2),经过优化后,空间复杂度可为O(n),时间复杂度为O(nlogn)。更多详情,参见之前写的一篇拙文(不过,鉴于写的糟,日后会重写):三、dynamic programming。
二十六、红黑树的算法与实现
关于红黑树,linux内核中有实现,本BLOG内也已经写了4篇红黑树系列的文章。详情,请参考:五(续)、教你透彻了解红黑树。
二十七、A*搜寻算法。
相对于BFS、Dijkstra 等算法,A*搜寻算法作为一种高效的最短路径搜索算法,如今,已得到日益广泛的应用。初步了解A*搜寻算法的高效及与其它最短路径算法的比较,请参考此文:一(续)、A*,Dijkstra,BFS算法性能比较及A*算法的应用。
二十八、图像特征提取与匹配之SIFT算法
sift,尺度不变特征转换,是一种电脑视觉的算法用来侦测与描述影像中的局部性特征,它在空间尺度中寻找极值点,并提取出其位置、尺度、旋转不变量,此算法由 David Lowe 在1999年所发表,2004年完善总结。关于此算法,请参考如下,粗略介绍:九、图像特征提取与匹配之SIFT算法,利用第三方库编译过程:九(续)、sift算法的编译与实现,c语言一步一步实现sift算法:一、教你一步一步用c语言实现sift算法、上,及一、教你一步一步用c语言实现sift算法、下。
候选经典算法一直在不断增补中,估计最后能达到上100种。...
还犹豫什么列?快投上您宝贵的一票吧。每人限投一票,如果你认为那个算法是最为经典的算法,您就在下面的评论里写上它的序号,及算法名称。
当然,如果上文中不曾出现你认为最经典的算法,你也可以写在评论里,为你钟爱的它投上一票。而后我将考虑您的意见,把您钟爱的算法也作为一种候选算法,添补上去。:D。
最后,我们自己来做一份十大经典算法的排名榜单,也让世界各地的人看看我们中国人的意见。怎么样,还犹豫什么列,赶紧评论、赶紧投票吧...且,投了票的朋友,都有机会免费得到本BLOG第一期文件、第二期、第三期、第..全部博文集锦的CHM 文件(想要的,投票,投完票之后,留下邮箱,好传送。:D。)。
本BLOG版权声明、即日生效:
1、本人和CSDN对本BLOG内所有任何一切内容和文章,享有版权。如需转载,请注明出处及作者本人。
2、本BLOG内任何一篇原创作品,坚决禁止任何盈利性网站转载本BLOG内任何内容。
3、凡是转载本BLOG内任何文章和内容的个人,或网站,一律不注明出处者,本人将永久追踪、永久谴责、永久追究法律责任的一切权利。谢谢。July、二零一一年三月七日,即日起生效。
本文来自CSDN博客,转载请标明出处:
http://blog.csdn.net/v_JULY_v/archive/2011/03/07/6228235.aspx
分享到:
相关推荐
本文将讨论由网友票选的“当今世界最为经典的十大算法”。这些算法不仅在理论上有深远影响,而且在实际应用中也表现出卓越的性能。 1. **霍夫曼编码(Huffman Coding)** 霍夫曼编码是一种无损数据压缩技术,基于...
在这个文档中,作者July列举了根据StackExchange社区投票选出的十大经典算法,这些算法在信息技术领域具有广泛的影响和应用。 1. **霍夫曼编码 (Huffman Coding)**:霍夫曼编码是一种无损数据压缩技术,通过构建...
在当今互联网时代,人们获取信息的途径变得更加多样化,同时也对信息的准确性提出了更高的要求。由于数据来源复杂多样,不同来源对同一实体属性的描述往往存在冲突。为解决这一问题,需要依赖有效的真值发现算法。...
算法通过计算新样本与训练集中每个样本的距离,选取最近的K个邻居,然后根据邻居的类别进行投票,决定新样本的类别。K的选择对结果有显著影响,过大可能导致过平滑,过小可能过于敏感。 算法四:ID3算法 ID3...
随机森林算法利用了包括年龄、性别、教育水平、工作行业和住宅地等多个特征来构建决策树,每棵树基于不同的特征组合进行独立分类,并通过多数投票机制来确定最终的预测结果。实验结果表明,模型能够较为准确地预测...
在当今信息爆炸的时代,有效地对大量文本数据进行分类显得尤为重要。C++作为一种高效、性能强大的编程语言,被广泛用于各种算法的实现,包括机器学习和数据挖掘中的KNN文本分类算法。K-最近邻(K-Nearest Neighbors...
随机森林通过构建多个决策树并进行投票或平均来提高预测的准确性,而AdaBoost则通过赋予前一个模型错误分类的实例更大的权重来不断改进新模型。 机器学习的算法库不仅仅限于上述模型,还包含了支持向量机(SVM)、...
在算法的最后阶段,通过投票机制对选定的特征点进行聚合处理,利用聚类分析将投票结果分组。这样的处理不仅能够有效地抑制噪声干扰,还能够增强特征点集的代表性,从而提高目标中心位置估计的精度。 通过大量实验的...
在当今互联网时代,各种线上互动活动如雨后春笋般涌现,其中投票与抽奖活动是最受欢迎的形式之一。PHP作为一款广泛应用于网页开发的语言,自然成为了构建这类系统的首选工具。本文将深入探讨基于PHP开发的网站版投票...
KNN算法通过计算待分类样本与训练集中所有样本的距离,找到最近的K个邻居,然后根据这些邻居的类别进行投票,决定待分类样本的类别。距离的计算通常采用欧氏距离或曼哈顿距离,但也可以根据实际情况选择其他合适的...
在当今信息时代的背景下,数据挖掘技术已经成为处理大量数据、发现有价值信息的重要手段。本文档“数据挖掘算法在交通数据中的研究分析.pdf”聚焦于数据挖掘技术在交通领域的应用,试图通过算法来科学合理地寻找数据...
### 使用随机森林算法实现优质股票的选择 #### 一、引言 在当今金融市场中,投资者面临着众多的投资选择,其中股票投资因其潜在的高回报而备受关注。然而,如何从成千上万的股票中筛选出具有较好成长潜力的股票...
在当今的数字化时代,自然语言处理(NLP)技术已经成为人工智能领域的重要分支,广泛应用于智能助手、文本分析、机器翻译等场景。NLP算法工程师则是推动这一技术发展的核心力量,他们通过设计和优化算法来解决实际...
k-NN算法的核心思想是:在特征空间中,根据某一个距离度量,为待预测的新样本找到最近的k个邻居,然后根据这些邻居的类别进行投票或平均,以此来预测新样本的标签。 本文所讨论的“kNN_python.rar_datingTestSet_...
在当今的计算机视觉和图像处理领域,前景与背景的分类是关键任务之一,它在许多视觉应用中扮演着重要角色,比如物体识别、图像分割和视频分析等。前景提取指的是从图像中区分和提取出前景物体区域,而背景则是图像中...
本资料主要探讨的是“TraditionML”——对一系列经典传统机器学习算法的深入理解和应用实践,借助Jupyter Notebook这一强大工具,我们可以通过实例来更好地理解和掌握这些算法。 1. **线性回归** 线性回归是最基础...