当前位置:首页 > 技术学院 > 技术前线
[导读]算法虽然广泛应用在计算机领域,但却完全源自数学。实际上,最早的数学算法可追溯到公元前1600年-Babylonians有关求因式分解和平方根的算法。


什么是算法?

简而言之,任何定义明确的计算步骤都可称为算法,接受一个或一组值为输入,输出一个或一组值。(来源:homas H. Cormen, Chales E. Leiserson 《算法导论第3版》)

可以这样理解,算法是用来解决特定问题的一系列步骤(不仅计算机需要算法,我们在日常生活中也在使用算法)。算法必须具备如下3个重要特性:

有穷性,执行有限步骤后,算法必须中止。

确切性,算法的每个步骤都必须确切定义。

可行性,特定算法须可以在特定的时间内解决特定问题,

其实,算法虽然广泛应用在计算机领域,但却完全源自数学。实际上,最早的数学算法可追溯到公元前1600年-Babylonians有关求因式分解和平方根的算法。

汇总统治世界的 10 大算法

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

1 排序算法

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


汇总统治世界的 10 大算法

稳定的

冒泡排序(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——O(n^2.7)很漂亮但是很耗时

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

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

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

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

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

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

3 Dijkstra 算法

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

4 RSA算法变换

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

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

5 安全哈希算法

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

6 整数因式分解

这是在计算机领域被大量使用的数学算法,没有这个算法,信息加密会更不安全。该算法定义了一系列步骤,得到将一合数分解为更小因子的质数分解式。这被认为是一种FNP问题,它是NP分类问题的延伸,极其难以解决。

许多加密协议(如RSA算法)都基于这样一个原理:对大的合数作因式分解是非常困难的。如果一个算法能够快速地对任意整数进行因式分解,RSA的公钥加密体系就会失去其安全性。

量子计算的诞生使我们能够更容易地解决这类问题,同时它也打开了一个全新的领域,使得我们能够利用量子世界中的特性来保证系统安全。

7 链接分析

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

8 比例积分微分算法

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

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

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

9 数据压缩算法

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

10 随机数生成

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


本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

9月2日消息,不造车的华为或将催生出更大的独角兽公司,随着阿维塔和赛力斯的入局,华为引望愈发显得引人瞩目。

关键字: 阿维塔 塞力斯 华为

加利福尼亚州圣克拉拉县2024年8月30日 /美通社/ -- 数字化转型技术解决方案公司Trianz今天宣布,该公司与Amazon Web Services (AWS)签订了...

关键字: AWS AN BSP 数字化

伦敦2024年8月29日 /美通社/ -- 英国汽车技术公司SODA.Auto推出其旗舰产品SODA V,这是全球首款涵盖汽车工程师从创意到认证的所有需求的工具,可用于创建软件定义汽车。 SODA V工具的开发耗时1.5...

关键字: 汽车 人工智能 智能驱动 BSP

北京2024年8月28日 /美通社/ -- 越来越多用户希望企业业务能7×24不间断运行,同时企业却面临越来越多业务中断的风险,如企业系统复杂性的增加,频繁的功能更新和发布等。如何确保业务连续性,提升韧性,成...

关键字: 亚马逊 解密 控制平面 BSP

8月30日消息,据媒体报道,腾讯和网易近期正在缩减他们对日本游戏市场的投资。

关键字: 腾讯 编码器 CPU

8月28日消息,今天上午,2024中国国际大数据产业博览会开幕式在贵阳举行,华为董事、质量流程IT总裁陶景文发表了演讲。

关键字: 华为 12nm EDA 半导体

8月28日消息,在2024中国国际大数据产业博览会上,华为常务董事、华为云CEO张平安发表演讲称,数字世界的话语权最终是由生态的繁荣决定的。

关键字: 华为 12nm 手机 卫星通信

要点: 有效应对环境变化,经营业绩稳中有升 落实提质增效举措,毛利润率延续升势 战略布局成效显著,战新业务引领增长 以科技创新为引领,提升企业核心竞争力 坚持高质量发展策略,塑强核心竞争优势...

关键字: 通信 BSP 电信运营商 数字经济

北京2024年8月27日 /美通社/ -- 8月21日,由中央广播电视总台与中国电影电视技术学会联合牵头组建的NVI技术创新联盟在BIRTV2024超高清全产业链发展研讨会上宣布正式成立。 活动现场 NVI技术创新联...

关键字: VI 传输协议 音频 BSP

北京2024年8月27日 /美通社/ -- 在8月23日举办的2024年长三角生态绿色一体化发展示范区联合招商会上,软通动力信息技术(集团)股份有限公司(以下简称"软通动力")与长三角投资(上海)有限...

关键字: BSP 信息技术
关闭