数据结构-关于算法的讨论

一，什么是算法 ？算法的主要特征

概念算法即对特定问题求解步骤的描述，它是指令的有限序列，每一条指令代表一个或多个操作。

特征

有穷性：即算法可以经过有限个步骤，状态，指令后结束，不能无限执行下去。

确定性：在确定语境下具有唯一一条执行路径，因此相同的输入只能得到相同的输出。

可行性：任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成

输入性：除算法自己具有初始化条件外，必须给予输入项以刻画运算对象的初始情况

输出性：有一个或多个项输出，反映执行后的结果。

二，评价算法的几个依据

正确性：满足问题的需求，正确求解问题。

健壮性：遇到不正确输入能够处理，遇到异常情况能够正常终止

效率，存储空间：算法执行的时间（相对于同样的机器环境下），算法占用的空间

三，时间复杂度，空间复杂度

这两个概念分别是相对于标题二中“效率”，和“存储空间”来说的

关于算法的执行时间

通常认为：

1， 同一个算法，用不同的编程语言来实现，显然执行的绝对时间是不同的。实现的语言级别越高，执行效率就越低。

2， 以上条件相同，算法在性能不同的计算机上执行，消耗的绝对时间不同，除了硬件的性能（CPU，内存条）外，软件（如编译器，操作系统）也产生影响

3， 以上条件相同，算法在不同输入的情况下执行的绝对时间不同，如冒泡排序中，基本操作是比较相邻两个数的大小并交换，因此输入数据可能存在不需要执行交换的情况，减少了操作的执行时间。

因此以算法执行的绝对时间单位来衡量算法是不合适的。

关于算法的工作量

0， 可以理解为算法要执行的基本操作（固有数据操作）的重复执行次数，

1， 它应当是一个只受到问题的规模（记为整数量n）影响的函数（这很好理解，它不应当受到实现语言，计算机硬件，软件环境的影响）。

关于时间复杂度

算法工作量力求达到的结果是，以该工作量衡量的算法能够表现出：

在实现语言不同的情况下，语言级别越高效率越低，执行的绝对时间越低（为什么高级语言效率就低？）

在计算机性能不同的情况下，性能更好计算机的执行速度越快

因此，使得算法的工作量可以直接用来衡量效率。

定义问题规模n，则时间复杂度T(n),定义算法的工作量 f(n)应当如下：

T(n)=O（f（n））。

不同数量级时间复杂度

计算下列程序段的时间复杂度

              程序段：

(1){++x;s=0}：O（1）

(2)将上述语句放到一层循环中：若循环n次，则O（n）

（3）将上述语句放入到多层循环中：若每层循环的次数分别为n，m等等

，则时间复杂度为O（n*m*····）

O（1）,O(n),O(n平方)称为算法的数量级，常量阶，线性阶，平方阶。

此外还有指数阶O（n的k次方），对数阶（log n）等等，

绘制算法问题的规模n和时间复杂度的增长图

显然，在问题规模增长不断增长时，不同数量级的算法时间复杂度的增长率不同，（指数阶的算法在问题规模很小的时候就可以将时间复杂度突破天际！）