算法的相关理论概述

jopen 6年前

算法概述

从字面意义上理解,算法(Algorithm)就是用于计算的方法,并通过这种方法可以达到预期的计算结果。算法的专业解释:算法是解决实际问题的一种精确描述的方法,算法是对特定问题的求解步骤的一种精确描述方法。但更广泛认可的算法专业定义:算法是模型分析的一组可行的、精确的和有穷的规则。

通俗的讲,算法可以理解为一个完整的解题步骤,由一些基本运算和规定的运算顺序而构成。通过这样的解题步骤可以解决特定的问题。从计算机程序设计的角度看,算法由一系列求解问题的指令构成,能够根据规范的输入,在有限的时间内获得有效的输出结果。算法代表了用系统的方法来描述解决问题的一种策略机制。

典型的算法可以从其中抽象出5个特征:有穷性、确切性、输入、输出和可行性。

 有穷性:

算法的指令或者步骤的执行次数是有限的,执行时间也是有限的。

 确切性:

算法的每一个指令或者步骤都必须有明确的定义和描述。

 输入:

一个算法应该有相应的输入条件,用来刻画运算对象的初始情况。

输出:

一个算法应该有明确的结果输出。这是容易理解的,没有得到结果的算法是毫无意义的。

 可行性:

算法的执行步骤必须是可行的且可以在有限的时间内完成。

算法的分类

算法是一门古老且庞大的学科,随着历史的发展,演化出多种多样的算法。按照不同的应用和特性,可以分为不同的类别。

1.按照应用来分类

按照算法的应用领域,也就是解决的问题,算法可以分为基本算法、数据结构相关的算法、几何算法、图论算法、规划算法、数值分析算法、加秘/解密算法、排序算法、查找算法、并行算法和数论算法等。

2.按照确定性来分类

按照算法结果的确定性来分类,可以分为确定性算法和非确定性算法。

•确定性算法:这类算法在有限的时间内完成计算,得到的结果是唯一的,且经常取决于输入值。

•非确定性算法:这类算法在有限的时间内完成计算,但是得到的结果往往不是唯一的,也就是存在多值性。

3.按照算法的思路来分类

按照算法的思路来分类,算法可以分为递推算法、递归算法、穷举算法、贪婪算法、分治算法、动态规划算法和迭代算法等多种。

算法相关概念的区别

算法其实是一种很抽象的概念,往往需要依托于具体的实现方法才能体现其价值,例如在计算机编程中的算法、数值计算中的算法等。本文所重点讲解的便是算法在计算机中的应用。正是由于算法的抽象性,导致读者很容易产生混淆,这里有必要说明一些基本概念。

算法与公式的关系

从当前所谈到的算法,让我们很容易联想到数学中的公式。公式也是解决某类问题,有特定的输入和结果输出,能在有限时间内完成,并且公式都是完成可以操作计算的。其实公式确实是提供了一种算法,但算法不完全等于公式。

公式是一种高度精确的计算方法,可以认为就是一种算法,其是人类智慧的结晶。而算法并不一定是公式,算法的形式可以比公式更复杂,解决的问题更加广泛。

算法与程序的关系

正如前面所述,算法是依托于具体的实现方式的。虽然我们一提到算法,就联想到计算机程序设计,但算法并非如此。例如,在传统的笔算中,通过纸和笔按照一定的步骤完成的计算也是算法的应用。在速记中,人们通过特殊的方式来达到快速牢固记忆的目的,这也是一种算法的应用。

在计算机程序设计中,算法的体现更加广泛,几乎每个程序都需要用到算法,只不过有些算法比较简单,有些算法比较复杂。

算法和程序设计语言是不同的。目前较为主流的程序设计语言,包括VB、C、C++、Java、C#等。程序设计语言是算法实现的一种形式,也就是一种工具。我们往往需要首先熟悉程序语言的语法格式,然后才能使用这种程序语言编写合适的算法实现程序。学习一门程序设计语言是比较容易的,难的是如何正确合理地运用算法来编写求解问题。

算法和数据结构的关系

数据结构是数据的组成形式,可以用来表征特征的对象数据。在计算机程序设计中,操作的对象是各种各样的数据,这些数据往往拥有不同的数据结构,例如数组、结构体、联合、指针和链表等。因为不同的数据结构所采用的处理方式不同,计算的复杂程度也不同,因此算法往往是依赖于某种数据结构的。换言之,数据结构是算法实现的基础。

计算机科学家尼克劳斯•沃斯(Nikiklaus Wirth)曾提出了一个著名的公式:数据结构+算法=程序。后来出版了《数据结构+算法=程序》,这一著作。我们从中可以看出算法和数据结构的关系。

通过前面的介绍,我们现在对程序、算法、数据结构设计有了比较深刻的认识。如果给出一个公式的话,可以表述成如下形式:

数据结构+算法+程序设计语言=程序

这里,数据结构往往表示的是处理的对象,算法是计算和处理的核心方法,程序设计语言是算法的实现方法。它们之间的综合便构成一个实实在在的程序。算法是解决问题的一个抽象方法和步骤,同一个算法在不同的语言中具有不同的实现形式,这依赖于数据结构的形式和程序设计语言的语法格式(规则)。

算法的性能评价

算法其实就是解决问题的一种方法,一个问题的解决往往可以采用多种方法,但每种方法所有的时间和得到的效果往往是不一样的。好的算法执行效率高,所耗费的时间短;差的算法则往往需要耗费更多的时间,导致效率很低。

算法的一个重要任务便是找到合适的、效率最高的解决问题的方法,也就是做好的算法。从理论上,这需要对算法的性能能有一个合理的评价。一个算法优劣往往通过算法复杂度来衡量,算法复杂度包括时间复杂度和空间复杂度两个方面。

时间复杂度

时间复杂度也就是通常所说的算法执行所需要耗费的时间,时间越短,算法越好。一个算法执行的时间往往无法精确估算,通常需要在实际的计算机运行才能知道。但是,我们也可以对算法代码进行估算,而得到算法的时间复杂度。

首先,算法代码执行的时间往往和算法代码中语句执行的数量有关。由于每条语句执行都是需要时间的,语句执行的次数越多,整个程序所耗费的时间就越长。因此,简短、精悍的算法程序往往执行速度快。

另外,算法的时间复杂度还与问题的规模有关。这方面的专门的算法分析中有详细的分析,有兴趣的读者可以参阅算法分析的相关书籍。

空间复杂度

空间复杂度指的是算法程序在计算机中执行所需要消耗的存储空间。空间复杂度其实可以分为以下两个方面:

• 程序保存所需要的存储空间,也就是程序的大小。

• 程序在执行过程中所需要消耗的存储空间资源,例如程序在执行过程中的中间变量等。

一般来说,程序的大小越小,执行过程所消耗的资源越少,这个程序越好。在算法分析中,空间复杂度有更为详细的量度,有兴趣的读者可以阅读相关的书籍。

文章出处: http://blog.csdn.net/mahoking/article/details/43758463