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

标签: jianshu | 发表时间:2020-02-27 00:00 | 作者:
出处:http://itindex.net/relian

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

压缩技术

哈弗曼编码

image

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

密码学

公共秘钥加密

image

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

搜索算法

Dijkstra 最短路径算法

image

这一算法由Dijkstra在1956年完成,这是一个为图设计的搜索算法。它解决了单向图中的最短路径问题,因此,也可以用来生成最短路径树。很多基于图的算法中,都应用了这样的算法来进行路径规划或是子路径选择。上图展示了在单向图中,利用这样的算法求最短路径的过程。

二分搜索算法

image

二分搜索算法用来在已经有序的数组中找到关键字的位置。在说明词义的字典中,词的排列基本是有序的。电话本上,记录也都按照人名、地址或是电话号码排序。通过这样的算法,我们可以由人名,很快地在电话本中找到相应的电话以及地址。

排序算法

快速排序

image

这种算法由Tony Hoare在1960年设计。这个算法本来用于调整待翻译单词的顺序,从而使它们与词典顺序更加一致,方便翻译。这种算法由于在Unix系统中被用作默认排序算法而声名大噪。同时,这种算法由于它在C语言标准库中的函数名“qsort”而得名。

数学方法

Karatsuba快速相乘算法

image

这种算法用来更快完成相乘的数学操作。由Anatolii Alexeevitch Karatsuba在1962年提出。它减少了乘法中需要操作的数字,并且提供了一个快速的相乘计算方法。这种算法的改进算法是Toom–Cook算法。然而,对于大数相乘,Schönhage–Strassen 算法则是一种更快速的解决方案。

欧几里得算法(辗转相除)

image

利用欧几里得算法,可以计算最大公约数。即两个正整数可以被整除的最大数。虽然这种算法只通过减法和比较来找到最大公约数,但是它被应用在了许多高级算法中。欧几里得被认为是这个算法的发明者,欧几里得的这个算法被认为是欧几里得时期(公元前300年左右)最古老的算法之一。

图形学的发展

Bresenham直线算法

这种算法由Jack Elton Bresenham在1962年,他在IBM工作期间提出。这种算法本来用于在计算机屏幕上画出直线。算法用到的操作非常简单,整数的加法,减法和移位操作。这在计算机图形学中是非常先进的方法。基于这样的方法,后来算法又有了一系列的拓展,比如:画圆算法等。由于这种算法的高效、快捷,至今在很多硬件中(比如绘图仪和现代图形卡等)这种算法仍然十分重要并且仍在使用。

平方根倒数速算法

这种算法提供了一种快速计算平方根的倒数的方法。这种方法在3D图像中广泛应用于确定光线和投影关系,这可能需要每秒上千万次的计算速度。在《雷神之锤三:竞技场》的源代码中就有这样的算法,可是,直到2002年这种算法才被广泛应用。这个算法使用了一系列的简单操作来解决复杂问题。虽然很多人认为,这种算法由John Carmack研发,但是,SGI和3dfx早就曾在产品中应用此算法,当时应用的是Gary Tarolli实现的版本。

相关 [改变 计算 技术] 推荐:

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

- - IT瘾-jianshu
在过去,很多巧妙的计算机算法设计,改变了我们的计算技术. 通过操作标准计算机中提供的中间运算符,可以产生很多的高效函数. 这些函数导致了计算机程序的复杂性和多样性,这也是今天计算机时代快速发展的重要原因. 如下所示,我们列举了一些算法,它们改变了我们的计算机使用. 哈弗曼编码在无损数据压缩中广泛应用.

地理位置技术将如何将改变服务业

- 彭全兵 - 互联网的那点事...
据国外媒体报道, 现场服务管理应用套件ServiceMax的首席执行官戴夫·约诺德(Dave Yarnold)今天发表署名文章,讨论地理位置技术在服务业中的应用,以下为全文摘要:. 面向消费者的地理位置服务如雨后春笋般冒出来,它们无处不在,比如Uber,它可以派一辆轿车到你的门口,速度比出租车快一倍,又比如应用程序Bizzy,它显示你的朋友们最近在哪里吃饭,并为你提供朋友们的推荐.

花旗:预测彻底改变世界的十大技术

- - 互联网的那点事
花旗分析师在一份研究报告中列出了10项可能彻底改变世界的技术. 这10项技术覆盖能源、娱乐、IT、制造、运输等领域. 部分技术已经存在一段时间,但将变得更好、成本会进一步降低;部分技术才刚刚问世,未来数年将会普及. 由于成本日趋下降,更易用的软件,更复杂的设计能力,3D打印技术将呈爆炸性增长态势. 未来,50%的喷气发动机零部件将由3D打印机完成制造.

十项将彻底改变你生活的新技术

- - 互联网的那点事
十项将彻底改变你生活的新技术. 技术的进步让你的生活与众不同. 保持对个人电脑和信息技术发展的全面了解对于一般人来说几乎是不可能的,但是下面介绍的十项技术你最应该了解,因为这些技术将最大限度的改变你的生活. 事实上带上一副特制的太阳镜就能从二维屏幕上看到各种各样的三维图像,更糟糕的是所谓的三维游戏并不如多点触摸以及自然用户界面的游戏更具说服力,尽管两者几乎是在同一时间商品化的.

“位置跟踪”技术将改变购物模式

- - 互联网的那点事
你在杂货店里找不到自己需要的商品. 一些零售商想帮助你,但这可能意味着你在商店过道转悠时,商家跟踪你的一举一动. 在结合位置数据、市场营销和数据分析的这个新兴领域,零售商们正在尝试新的方法,了解顾客如何逛店购物,然后借助促销活动和顾客智能手机上的店内地图,牢牢锁定顾客. 这个概念有时又叫基于位置的营销(place-based marketing),利用详细的位置信息——常常具体到你走过的那只货架,以期带动销售额,并且为零售商提供关于店内客流量的更多信息.

技术分析:苹果之后 HTML5将改变移动互联网

- Lamo - 互联网的那点事
乔布斯离开了,创新和变革的脚步却不会因为乔帮主的离开而停下,下一个给移动互联网世界带来重大变革的可能就是HTML5. 众所周知,苹果一直站在与Flash做斗争的最前沿,杜绝Flash出现在iPhone和iPad上,声称Flash技术太过陈旧,影响设备的应用体验. 之后,苹果找到了可以替代Flash的革命性技术——HTML5,并且种种迹象表明苹果将大力推广HTML5.

Google Wallet测试(图片、视频):改变未来的移动支付技术

- David - cnBeta.COM
编者注:以下是TC作者 Greg Kumparak对刚刚发布的Google Wallet的一个试用报告. 虽然Google Wallet刚刚发布,但Greg Kumparak已经试用了好几周的Google Wallet,并称Google Wallet是一项改变未来的移动支付技术. 以下则是他对Google Wallet的亲身测试体验.

麦肯锡:12项可能改变世界的破坏性技术

- - cnBeta.COM
麦肯锡全球研究所(McKinsey Global Institute)发布研究报告,公布未来12项可能改变生活、企业与全球经济的破坏性科技(disruptive technologies),这些技术有望在2025年带来14万亿至33万亿美元的经济效益. 研究报告从100种技术中挑选出12项经济效益最高的技术,然后分析这些技术可能的应用方式,以及可创造的价值,并以经济效益排名.

【CDC翻客】10项即将到来并可能改变世界的技术

- - 腾讯CDC
  译者注: 随着Google Glass袭来,我们看到更多先进的技术即将带来生活和工作的巨大变革. 本文精选了10个即将改变世界的科技产品,部分来自于国外最大的众酬平台Kickstarter,也有源于世界知名公司的产品. 相信未来的生活都会因它们而不同. 原文请见: 10 Upcoming Technology That May Change The World.

IBM CEO称,这三项技术趋势会改变未来商业

- - 虎嗅网
本文节选自 Forbes.com,由新浪科技翻译:. IBM CEO罗睿兰(Ginni Rometty)本周在非营利组织外交关系协会举办的一次活动上表示,云计算、移动互联网、社交网络和大数据正快速发展,这样的技术进展将改变企业运营的方方面面. 罗睿兰预计,数据将是未来竞争优势的基础,将会是“下一项重要的自然资源”.