文档章节

主宰全球的10大算法

丈量大地
 丈量大地
发布于 2014/06/03 17:24
字数 2149
阅读 94
收藏 9

主宰全球的10大算法

【编者按】Reddit有篇帖子介绍了算法对我们现在生活的重要性,以及哪些算法对现代文明所做贡献最大。这个表单并不完整,很多与我们密切相关的算法都没有提到,如机器学习和矩阵乘法,欢迎你继续补充。

如果对算法有所了解,读这篇文章时你可能会问“作者知道算法为何物吗?”,或是“Facebook的‘信息流’(News Feed)算是一种算法吗?”,如果“信息流”是算法,那就可以把所有事物都归结为一种算法。才疏学浅,结合那篇帖子,接下来我试着解释一下算法是什么,又是哪些算法正在主导我们的世界。


什么是算法?

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

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

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

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

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

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

那么又是哪10个计算机算法造就了我们今天的生活呢?请看下面的表单,排名不分先后:

1. 归并排序(MERGE SORT)、快速排序(QUICK SORT)和堆积排序(HEAP SORT)


哪个排序算法效率最高?这要看情况。这也就是我把3种算法放在一起讲的原因,可能你更常用其中一种,不过它们各有千秋。

归并排序算法,是目前为止最重要的算法之一,是分治法的一个典型应用,由数学家John von Neumann于1945年发明。

快速排序算法,结合了集合划分算法和分治算法,不是很稳定,但在处理随机列阵(AM-based arrays)时效率相当高。

堆积排序,采用优先伫列机制,减少排序时的搜索时间,同样不是很稳定。

与早期的排序算法相比(如冒泡算法),这些算法将排序算法提上了一个大台阶。也多亏了这些算法,才有今天的数据发掘,人工智能,链接分析,以及大部分网页计算工具。

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

这两种算法简单,但却相当强大,整个数字世界都离不开它们,其功能是实现时间域函数与频率域函数之间的相互转化。能看到这篇文章,也是托这些算法的福。

因特网,WIFI,智能机,座机,电脑,路由器,卫星等几乎所有与计算机相关的设备都或多或少与它们有关。不会这两种算法,你根本不可能拿到电子,计算机或者通信工程学位。(USA)

3.  迪杰斯特拉算法 (Dijkstra’s algorithm)

可以这样说,如果没有这种算法,因特网肯定没有现在的高效率。只要能以“图”模型表示的问题,都能用这个算法找到“图”中两个节点间的最短距离。

虽然如今有很多更好的方法来解决最短路径问题,但代克思托演算法的稳定性仍无法取代。

4. RSA非对称加密算法


毫不夸张地说,如果没有这个算法对密钥学和网络安全的贡献,如今因特网的地位可能就不会如此之高。现在的网络毫无安全感,但遇到钱相关的问题时我们必需要保证有足够的安全感,如果你觉得网络不安全,肯定不会傻乎乎地在网页上输入自己的银行卡信息。

RSA算法,密钥学领域最牛叉的算法之一,由RSA公司的三位创始人提出,奠定了当今的密钥研究领域。用这个算法解决的问题简单又复杂:保证安全的情况下,如何在独立平台和用户之间分享密钥。

5. 哈希安全算法(Secure Hash Algorithm)

确切地说,这不是一种算法,而是一组加密哈希函数,由美国国家标准技术研究所首先提出。无论是你的应用商店,电子邮件和杀毒软件,还是浏览器等等,都使用这种算法来保证你正常下载,以及是否被“中间人攻击”,或者“网络钓鱼”。

6. 整数质因子分解算法(Integer factorization)

这其实是一个数学算法,不过已经广泛应用与计算机领域。如果没有这个算法,加密信息也不会如此安全。通过一系列步骤将,它可以将一个合成数分解成不可再分的数因子。

很多加密协议都采用了这个算法,就比如刚提到的RSA算法。

7. 链接分析算法(Link Analysis)


在因特网时代,不同入口间关系的分析至关重要。从搜索引擎和社交网站,到市场分析工具,都在不遗余力地寻找因特网的正真构造。

链接分析算法一直是这个领域最让人费解的算法之一,实现方式不一,而且其本身的特性让每个实现方式的算法发生异化,不过基本原理却很相似。

链接分析算法的机制其实很简单:你可以用矩阵表示一幅“图“,形成本征值问题。本征值问题可以帮助你分析这个“图”的结构,以及每个节点的权重。这个算法于1976年由Gabriel Pinski和Francis Narin提出。

谁会用这个算法呢?Google的网页排名,Facebook向你发送信息流时(所以信息流不是算法,而是算法的结果),Google+和Facebook的好友推荐功能,LinkedIn的工作推荐,Youtube的视频推荐,等等。

普遍认为Google是首先使用这类算法的机构,不过其实早在1996年(Google 问世2年前)李彦宏就创建的“RankDex”小型搜索引擎就使用了这个思路。而Hyper Search搜索算法建立者马西莫·马奇奥里也曾使用过类似的算法。这两个人都后来都成为了Google历史上的传奇人物。

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


飞机,汽车,电视,手机,卫星,工厂和机器人等等事物中都有这个算法的身影。

简单来讲,这个算法主要是通过“控制回路反馈机制”,减小预设输出信号与真实输出信号间的误差。只要需要信号处理,或电子系统来控制自动化机械,液压和加热系统,都需要用到这个算个法。

没有它,就没有现代文明。

9. 数据压缩算法

数据压缩算法有很多种,哪种最好?这要取决于应用方向,压缩mp3,JPEG和MPEG-2文件都不一样。

哪里能见到它们?不仅仅是文件夹中的压缩文件。你正在看的这个网页就是使用数据压缩算法将信息下载到你的电脑上。除文字外,游戏,视频,音乐,数据储存,云计算等等都是。它让各种系统更轻松,效率更高。

10. 随机数生成算法

到如今,计算机还没有办法生成“正真的”随机数,但伪随机数生成算法就足够了。这些算法在许多领域都有应用,如网络连接,加密技术,安全哈希算法,网络游戏,人工智能,以及问题分析中的条件初始化。

本文转载自:http://www.csdn.net/article/2014-06-03/2820046-Algorithm

共有 人打赏支持
丈量大地

丈量大地

粉丝 16
博文 52
码字总数 27634
作品 0
都江堰
程序员
私信 提问
对大学保持感激之情

大学学的是电子工程专业, 所以 51汇编, C , 信号处理...... 都是必修 那个时代,一样浮躁. 大家都埋怨学校学的东西过时了.... 因为据说, C++的时代来了,并且java要主宰世界了. 但是学校甚至连...

宏哥
2012/07/10
546
8
9miao.com/dazhuzai

dazhuzai #####"大主宰ol"由9秒社团原创,任何相关问题均可到论坛进行提问,我们会在第一时间做出回复,提问地址:http://www.9miao.com/forum-54-1.html #####9秒社团“大玩具开源计划”:h...

9miao.com
2015/01/19
0
0
中国网民超4.4亿 汉语5年内成互联网主宰语言

法制晚报报讯(记者 尹晓琳) 互联网咨询专业提供商The Next Web日前发布了一项统计报告指出,互联网的使用在中国以惊人的速度增长,5年内,汉语将超过英语成为互联网上新的主宰语言。 数据显...

红薯
2010/12/26
804
16
微信社交文字MUD游戏《大主宰OL》完整开源,基于firefly

说明: “大主宰ol”是一款基于微信公众号开发的即时回应式文字mud网游,游戏以著名作家天蚕土豆的最新热门著作《大主宰》为背景改编而成,由9秒社团原创开源。 用户只需在微信公众号游戏平台...

大鸡蛋
2015/01/19
19.6K
33
2014百度沸点榜单

  百度沸点2014搜索风云榜发布,包括十大社会热点,十大焦点人物,十大移动热搜景点等21个子榜单。这些榜单的排名依据PC网民和移动网民在过去一年搜索关键词的次数得出,是每年度最受期待、...

ytkahcom
2016/12/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

深入 理解char * ,char ** ,char a[ ] ,char *a[] 的区别

C语言中由于指针的灵活性,导致指针能代替数组使用,或者混合使用,这些导致了许多指针和数组的迷惑,因此,刻意再次深入探究了指针和数组这玩意儿,其他类型的数组比较简单,容易混淆的是字...

天王盖地虎626
18分钟前
1
0
关于我这三年的架构历程(待完成)

从16年7月实习至今,快三年的开发经历中,经手了好几个项目。目前有幸作为一个项目的负责人,完成了一个项目的完全架构设计。因此想记录下这份架构设计中的点点面面。 总架构: 基于DNS的负载...

赵熠熠
19分钟前
0
0
springboot 使用 flyway 进行数据库版本管理

要在启动时自动运行Flyway数据库迁移,请将其添加 org.flywaydb:flyway-core到类路径中。 迁移是表单中的脚本V<VERSION>__<NAME>.sql(使用<VERSION>下划线分隔的版本,例如“1”或“2_1”)...

NotFound403
38分钟前
4
0
spring 5.1.5版本(二)

spring 5.1.5版本(一) spring 5.1.5版本(二) spring 5.1.5版本(三) 对象创建方式 方式一 applicationContext.xml <?xml version='1.0' encoding='UTF-8'?><beans xmlns="http://ww......

gwl_
40分钟前
0
0
CMake生成Mingw用的Make文件

CMake 在win下 默认会生成vc++的nmake用的make 当没安装时 就会报 -- Building for: NMake Makefiles -- The C compiler identification is unknown -- The CXX compiler identification is......

shzwork
57分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部