计算机算法改变了我们的计算机使用,你知道吗?

微信ID:jobbole

如需转载,请务必联系“伯乐在线”

过去,许多巧妙的计算机算法设计改变了我们的计算技术。通过操纵标准计算机中提供的中间算子,可以产生许多有效的功能。这些功能导致了计算机程序的复杂性和多样性,这也是当今计算机时代迅速发展的重要原因。如下图,我们列举了一些改变我们计算机使用的算法。

压缩技术

霍夫曼编码

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

密码学

公钥加密

对于加密算法,需要两个不同的密钥,公钥用于加密明文或验证数字签名。私钥用于解密密文或生成数字签名。公钥加密使用户能够通过公共渠道安全地传输数据。虽然这种方法是在 1997 年发表的,但它是由 GCHQ 的 James H. Ellis、Clifford Cocks 和 Malcolm Williamson 于 1973 年设计并投入使用的。

搜索算法

Dijkstra 的最短路径算法

该算法由 Dijkstra 于 1956 年完成,是一种为图设计的搜索算法。它解决了单向图中的最短路径问题,因此也可用于生成最短路径树。在许多基于图的算法中,此类算法用于路径规划或子路径选择。上图显示了在单向图中使用这种算法找到最短路径的过程。

二分搜索算法

二分搜索算法用于查找关键字在已排序数组中的位置。在描述词义的字典中,词的排列基本上是有序的。在电话簿中,记录也按姓名、地址或电话号码排序。通过这样的算法,我们可以通过人名在电话簿中快速找到对应的电话号码和地址。

排序算法

快速排序

这个算法是托尼·霍尔在 1960 年设计的。这个算法最初是用来调整要翻译的单词的顺序,使它们在字典上更加一致,更容易翻译。该算法因其在 Unix 系统中用作默认排序算法而声名狼藉。同时,该算法以其在C语言标准库中的函数名“qsort”命名。

数学方法

Karatsuba 快速乘法算法

该算法用于更快地执行乘法的数学运算。由 Anatolii Alexeevitch Karatsuba 于 1962 年提出。它减少了乘法中要操作的数字数量密码学算法 大数问题,并提供了一种快速的乘法计算方法。该算法的改进算法是Toom-Cook算法。然而,对于大数相乘,Schönhage-Strassen 算法是一种更快的解决方案。

欧几里得算法(除法)

使用欧几里得算法,可以计算最大公约数。即两个正整数可被整除的最大数。尽管该算法仅通过减法和比较来找到最大公约数,但它被用于许多高级算法中。Euclid 被认为是该算法的发明者,而 Euclid 的算法被认为是 Euclid 时代(约公元前 300 年)最古老的算法之一。

图形的发展

Bresenham 直线算法

该算法由 Jack Elton Bresenham 于 1962 年在 IBM 工作时提出。该算法最初用于在计算机屏幕上绘制直线。算法中使用的操作非常简单,整数加减法和移位操作。这是计算机图形学中非常先进的方法。基于这种方法,后来的算法又有了一系列的扩展,比如:画圆算法等等。由于该算法的效率和速度,它仍然非常重要,并且仍在许多硬件(例如绘图仪和现代显卡等)中使用。.

平方根倒数算法

该算法提供了一种计算平方根倒数的快速方法。该方法广泛用于 3D 图像中确定光线和投影关系,每秒可能需要数千万次计算。Quake III:Arena的源代码中有这样一个算法密码学算法 大数问题,但直到2002年才被广泛使用。这个算法使用一系列简单的操作来解决复杂的问题。虽然很多人认为这个算法是 John Carmack 开发的,但 SGI 和 3dfx 在他们的产品中使用这个算法很长时间了,使用的是当时由 Gary Tarolli 实现的版本。

© 版权声明
THE END
喜欢就支持一下吧
点赞0
分享
评论 抢沙发

请登录后发表评论