统治世界的十大算法

一篇有趣的文章《统治世界的十大算法》中,作者George Dvorsky试图解释算法之于当今世界的重要性,以及哪些算法对人类文明最为重要。

1.排序算法

所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。

稳定的

冒泡排序(bubble sort O(n^2

鸡尾酒排序(Cocktail sort,双向的冒泡排序) O(n^2

插入排序(insertion sort)— O(n^2)

桶排序(bucket sort)— O(n); 需要 O(k) 额外空间

计数排序(counting sort) O(n+k); 需要 O(n+k) 额外空间

合并排序(merge sort)— O(nlog n);需要 O(n) 额外空间

原地合并排序— O(n^2)

二叉排序树排序 Binary tree sort O(nlog n)期望时间; O(n^2)最坏时间; 需要 O(n) 额外空间

鸽巢排序(Pigeonhole sort) O(n+k); 需要 O(k) 额外空间

基数排序(radix sort)— O(n·k); 需要 O(n) 额外空间

Gnome 排序— O(n^2)

图书馆排序— O(nlog n) withhigh probability,需要1+ε)n额外空间

不稳定的

选择排序(selection sort)— O(n^2)

希尔排序(shell sort)— O(nlog n) 如果使用最佳的现在版本

组合排序— O(nlog n)

堆排序(heapsort)— O(nlog n)

平滑排序— O(nlog n)

快速排序(quicksort)— O(nlog n) 期望时间,O(n^2) 最坏情况; 对于大的、乱数列表一般相信是最快的已知排序

Introsort—O(nlog n)

Patience sorting O(nlog n+k) 最坏情况时间,需要额外的 O(n+ k) 空间,也需要找到最长的递增子串行(longest increasing subsequence

不实用的

Bogo排序— O(n× n!) 期望时间,无穷的最坏情况。

Stupid sort O(n^3); 递归版本需要 O(n^2)额外存储器

珠排序(Bead sort O(n) or O(√n),但需要特别的硬件

Pancake sorting O(n),但需要特别的硬件

stooge sort——On^2.7)很漂亮但是很耗时

2.傅立叶变换与快速傅立叶变换

傅立叶是一位法国数学家和物理学家,原名是JeanBaptiste Joseph Fourier(1768-1830), Fourier1807年在法国科学学会上发表了一篇论文,论文里描述运用正弦曲线来描述温度分布,论文里有个在当时具有争议性的决断:任何连续周期信号都可以由一组适当的正弦曲线组合而成。

当时审查这个论文拉格朗日坚决反对此论文的发表,而后在近50年的时间里,拉格朗日坚持认为傅立叶的方法无法表示带有棱角的信号,如在方波中出现非连续变化斜率。直到拉格朗日死后15年这个论文才被发表出来。

谁是对的呢?拉格朗日是对的:正弦曲线无法组合成一个带有棱角的信号。但是,我们可以用正弦曲线来非常逼近地表示它,逼近到两种表示方法不存在能量差别,基于此,傅立叶是对的。

为什么我们要用正弦曲线来代替原来的曲线呢?如我们也还可以用方波或三角波来代替呀,分解信号的方法是无穷多的,但分解信号的目的是为了更加简单地处理原来的信号。

用正余弦来表示原信号会更加简单,因为正余弦拥有原信号所不具有的性质:正弦曲线保真度。一个正余弦曲线信号输入后,输出的仍是正余弦曲线,只有幅度和相位可能发生变化,但是频率和波的形状仍是一样的。且只有正余弦曲线才拥有这样的性质,正因如此我们才不用方波或三角波来表示。

3.Dijkstra 算法

Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

4. RSA算法

RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的绝大多数密码攻击,已被ISO推荐为公钥数据加密标准。

今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天,RSA加密安全性受到了挑战。

5.安全哈希算法

一种对输入信息(例如消息)进行摘要的算法。摘要过程能够完成下列特点:不同的输入信息绝对不会具有相同的指纹:相近输入信息经过摘要之后的输出信息具有较大的差异,同时计算上很难生产一个与给定输入具有相同指纹的输入。(即不可逆)。

7.链接分析

链接分析,源于对Web结构中超链接的多维分析。当前其应用主要体现在网络信息检索、网络计量学、数据挖掘、Web结构建模等方山。作为Google的核心技术之一,链接分析算法应用已经显现出j惊人的商业价值。

8.比例积分微分算法

你是否曾经用过飞机、汽车、卫星服务或手机网络?你是否曾经在工厂工作或是看见过机器人?如果回答是肯定的,那么你应该已经见识过这个算法了。

大体上,这个算法使用一种控制回路反馈机制,将期望输出信号和实际输出信号之间的错误最小化。无论何处,只要你需要进行信号处理,或者你需要一套电子系统,用来自动化控制机械、液压或热力系统,这个算法都会有用武之地。

可以这样说,如果没有这个算法,现代文明将不复存在。

9.数据压缩算法

在现今的电子信息技术领域,正发生着一场有长远影响的数字化革命。由于数字化的多媒体信息尤其是数字视频、音频信号的数据量特别庞大,如果不对其进行有效的压缩就难以得到实际的应用。因此,数据压缩技术已成为当今数字通信、广播、存储和多媒体娱乐中的一项关键的共性技术。

10.随机数生成

在统计学的不同技术中需要使用随机数,比如在从统计总体中抽取有代表性的样本的时候,或者在将实验动物分配到不同的试验组的过程中,或者在进行蒙特卡罗模拟法计算的时候等等。

本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院