算法

（1）程序设计的要素

算法语言、算法、数据结构和程序设计技术。

（2）算法

解决特定问题的方法。

（3）算法的5个特性

1.有穷性

在合法输入下，一个算法必须在执行有穷步之后结束，而其中每一个步骤都能在有限时间内完成。

2.确定性

算法中每一个步骤、每一条指令都有确切的含义，对符合算法要求的任何输入数据都能正确执行。而对于相同的输入只能得出相同的输出。

3.可行性

算法中描述的操作都可以通过已经实现的基本操作执行有限次来实现。

4.算法有零个或多个输入

算法要有处理的对象，也就是数据。根据需要某些数据可以在执行时输入，并通过变量接受它们。有些数据可能已被嵌入算法中，或通过赋值方法使变量获得数据。

5.算法有一个或多个输出

输出是一组与输入量有着某种特定关系的量，是算法执行后的结果。

2.时间复杂度

算法的时间复杂度是评估算法的重要标准之一，它能较好地体现算法本身的时间效率，而与具体实现算法的计算机软件、硬件无关。时间复杂度在“算法的设计与分析”理论研究中占有重要地位，对于应用人员，只要求了解时间复杂度分析的一般原理，并能参照它作为选用算法的一个标准。

分析一个算法的时间复杂度首先要从中选取一种能在很大程度上体现该算法执行时间的基本操作，以该基本操作重复执行的次数作为度量。例如在矩阵相乘的算法中，乘法就是基本操作。在从一批整数中求最大数的算法中，对两个数据的比较就是基本操作，一批整数中数据的个数称为问题的规模。

一般情况下，算法基本操作重复执行的次数是问题规模n的某个函数f(n)。而算法的时间复杂度简单说来是指算法中某种基本操作执行次数的数量级。通常用T(n)=O(f(n))表示，其中O表示f(n)的数量级。

	例1.1 用C语言求两个n阶矩阵的乘积的算法	for(i=1;i<=n;i++)	 for(j=1;j<=n;j++)	 { 	 c[i][j]=0;	 for(k=1;k<=n;k++)	 c[i][j]= c[i][j]+a[i][k]*b[k][j];	 }

上述算法问题的规模为n，基本操作乘法的执行次数f(n)≈n*n*n，所以T(n)=O(n³)。

3.空间复杂度

类似于算法的时间复杂度，空间复杂度作为算法所需存储空间的量度，记作

S(n)= O(f(n))

其中n为问题的规模，算法所需存储空间是问题规模n的函数f(n)。空间复杂度对于“算法设计与分析”的研究也是必要的，但它的重要性远不如时间复杂度，本课程不做重点讨论。但程序设计人员在设计算法时始终要有“时、空”这一概念，要尽量避免存储空间的浪费。