算法及其特征

 

1.算法(Algorithm)

算法是对特定问题求解步骤的一种描述，是指令的有限序列。描述算法需要一种语言，可以是自然语言、数学语言或者是某种计算机语言。

算法一般具有下列5个重要特性：

（1）输入： 一个算法应该有一个或多个输入：

（2）有穷性：一个算法必须在执行有穷步骤之后正常结束，而不能形成无穷循环：

（3）确定性：算法中的每一条指令必须有确切的含义，不能产生多义性：

（4）可行性：算法中的每一条指令必须是切实可执行的，即原则上可以通过已经实现的基本运算执行有限次来实现：

（5）输出：一个算法应有零个或多个输出，这些输出是同输入有某个特定关系的量。

 

2. 算法的描述

一个算法可以用自然语言、计算机程序语言或其它语言来说明，惟一的要求是该说明必须精确地描述计算过程。

一般而言，描述算法最合适的语言是介于自然语言和程序语言之间的伪语言。它的控制结构往往类似于Pascal、borland C++、visual C++等程序语言，但其中可使用任何表达能力强的方法使算法表达更加清晰和简洁，而不至于陷入具体的程序语言的某些细节。

3. 算法分析技术

1) 评价算法好坏的标准

　评价一个算法好坏算法首先应该是"正确"的,另外，主要还要看这个算法所要占用机器资源的多少。而在这些资源中时间空间是两个最主要的方面。

① 问题的规模。所谓问题的规模是指算法中数据元素的数量。下文常用小写字母n来表示。假设某问题只有一个数据元素(n=1)，算法的时间、空间占用无论如何也不会很大，可以忽略不予考虑。但是，某问题有成千上万个数据元素时，即问题的规模n很大时，算法的时间、空间占用就不可忽略。

② 空间。所谓算法的空间代价（或称空间复杂性）指的是：当问题的规模以某种单位由1增至n时，解决该问题的算法实际所占用的空间也以某种单位由1增至f（n）。则称该算法的空间代价是f（n）。

③时间。算法的时间代价（或称时间复杂性）。

时间复杂度分析

（1）算法耗费的时间和语句频度

所谓某语句的频度，是指在一个算法中该条语句重复执行的次数。一个算法所耗费的时间=算法中每条语句的执行时间之和。

每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间

算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。

若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。

 【算法1.1】求两个n阶方阵的乘积 C=A×B,其算法如下:

# define n 100 // n 可根据需要定义,这里假定为100

void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n])

{ //右边列为各语句的频度

int i ,j ,k;

(1) for(i=0; i＜n;j++) n+1

(2)   for (j=0;j＜n;j++) { n(n+1)

(3)     C[i][j]=0; n2

(4)     for (k=0; k＜n; k++) n2(n+1)

(5)       C[i][j]=C[i][j]+A[i][k]*B[k][j]; n3

       }

     }

该算法中所有语句的频度之和(即算法的时间耗费)为：

         T(n)=2n3+3n2+2n+1 (1.1)

分析：

语句(1)的循环控制变量i要增加到n，测试到i=n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得语句(3)，(4)和(5)的频度分别是n2，n2(n+1)和n3。

算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。

（2）渐进时间复杂度评价算法时间性能

算法的时间度量依据算法中最大语句频度来估算，它是问题规模n的某个函数f（n）。算法的时间量度记作：

　　　　　　　　　T(n)=O(f(n))

【算法1.2】变量计数。

(1) x=1;

(2) for(i=1;i<=n;i++)

(3)     for(j=1;j<=i;j++)

(4)         for(k=1;k<=j;k++)

(5)             x++;

该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：

则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)。