改变计算技术的 9 个伟大算法

翻译:programmer_lin 摘自:伯乐在线 微信ID: jobbole 如需转载,务必联系“伯乐在线”

在过去,很多巧妙的计算机算法设计,改变了我们的计算技术。通过操作标准计算机中提供的中间运算符,可以产生很多的高效函数。这些函数导致了计算机程序的复杂性和多样性,这也是今天计算机时代快速发展的重要原因。如下所示,我们列举了一些算法,它们改变了我们的计算机使用。

压缩技术

哈弗曼编码

哈弗曼编码在无损数据压缩中广泛应用。为了找到一种最高效的二进制编码,哈弗曼在1951年提出了根据字符频率排序的二叉树这样的编码方法。这种方法被证明,是最有效的编码方法。由于这种方法简单、高效,这种方法被用在很多的压缩方法中比如:DEFLATE(PKZIP压缩软件中的算法),以及很多的多媒体编码包括JPEG和MP3中。

密码学

公共秘钥加密

对于加密算法而言,需要两种不同的秘钥,公共秘钥是用来作为加密的明文或者验证数字签名。私钥则用来解密密文,或生成数字签名。公共秘钥加密使得用户可以在公共信道中安全传送数据。虽然这种方法于1997年发表,但是由英国政府通讯总部(GCHQ)的James H. Ellis, Clifford Cocks, Malcolm Williamson在1973年设计完成,并且投入使用。

搜索算法

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实现的版本。

原文链接:http://blog.jobbole.com/61815/

原文发布于微信公众号 - 大数据文摘(BigDataDigest)

原文发表时间:2015-03-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏逍遥剑客的游戏开发

Puyo-Puyo设计文档

2095
来自专栏计算机视觉战队

利用深度学习消去反光

越来越接近毕业季了,相信很多同学都结束了论文的撰写以及论文审批,现在就坐等着毕业论文答辩和毕业典礼了!其实我也是这样的一个状态,但是期间大Boss还是会安排很多...

1341
来自专栏程序生活

贪心算法总结贪心算法基本思路算法实现实例分析参考

贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。...

1.8K4
来自专栏小樱的经验随笔

ACM训练计划

看完人家的博客,发现任重道远。。。 一位高手对我的建议: 一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的,主要时间...

46410
来自专栏开发 & 算法杂谈

动态数据竞争检测方法实验分析(一)

之前的文章大致介绍了一下我们的动态数据竞争检测平台如何构建,这篇文章主要是在动态数据竞争检测平台上实现了之前介绍的数据竞争检测方法,我们扩展了其中的一些方法使得...

2172
来自专栏奇点大数据

遗传算法(2)

在遗传算法中我们再举一个求极大值的例子。这种例子也是比较多见的,只要我们把一些数据关系描述成函数之后就会有一些求极大值或者极小值的问题。 其实极大值和极小值是一...

33312
来自专栏iOSDevLog

google 机器学习速成课程字幕和视频

1.5K7
来自专栏人工智能LeadAI

你听过算法也是可以贪心的吗?

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法...

3847
来自专栏余林丰

初学数据挖掘——相似性度量(二)

  上一篇中介绍了四个算法,并用四个算法分别计算了两个人的相似度。这篇就来讲讲相似性算法在实际当中怎么用。第一:将指定的人与其他人作相似性比较,并从高到低进行排...

2296
来自专栏天天P图攻城狮

Android上实现频域均衡器

本篇文章主要介绍了将录音从时域数据转化成频域数据的方法。

3982

扫码关注云+社区