主宰世界的10大算法
所属分类 algo
浏览量 712
什么是算法?
任何定义明确的计算步骤都可称为算法,接受一个或一组值为输入,输出一个或一组值
来源:homas H. Cormen, Chales E. Leiserson 《算法导论第3版》
算法是用来解决特定问题的一系列步骤
算法必须具备如下3个重要特性
有穷性 执行有限步骤后,算法必须中止
确切性 算法的每个步骤都必须确切定义
可行性 特定算法须可以在特定的时间内解决特定问题
算法虽然广泛应用在计算机领域,但却源自数学
最早的数学算法可追溯到公元前1600年 Babylonians有关求因式分解和平方根的算法
1. 归并排序(MERGE SORT) 快速排序(QUICK SORT) 堆排序(HEAP SORT)
归并排序算法,是目前为止最重要的算法之一,是分治法的一个典型应用,由数学家John von Neumann于1945年发明
快速排序算法,结合了集合划分算法和分治算法,不是很稳定,但在处理随机列阵(AM-based arrays)时效率相当高
堆排序,采用优先队列机制,减少排序时的搜索时间,同样不是很稳定
与早期的排序算法相比(如冒泡算法),这些算法将排序算法提上了一个大台阶
2. 傅立叶变换和快速傅立叶变换
这两种算法简单,但却相当强大,整个数字世界都离不开它们
其功能是实现时间域函数与频率域函数之间的相互转化
因特网,WIFI,智能机,座机,电脑,路由器,卫星等几乎所有与计算机相关的设备都或多或少与它们有关
不会这两种算法,你根本不可能拿到电子,计算机或者通信工程学位
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是首先使用这类算法的机构
不过其实早在1996年(Google问世2年前)李彦宏就创建的“RankDex”小型搜索引擎就使用了这个思路
8. 比例微积分算法(Proportional Integral Derivative Algorithm)
飞机,汽车,电视,手机,卫星,工厂和机器人等都有这个算法的身影
这个算法主要是通过“控制回路反馈机制”,减小预设输出信号与真实输出信号间的误差
只要需要信号处理,或电子系统来控制自动化机械,液压和加热系统,都需要用到这个算个法。
9. 数据压缩算法
10. 随机数生成算法
计算机目前还没有办法生成“真正的”随机数,但伪随机数生成算法就足够了
这些算法在许多领域都有应用,如网络连接,加密技术,安全哈希算法,网络游戏,人工智能,以及问题分析中的条件初始化
上一篇
下一篇
数据结构基础概念和术语
计算机科学概论
华裔天才数学家陶哲轩自述
数学建模十大算法
数学简史
算法笔记