APP下载

简单了解十大真实演算法的特点

消息来源:baojiabao.com 作者: 发布时间:2024-05-08

报价宝综合消息简单了解十大真实演算法的特点

首先在说这个之前,我们首先要搞明白,什么是算法?

算法就是任何明确定义的计算过程,它接受一些值或集合作为输入,并产生一些值或集合作为输出。因此,算法就是将输入转换为输出的一系列计算过程。算法不仅仅在电脑科学中可以使用,同样也存在于数学领域中。而且,一个有效的算法应该含有三个有效特性:

1. 有穷性:执行有限步骤后,算法终止;

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

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

十大算法是哪十大算法呢?

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

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

3. 狄克斯特拉算法 (Dijkstra's algorithm)

4. RSA非对称加密算法

5. 杂凑安全算法(Secure Hash Algorithm)

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

7. 连结分析算法(Link Analysis)

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

9. 资料压缩算法

10. 随机数生成算法

来源于网络

那么它们有什么特点呢?

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

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

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

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

幸亏有这些算法,才会有今天的人工智能、资料发掘、连结分析和大部分网页计算工具。

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

傅立叶变换能将满足一定条件的某个函式表示成三角函式(正弦和/或余弦函式)或者它们的积分的线性组合。在不同的研究领域,傅立叶变换具有多种不同的变体形式,如连续傅立叶变换和离散傅立叶变换。最初傅立叶分析是作为热过程的解析分析的工具被提出的。

快速傅立叶变换 (fast Fourier transform), 即利用计算机计算离散傅立叶变换(DFT)的高效、快速计算方法的统称,简称FFT。快速傅立叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅立叶变换所需要的乘法次数大为减少,特别是被变换的抽样点数N越多,FFT算法计算量的节省就越显著。

3、 狄克斯特拉算法 (Dijkstra's algorithm)

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩充套件,直到扩充套件到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如资料结构,图论,运筹学等等。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。

4、 RSA非对称加密算法

在资讯加密领域,有一个算法始终是世界上最重要的算法之一,它就是RSA算法。这个算法是由RSA公司的创始人所建立的,它使资讯加密惠及千家万户,奠定了当今资讯加密的运作基础。RSA算法用来解决一个简单而又复杂的问题:怎样在不同平台和终端使用者之间共享公钥,继而实现资讯加密。这样做更安全,金钥越长越难破解,就是加密速度慢了点。

5、 杂凑安全算法(Secure Hash Algorithm)

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

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

这其实是一个数学算法,不过已经广泛应用与计算机领域。如果没有这个算法,加密资讯也不会如此安全。通过一系列步骤将,它可以将一个合成数分解成不可再分的数因子。很多加密协议都采用了这个算法,就比如刚提到的RSA算法。

7、 连结分析算法(Link Analysis)

在因特网时代,不同入口间关系的分析至关重要。从搜索引擎和社交网站,到市场分析工具,都在不遗余力地寻找因特网的正真构造。连结分析算法一直是这个领域最让人费解的算法之一,实现方式不一,而且其本身的特性让每个实现方式的算法发生异化,不过基本原理却很相似。连结分析算法的机制其实很简单:你可以用矩阵表示一幅"图",形成本征值问题。本征值问题可以帮助你分析这个"图"的结构,以及每个节点的权重。这个算法于1976年由Gabriel Pinski和Francis Narin提出。

搜索引擎是如何进行网页的相关性排序的呢?除了看网页本身的关键词密度和关键词位置外,还要看一个更重要的要素,就是连结流行度(或称之为连结分析),几个方面结合起来就能让排序更加精确。连结流行度的原理是,一个网页拥有的反向连结越多,就越有可能是高质量网页,不然也不会有更多人愿意为其做连结。因此,在其他因数相同的条件下,反向连结越多的网页排名更靠前。

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

飞机,汽车,电视,手机,卫星,工厂和机器人等等事物中都有这个算法的身影。简单来讲,这个算法主要是通过"控制回路反馈机制",减小预设输出讯号与真实输出讯号间的误差。只要需要讯号处理,或电子系统来控制自动化机械,液压和加热系统,都需要用到这个算个法。

9、 资料压缩算法

压缩算法(compaction algorithm)是指资料压缩的算法,在电子与通讯领域也常被称为讯号编码,包括压缩和还原(或解码和编码)两个步骤。由于多媒体讯号的资料量巨大,所以需要压缩;同时,由于在多媒体资料中,存在着各种冗余,所以可以压缩。

10、 随机数生成算法

如今,计算机尚且无法生成真正的随机数(掷钱币、骰子、转轮、使用电子元件的噪音、核裂变等。需要满足随机性、不可预测性、不可重现性),但是可以生成伪随机数(只要是通过确定算法生成的随机数,就是伪随机。如Random算法和Shuffle算法)。随机数用于网络互联、资料加密、游戏、人工智能、优化分析等。

2019-08-15 11:56:00

相关文章