`

主宰全球的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. 随机数生成算法

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

分享到:
评论

相关推荐

    主宰世界的十大算法

    关于比较重要比较常见的软件算法的说明介绍,复杂的算法都是基于这些算法之上。

    主宰创意时代的6大就业力.pptx

    主宰创意时代的6大就业力.pptx

    2015:五大趋势将主宰安全领域.pdf

    2015:五大趋势将主宰安全领域.pdf2015:五大趋势将主宰安全领域.pdf

    ESPERIS-全球氢市场—谁将主宰这场比赛?(英文).pdf

    然而,我们不仅需要关注欧洲市场,更应放眼全球,思考这个市场的潜力究竟有多大。 目前全球氢能市场规模尚处于初级阶段,估计每年生产约74百万吨。美国生产约10百万吨氢气,略高于欧盟。波兰也凭借每年1百万吨的...

    主宰未来10年 OLED强在哪、液晶弱在哪

    未来随着OLED生产技术的不断进步和成本的降低,预计OLED有望在更多领域取代LCD技术,主宰未来的显示市场。然而,LCD技术凭借其成熟度高、价格低廉的特点,仍将长期存在并在一些应用场景中保持其市场地位。

    本科毕业设计-基于矩阵分解的推荐算法研究(源码+全部数据).zip

    《基于矩阵分解的推荐算法研究》 笔记仓库 Github Gitee Software Language:Python3 Compile:IPython IDE:JupyterLab \ JupyterNotebook License:GPL-3.0 Struction AmazonProduct:亚马逊产品数据分析和产品...

    云计算:信息时代的新主宰.pdf

    以Google、IBM、Apple、微软等为代表的大公司,正在构建这些云服务,为用户提供高效、便捷且成本低廉的数据处理解决方案。 云计算的关键特性包括以用户为中心、以任务为中心、强大计算能力、弹性扩展性、高可用性和...

    命运的主宰者作文.doc

    【命运的主宰者】 在人生的舞台上,我们每个人都扮演着各自的角色,而关于命运的主宰者这一话题,一直以来都引发了广泛的讨论。有人认为命运是由至高无上的上帝所主宰,而另一些人则坚信命运掌握在自己的手中。这篇...

    10秒钟轻松卸载linux系统,让windows主宰电脑

    标题中的“10秒钟轻松卸载Linux系统,让Windows主宰电脑”指的是在计算机上同时安装了Linux和Windows双操作系统的情况下,如何快速地卸载Linux系统,以便让Windows成为唯一的操作系统。这一过程通常涉及到主引导记录...

    主宰自己的生活和快乐作文.doc

    这篇文章探讨了如何主宰自己的生活和追求快乐的主题。文章指出,我们不应该被外界的声音左右,而应该学会倾听内心,保持独立思考。"主宰自己"意味着要有主见,不盲目跟从他人,不受外界环境影响,而是根据自己的认知...

    未来中国将主宰亚洲半导体市场.pdf

    近年来,中国在半导体产业中的影响力逐渐增大,正逐步主宰亚洲市场。这主要得益于中国在技术研发、生产能力提升和市场拓展方面的积极努力。中国拥有庞大的市场需求和完整的供应链,为半导体产业提供了广阔的发展空间...

    2015:五大趋势将主宰安全领域.docx

    在2015年的安全领域,五大趋势对整个行业产生了深远影响,这些趋势与互联网的快速发展密切相关,塑造了我们今天看待网络安全的方式。以下是对这些关键趋势的深入解析: 1. **网络犯罪分子的合作加强** 在2014年,...

    炫酷真我主宰校园1.doc

    炫酷真我主宰校园1.doc

    毕马威发布2017年颠覆性技术变革趋势报告:AI、IoT和机器人这三大技术趋势,主宰未来商业变革

    通过深度学习、自然语言处理和其他高级算法的应用,AI能够实现自动化决策、个性化服务和高效的数据分析等功能。AI的发展不仅提高了生产力,也为许多行业带来了新的商业模式和服务方式。 2. **物联网(IoT)**:IoT...

    九年级历史下册《第18课经济全球化的趋向》导学案(无答案)川教版.pdf

    这表明世界不再由单一超级大国主宰,而是呈现出多个经济中心;全球化深入发展,各国经济相互依存度提高;信息化成为经济发展的重要驱动力;市场经济成为多数国家的主导经济模式。 【经济全球化对发展中国家的影响】...

    主宰自己的命运作文.doc

    【主宰自己的命运】这篇文章以读后感的形式探讨了个人命运与态度的关系,主要围绕着海伦·凯勒的人生经历展开。海伦·凯勒,一个在出生不久后就遭受聋、盲、哑多重打击的人,她的故事成为了挑战命运的典范。文章通过...

    做命运的主宰作文.doc

    【标题】:做命运的主宰——从《战胜困难的孩子》谈起 【描述】:这篇文档是一篇关于如何面对和战胜困难的作文,通过阅读《战胜困难的孩子》的故事,阐述了勇者如何掌控自己的命运。 【标签】:范文 【部分内容...

    黑帽之王《零距离主宰站群泛目录》售价18888

    "黑帽之王《零距离主宰站群泛目录》"是针对这一策略的高级工具,其官方售价高达18888元,表明它在SEO行业内可能被视为一种高端、专业的解决方案。 首先,我们要理解什么是“泛目录”。泛目录是通过创建大量子目录,...

Global site tag (gtag.js) - Google Analytics