个人意见:这十个演算法,才是真的改变世界的重量级演算法

 

那天,我正在浏览 Reddit 的时候,我看到了一篇叫做「10 个改变世界的演算法」的文章。作者 George Dvorsky 试图透过文章表达演算法的在这个世界上极大的贡献,以及介绍那些对我们人类的文明有着最大的影响的演算法。

但是如过你有对演算法略有涉略,你可能会边读边想「这个作者真的知道演算法是什幺吗?」或是「脸书的动态时报也算是一个演算法?」, 因为如果连那个都算是一种演算法的话,那几乎所有东西都可以被归类于演算法下面。因此,我在这篇文章中将会介绍演算法到底是什幺以及 10 个真正改变世界的演算法。

什幺是演算法?

简单的说,演算法是一种将一些「输入值」经过一些运算后产生出「输出值」的运算方法。所以演算法其实是将输入值传变成输出值的过程。

其实,我们可以说演算法就只是完成某项任务的步骤(并不是只有电脑在使用演算,人们也在用)。一个有效的演算法有三个必要的条件:

但是很重要的是,演算法并不是仅仅用于电脑科学上,他在数学上也有极大的用处。事实上,人类史上第一个有 纪载的数学演算法是西元前 1600 年前巴比伦人用来计算平方根的 。所以 George Dvorsky 在他那篇文章的问题其实是他把演算法侷限在电脑上的应用,而当你把用演算法真正的定义的话,你会在有关数学的书里找到十个影响最大的演算法(加减乘除之类的)。

但是即便我们只考虑在电脑上应用的演算法,问题仍然存在:到底是哪十个演算法对世界最有影响?我在下面整理了十个改变世界的演算法,但是他们的顺序并不代表影响力的大小。

合併排序法、快速排序法 还有堆积排序法

哪一个最好的排序的演算法呢?其实这三个演算法的优劣完全看你的需要,所以在这里我才把三种方法都列出来。你个人可能有偏好其中一种,但是这三个演算法都同样的重要。

由数学家 John von Neumann 在 1945 年所发明的 合併排序法(Merge Sort)是截至目前为止最重要的演算法之一,因为透过将一个大的问题分解成极多的小的问题,他把一个需要大 n 平方时间的任务变成了 nlog(n) 。

虽然同样都是将一个大问题化成许多小问题, 快速排序法(Quick Sort)不同于 Merge Sort 的是, 他是不断的透过支点将资料排序。虽然 Quick Sort 并不是一个稳定的排序演算法,但是他是一个处理 RAM(随机处理记忆体)极有效率的演算法。

最后, 堆积排序法(Heap Sort)是使用优先序列来降低搜寻资料的时间。这个演算法跟 Quick Sort 一样都不稳定并且也都是 in-place 演算法。

这些演算法大大的改进了先前的 气泡排序法 ,并且因为有这些演算法,我们现在才可以有像是 Data mining, 人工智慧,连结分析,以及网路等电脑上的应用。

傅立叶变换 以及快速傅立叶变换

我们所有跟数位传输有关的东西都是透过 傅立叶变换(Fourier Transform)。他将讯号的时间领域转变为频率,反之亦然。

网路、无线网路、智慧型手机、一般电话、电脑、路由器、卫星和几乎任何跟电脑有关的东西都在某种程度上使用到他。

事实上是,你们要看到这篇文章也是有赖于这个演算法。如果你想要研究电子产品,电脑或是通讯传播的话,你一定会要学到这个无比重要的演算法。

戴克斯特拉演算法

个人意见:这十个演算法,才是真的改变世界的重量级演算法

(图片来源:wikipedia;由 Goran tek-en 上传)

「要是没有这个演算法,我们的网路便不会运作得如此迅速」,这句话套用在 Dijkstra 演算法 上并不为过。这个在图像搜寻的演算法的运用十分广泛,包括找寻两点之间的最短路径。

即便今天我们有更好的演算法可以找出两点间的最短路径, 在需要稳定性的系统哩,我们仍然在继续地在使用 Dijkstra 演算法。

RSA 加密演算法

如果没有网路安全和密码学,现在的网路便不会如此的重要。你可能会觉得网路安全是 NSA 或是其他情报机关的事,跟你自己毫不相干,或是,只有那些天真的人才会觉得网路上的资料是安全的。

但是,人们要感到自己的资料在网路上是安全的才会在网路上消费,没有我们前面说的资安保护,人们便不会在网路上输入自己的信用卡卡号来网购。

此外,从密码学的角度来说,由 RSA 公司开发出的 RSA 演算法 是史上最重要的演算法之一。这个演算法不但让每个人都可以使用密码学,更改变了现在人们使用密码学的习惯。RSA 演算法解决了一个一个既简单又複杂的问题:要怎样在各自独立的平台和终端使用者之间分享资讯,同时透过锁码让资讯不外流?(我个人认为这个问题并还没有被解决,需要更多的心血花在解决这个问题上。)

安全杂凑演算法(Secure Hash Algorithm)

与其说这是一个单独的演算法,这比较像许多由美国的 NIST 所开发出的锁码的方法。

这些演算法 是许多像是应用程式商店、电子邮件、防毒软体、浏览器的基石,因为他们都是透过这些演算法(事实上是那些锁码的方法)来确认你下载的东西是你要的而不是某个恶意程式,让你免时遭受钓鱼攻击。

整数分解(Integer Factorization)

这项演算法应用十分广泛,若缺少了这项演算法,加密技术的安全性将大大降低。这项演算法主要是一连串用于用于进行质因数分解的程序。由于这通常被视为 FNP 问题,属于 NP 等级的延伸,从而大大增加了问题的难度。

许多加密方法的基础都建立在质因数分解或 RSA 问题等相关问题之上。一个可以有效分析出随机因数的演算法,将严重危及以 RDA 为基础的加密法。量子演算的发明,大大降低了解决这项问题的难度,开启了一个全新以量子性质作为加密基础的方式。

  • 链结分析(Link Analysis)

    个人意见:这十个演算法,才是真的改变世界的重量级演算法

    (图片来源:Marc_Smith,CC Licensed)

    在网路时代,不同使用者间连结的的分析十分重要。

    搜寻引擎、社群网站到行销分析等机构,都正试图找出网路的的结构。对一般大众而言,连结分析可说是扑朔迷离且令人费解的。不过,儘管每种连结分析的演算法都有些许不同,但其实大多都建立在相同的基础之上。

    连结分析的基本想法非常简单,透过将表格化为方阵的方式,即可将问题简化为特徵值(eigenvalue)的计算。而特徵值将反映资料的结构与每一项组成元素之间的关係。这项演算方式是由Gabriel Pinski and Francis Narin 在 1976 年所发展的。

    这项演算法已经被普遍的运用在一般的日常生活中,如 Google 的 Paper Rank、Facebook 的 news feed、Google+ 与 Facebook 的可能好友、LinkedIn 的工作推荐、Netflix、Hulu、Youtube 的、影片推荐等。

    最后,虽然 Google 看起来好像是第一家将连结分析投入市场应用的公司,但其实在 1996 年(Google 成立的两年前),一家由 Robin Li 所创立名为 RankDex 的搜寻引擎早已将连结分析用于搜寻结果的优先排序上了。另外,HyperSearch 的创办人 Massimo Marchiori 也早已将连结分析应用于网页关联的分析上了。

    比例积分微分演算法(Proportional Integral Derivative Algorithm)

    个人意见:这十个演算法,才是真的改变世界的重量级演算法

     

    (图片来源:wikipedia;由 TravTigerEE 上传)

    任何使用过飞机、汽车、卫星服务、手机网路或参观过工厂製造过程的人,都已经亲眼见过这项演算法的威力了。

    基本上,这项演算法利用迴圈反馈机制,将理想结果与实际结果间的误差最小化。这项演算法已经被广泛应用在所有电子控制系统之中。也就是说,如果没有这项演算法,一般人所知的现代文明将不可能存在。

    资料压缩演算法(Data compression algorithms)

    由于随着压缩标的不同,所需的演算法也略有不同,要决定哪一个演算法的重要性最高是件困难的挑战。但众所皆知的是,这些演算法的重要性不容置疑。

    除了 zip 文件以外,不论是从网页上、游戏中、云端所下载的任何形式资料,都需要经过压缩程序。可以说,透过压缩程序,整个网路传输的成本才能大大降低致人人可负担得起。(可参考 维基百科 。)

    随机乱数产生器(Random Number Generation)

    虽然到目前为止,完全随机的数字产生演算法尚未出现,一些接近随机的数字产生演算法已经十分有效了。这些演算法被用于许多应用,包含连结建立、加密技术、AI,甚至是游戏之中。

    这项排名只是我的个人见解,而非具有公信力的排名。

  • 上一篇: 下一篇: