28个不得不看经典编程算法!!数学软件计算机进来!~

《28个不得不看经典编程算法!!数学软件计算机进来!~》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、前十个是来自圣经的十大算法：发起人的描述：《来自圣经的证明》收集了数十个简洁而优雅的数学证明，迅速赢得了大批数学爱好者的追捧。如果还有一本《来自圣经的算法》，哪些算法会列入其中呢？第一名：Union-find严格地说，并查集是一种数据结构，它专门用来处理集合的合并操作和查询操作。并查集巧妙地借用了树结构，使得编程复杂度降低到了令人难以置信的地步；用上一些递归技巧后，各种操作几乎都能用两行代码搞定。而路径压缩的好主意，更是整个数据结构的画龙点睛之笔。并查集的效率极高，单次操作的时间复杂度几乎可以看作是常数级别；但由于数据结构的实际行为难以预测，精确的时间复杂度分析需要用到不少高深的技巧。第二

2、名：Knuth-Morris-Pratt字符串匹配算法   关于此算法的介绍，请参考此文：六、教你从头到尾彻底理解KMP算法。KMP算法曾经落选于二十世纪最伟大的十大算法，但人们显然不能接受，如此漂亮、高效的KMP算法竟然会落选。所以，此次最终投票产出生，KMP算法排到了第二名。第三名：BFPRT算法   1973年，Blum、Floyd、Pratt、Rivest、Tarjan集体出动，合写了一篇题为“Timeboundsforselection”的论文，给出了一种在数组中选出第k大元素的算法，俗称"中位数之中位数算法"。依靠一种精心设计的pivot选取方法，该算法从理论上保证了最坏情形下

3、的线性时间复杂度，打败了平均线性、最坏O(n^2)复杂度的传统算法。一群大牛把递归算法的复杂度分析玩弄于骨掌股掌之间，构造出了一个当之无愧的来自圣经的算法。    我在这里简单介绍下在数组中选出第k大元素的时间复杂度为O（N）的算法：   类似快排中的分割算法： 每次分割后都能返回枢纽点在数组中的位置s,然后比较s与k的大小若大的话，则再次递归划分array[s..n]，小的话，就递归array[left...s-1]//s为中间枢纽点元素。否则返回array[s]，就是partition中返回的值。//就是要找到这个s。 找到符合要求的s值后，再遍历输出比s小的那一边的元素。    各位

4、可参考在：算法导论上，第九章中，以期望线性时间做选择，一节中，我找到了这个寻找数组中第k小的元素的，平均时间复杂度为O（N）的证明：上述程序的期望运行时间，最后证明可得O(n)，且假定元素是不同的。第四名：Quicksort（快速排序）快速排序算法几乎涵盖了所有经典算法的所有榜单。它曾获选二十世纪最伟大的十大算法（参考这：细数二十世纪最伟大的10大算法）。关于快速排序算法的具体介绍，请参考我写的这篇文章：一之续、快速排序算法的深入分析，及十二、快速排序算法之所有版本的c/c++实现。第五名：Floyd-Warshallall-pairs最短路径算法关于此算法的介绍，可参考我写的此文：几个最

5、短路径算法比较（http://blog.csdn.net/v_JULY_v/archive/2011/02/12/6181485.aspx）。d[]:二维数组.d[i,j]最小花费、或最短路径的邻边。forkfrom1ton:forifrom1ton:forjfrom1ton:d[i,j]=min(d[i,j],d[i,k]+d[k,j])第六名：Gentry'sFullyHomomorphicEncryptionScheme（绅士完全同态加密机制）算法。此算法很漂亮，它允许第三方执行任意加密数据运算得不到私钥（不是很了解）。第七名：DepthFirstSearch、BreadthFirs

6、tSearch（深度、广度优先搜索）它们是许多其他算法的基础。关于深度、广度优先搜索算法的具体介绍，请参考此文：教你通透彻底理解：BFS和DFS优先搜索算法。第八名：Miller-Rabin作的类似的试验测试这个想法是利用素数的性质(如使用费马大定理)的小概率寻找见证不数素数。如果没有证据是足够的随机检验后发现,这一数字为素数。第九名：BinarySearch（二分查找）在一个有序的集合中查找元素，可以使用二分查找算法，也叫二分搜索。二分查找算法先比较位于集合中间位置的元素与键的大小，有三种情况（假设集合是从小到大排列的）：1.键小于中间位置的元素，则匹配元素必在左边（如果有的话），于是对

7、左边的区域应用二分搜索。2.键等于中间位置的元素，所以元素找到。3.键大于中间位置的元素，则匹配元素必在右边（如果有的话），于是对右边的区域应用二分搜索。另外，当集合为空，则代表找不到。第十名：Huffmancoding（霍夫曼编码）霍夫曼编码(HuffmanCoding)是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，DavidA.Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建