十大有用算法

《十大有用算法》由会员分享，可在线阅读，更多相关《十大有用算法（10页珍藏版）》请在金锄头文库上搜索。

1、此时此刻，如果你已经学过算法的话，那么在你阅读那篇文章时，你脑海中所浮现 的第一件事也许是作者是否明白算法是什么？”或是“Facebook的新闻提要是 一种算法？”，因为如果Facebook的新闻提要也算是一种算法的话，那么最终你 可以把几乎所有的东西都归类为算法。因此，在本文中我会试着去解释什么是算法， 以及哪十个（也许更多）算法是真正统治世界的。什么是算法？直白地说，算法就是任何明确定义的计算过程，它接收一些值或集合作为输入，并 产生一些值或集合作为输出。这样，算法就是将输入转换为输出的一系列计算过程。来源 Thomas H. Cormen, Chales E. Leiserson （20

2、09）算法导论第三版 *简而言之，我们可以说算法就是用来解决一个特定任务的一系列步骤（是的，不止 计算机在使用算法，人类也同样如此）。目前，一个有效的算法应该含有三个重要 特性：1. 它必须是有限的:如果你设计的算法永无休止地尝试解决问题，那么它是无用的。2. 它必须具备明确定义的指令：算法的每一步都必须准确定义，在任何场景下指令 都应当没有歧义。3. 它必须是有效的：一个算法被设计用以解决某个问题，那么它就应当能解决这个 问题，并且仅仅使用纸和笔就能证明该算法是收敛的。还有一个要点需要指出，算法不仅仅在计算机科学中使用，同时也存在于数学领域 中。事实上，首个被记载的数学算法要追溯到公元前16

3、00年，古巴比伦人开发了 已知最早的算法，用作因式分解和计算平方根。这里，我们回答了前面所提到的那 篇文章中的第一个问题，它认为算法是计算机范畴的实体，但如果你知晓算法这个 词的真正内涵的话，真正统治世界的十大算法也能在数学书籍中找到（加法、减法、 乘积等等）。不过在这篇文章中，上我们将算法的定义限定在计算机算法上所以剩下的问题是： 哪十个算法统治了世界？在此我整理了一个小型列表，排名不分先后。1归并排序，快速排序和堆排序NameBestAverageWors-tMemoryStableBubble sortnn21Y&sSelection sort护1NoInsertion sortnn21

4、YesMerge sortn log nlog nn log nworst case s nYesIn-place merge sortn (log ?i21Y&sQuicksortn log nlog nn2log 11 on average, worst case isntypical inplace sort is not stable;Heapsortn log n71 log 77n. log n1No哪个排序算法最好？这取决于你的需求，这也是为什么我要将这三个使用频率较高的排序算法置于一处的原因。可能你比较偏爱其中一个，但它们都是同等重要的。归并排序算法是目前为止我们拥有的最重要的

5、算法之一。它是一种基于比较的排序 算法，使用分治法解决那些原本复杂度为0（N2）的问题。归并排序是由数学家Jo hn von Neumann 于 1945 年发明的。快速排序是解决排序问题的另一种途径，它使用就地分解算法，同时它也是一种分 治算法。这个算法的问题在于它是不稳定的排序算法，但它在基于内存的数组排序 上确实非常高效。最后，堆排序算法使用一个优先队列降低数据的查找时间，它也是一种就地排序算 法，同样也是不稳定的排序算法。相较于曾经使用的其他排序算法（如冒泡排序），上述算法带来了显著的改进。事 实上，多亏了它们，今天我们才有了数据挖掘、人工智能、链接分析，以及世界上 大部分的计算机工具

6、，也包括网络在内。（推荐阅读：视觉直观感受7种常用的排序算法）2.傅立叶变换与快速傅立叶变换他时工 亦dobnlA出 也火 廿応加占iGArtSfecM巴c*.Q QM 少31AA整个数字世界都在使用这些简单而又强大的算法，将信号从频域转换为时域，反之 亦然。事实上，正是归功于这些算法，你才能看到这篇文章。互联网、你的WIFI、智能手机、电话、计算机、路由器、卫星，几乎所有内置计算 机的东西都会以各种方式使用这些算法实现各自的功能。如果你没有学习这些重要 的算法，你将无法获得电子、计算机或通信方面的学位。编注：关于傅里叶变换，可以看看韩昊写的这篇文章通俗讲解傅里叶变换【完整 版】3Dijkst

7、ra算法(f)毫无不夸张地说，如果没有这个算法，当今互联网将无法有效工作。这是一种图搜 索算法，它被广泛应用在能够建模为图的问题中，用以找出两个节点之间的最短路 径。目前，即便我们已经拥有了解决最短路径问题的更好方法，Dijkstra算法依然在那 些重视稳定性的系统中得到应用。4. RSA算法如果没有信息加密和网络安全，互联网不会像现在那么重要。你可以认为安全问 题理所当然应该是美国国家安全局和其他情报机构的事情”或“你认为你身处在互 联网是安全的，这太天真了”。但是，人们需要在他们花钱时保有安全感，毕竟你 不会在网络服务器上输入你的信用卡号，如果你知道它是不安全的话。 在信息加密领域，有一个

8、算法始终是世界上最重要的算法之一，它就是RSA算法。这个算法是由RSA公司的创始人所建立的，它使信息加密惠及千家万户/奠定了当 今信息加密的运作基础。RSA算法用来解决一个简单而又复杂的问题：怎样在不同 平台和终端用户之间共享公钥，继而实现信息加密（我想说明一下这个问题还没完 全解决，我想我们需要基于这个方向做更多工作）。5.安全哈希算法准确地说，它不能称之为是算法，它是美国国家标准暨技术学会定义的加密散列函 数族中的一员，但是这族算法对整个世界的运作至关重要。从你的应用商店，你的 邮件，你的杀毒软件，到你的浏览器等等，所有这些都在使用安全哈希算法，它能 判断你是否下载了你想要的东西，也能判断

9、你是否是中间人攻击或网络钓鱼攻击的 受害者。（推荐阅读：加盐密码哈希：如何正确使用）这是在计算机领域被大量使用的数学算法，没有这个算法，信息加密会更不安全。 该算法定义了一系列步骤，得到将一合数分解为更小因子的质数分解式。这被认为 是一种FNP问题，它是NP分类问题的延伸，极其难以解决。许多加密协议（如RSA算法）都基于这样一个原理：对大的合数作因式分解是非常困难的。如果一个算法能够快速地对任意整数进行因式分解，RSA的公钥加密体系 就会失去其安全性。量子计算的诞生使我们能够更容易地解决这类问题，同时它也打开了一个全新的领 域，使得我们能够利用量子世界中的特性来保证系统安全。7. 链接分析tw

10、s title wukqroup.DoiriQjtlklLM畑 DOEKwatan.corrrronti q rpcKtconn.pkrecQeri.tvakabservErnt?!habrain.carnIT=eocrtesconnng.cumk WfSrHiaimdupuinliJtmIcnilykiiwi3h.c0FinjjT nn an. Ecnri-iJF- ji| I- .-ntr5,nFimmHl nim.pkpp.CEhm.pkTitv oinrkpkT臨tiwm呗F叭*2 .Ji* akistenlinkcomnkiribucuniindu ct a n.coiiri.EGm

11、xpress cum pkuns ifd ruly.Lihm_rrJgr 7 TX T -q-J J I YX-书也（J 审氐com*?n tU il fib mnnilapAaniwikipQdia. orgQQ _j-Hindus QidaytinfleecomQunE血m 诋r- voagoTwQshinqt 訂“pnMts 们在互联网时代，分析不同实体间的关系是相当重要的。从搜索引擎，社交网络，到 营销分析工具，每个人都在不停寻找互联网的真正结构。有证据显示，链接分析是公众心目中伴随着最多谬见和误解的算法之一。这里的问 题在于，有很多不同的方式可以进行链接分析，也存在很多特性使这些算法

12、看起来 有细微的区别（这些区别允许该算法独立申请专利），但它们本质上是类似的。链接分析背后的理念非常简单，以矩阵形式描绘出一张图，将问题转换为特征值问 题。特征值是一种很好的渠道，它有助于展现图的结构以及每个节点的相对重要性。 该算法是由Gabriel Pin ski和Fran cis Narin于1976年建立的。谁在使用这个算法？ Google的Page Rank算法，Facebook向你展示的新闻提要 （这就是为什么Facebook的新闻提要不是算法，只是使用算法的结果而已），G oogle+和Facebook的好友推荐，Linkedln的工作和联系人推荐，Netflix和Hui u的电

13、影，YouTuBe的视频，等等。虽然每个都有不同的目标和参数，但它们背后 的数学理念是相同的。最后，我想说明一点，尽管看上去Google是第一家使用这类算法的公司，然而在 1996年（Google之前两年），Robin Li （李彦宏）所建立的一个小型搜索引擎R ankDex”就已经在它的网页排名机制中使用了这项理念。后来，HyperSearch的 创始人Massimo Marchiori基于各网页之间的关系使用了另一种网页排名算法。（Google在它的专利中提到了这两位创始者）8. 比例积分微分算法uPlant /ProcessG(t)K?e(t) |ir ro/l/怙 be.现在我们还没有一个“真正的”随机数生成器，但我们已经有了一些伪随机数生成 器，这够用了。随机数生成器的用途非常广泛，从互联联络、数据加密、安全哈希 算法、电子游戏、人工智能、优化分析，到问题的初始条件、金融等等，都有它们 的身影。