改变计算机世界的“9”大算法 | 【伟大成就卓越】
本帖最后由 不二如是 于 2017-10-29 08:38 编辑前言：
在过去，很多巧妙的计算机算法设计，改变了我们的计算技术。
通过操作标准计算机中提供的中间运算符，诞生了很多的高效函数。这些函数导致了计算机程序的复杂性和多样性，这也是今天计算机时代快速发展的重要原因。
接下来按照目录中列出的6大主题，分别介绍9个改变世界的核心算法！
哈夫曼编码
哈弗曼编码在无损数据压缩中广泛应用。
为了找到一种最高效的二进制编码，哈弗曼在1951年提出了根据字符频率排序的二叉树这样的编码方法。
这种方法被证明，是最有效的编码方法。
由于这种方法简单、高效，这种方法被用在很多的压缩方法中比如：
DEFLATE（PKZIP压缩软件中的算法），以及很多的多媒体编码包括JPEG和MP3中。
TIPS：点击上方“目录”即可跳转到其他章节{:10_336:}
公共秘钥加密
对于加密算法而言，需要两种不同的秘钥：公共秘钥，私有秘钥
公共秘钥是用来作为加密的明文或者验证数字签名。
私钥则用来解密密文，或生成数字签名。
公共秘钥加密使得用户可以在公共信道中安全传送数据。
Dijkstra 最短路径算法
上图展示了在单向图中，利用这样的算法求最短路径的过程。
这一算法由Dijkstra在1956年完成，这是一个为图设计的搜索算法。
它解决了单向图中的最短路径问题，因此，也可以用来生成最短路径树。
很多基于图的算法中，都应用了这样的算法来进行路径规划或是子路径选择。
二分搜索算法
二分搜索算法用来在已经有序的数组中找到关键字的位置。
在说明词义的字典中，词的排列基本是有序的。
电话本上，记录也都按照人名、地址或是电话号码排序。
通过这样的算法，我们可以由人名，很快地在电话本中找到相应的电话以及地址。
快速排序
这种算法由Tony Hoare在1960年设计。
这个算法本来用于调整待翻译单词的顺序，从而使它们与词典顺序更加一致，方便翻译。
这种算法由于在Unix系统中被用作默认排序算法而声名大噪。
同时，这种算法由于它在C语言标准库中的函数名“qsort”而得名。
Karatsuba快速相乘算法
这种算法用来更快完成相乘的数学操作。
由Anatolii Alexeevitch Karatsuba在1962年提出。
它减少了乘法中需要操作的数字，并且提供了一个快速的相乘计算方法。
这种算法的改进算法是Toom–Cook算法。
然而，对于大数相乘，Schönhage–Strassen 算法则是一种更快速的解决方案。
欧几里得算法（辗转相除）
利用欧几里得算法，可以计算最大公约数。
即两个正整数可以被整除的最大数。虽然这种算法只通过减法和比较来找到最大公约数，但是它被应用在了许多高级算法中。
欧几里得被认为是这个算法的发明者。
欧几里得的这个算法被认为是欧几里得时期（公元前300年左右）最古老的算法之一。
Bresenham直线算法
这种算法由Jack Elton Bresenham在1962年，他在IBM工作期间提出。
这种算法本来用于在计算机屏幕上画出直线。
算法用到的操作非常简单，整数的加法，减法和移位操作。
这在计算机图形学中是非常先进的方法。
基于这样的方法，后来算法又有了一系列的拓展。
比如：
画圆算法等。
由于这种算法的高效、快捷，至今在很多硬件中（比如绘图仪和现代图形卡等）这种算法仍然十分重要并且仍在使用。
平方根倒数速算法
这种算法提供了一种快速计算平方根的倒数的方法。
这种方法在3D图像中广泛应用于确定光线和投影关系，这可能需要每秒上千万次的计算速度。
在《雷神之锤三：竞技场》的源代码中就有这样的算法。
可是，直到2002年这种算法才被广泛应用。
这个算法使用了一系列的简单操作来解决复杂问题。
虽然很多人认为，这种算法由John Carmack研发，但是，SGI和3dfx早就曾在产品中应用此算法，当时应用的是Gary Tarolli实现的版本。
如果喜欢，别忘了评分{:10_281:} ：
http://xxx.fishc.com/forum/201709/19/094516hku92k2g4kefz8ms.gif
页:
[1]