数据结构(C语言)课件第1章幻灯片.ppt

分析评价算法时应考虑的因素： 1、正确性 在给定有效的输入数据后，算法经过有穷时间的计算能给出正确的答案。 2、复杂度 时间复杂度 3、简单性 4、最优性 算法A是最优的是指：在给定问题的所有算法中，A执行的进步运算次数最少 5、可读性 要求算法易于理解，便于分析 6、可修改可扩展性 如果问题P 的一个算法是A，为了解答一个与P类似的问题，希望对A稍做改动就可正确运行，如算法A满足这一点，则说A的可修改性好。 与算法效率有关的因素 程序设计语言 编译的代码质量 机器执行指令的速度 问题的规模 求解同样一个问题可能会有许多不同的算法，如何评价这些算法的好坏呢？ 首先算法必须是正确的。此外还需考虑： 1、算法易于理解，易于编程（在计算机上实现） ，易于调试。 2、要求算法高效，节省时间与空间。 一个算法运行所需时间的长短、空间的大小具有非常重要的意义。 时间和空间相互之间有一种制约关系，何者为重需视具体情况而定。 算法高效与算法易理解、易编程之间也有一种制约关系 这两个要求有时互相矛盾。因此，对反复运行的算法，首先考虑的是高效性，对偶尔运行的算法，则需突出算法易理解和易编程（以排序为例 － 冒泡排序和快速排序）。 我们重点考虑时间因素。 一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间又是该语句的执行次数（频度）与该语句执行一次所需时间的乘积。 我们假定，每条语句一次执行的时间都是相同的，为单位时间。这样我们对时间的分析就可以独立于软硬件系统。 我们将算法求解问题的输入量称为问题的规模，用一个整数来表示，一个算法的时间复杂度是该算法的时间耗费，一般地说，时间复杂度是问题规模的函数 － T( n )。 当问题的规模n 趋于无穷大时，把时间复杂度T( n )的数量级（阶）称为算法的渐进时间复杂度（有时简称为时间复杂度）。 严格的数学定义为：若T( n ) 和 f( n ) 是定义在正整数集合上的两个函数，当存在两个正的乘数C和n0时，使得对所有的 成立，则 都有 这时称T( n )的时间复杂度为f( n )数量级。 算法运行所需要的时间与两个因素有关： 1、问题实例的大小（如1000个数的排序）； 2、实例的具体情况（如1000个数的排列情况） 算法分析 1、假定每条语句的执行时间为单位时间。算法的时间复杂度是该算法中所有语句的执行频度之和。 例：求两个方阵的乘积 C＝A*B ＃define n 自然数 MATRIXMLT(float A[n][n],float B[n][n],float C[n][n]) { int i,j,k; for(i=0;in;i++) //n+1 for(j=0;jn;j++) //n(n+1) { C[i][j]=0; //n*n for( k=0;kn;k++) //n*n*(n+1) C[i][j]=A[i][k]*B[k][j] //n*n*n } } 2、一般情况下，对步进循环语句只考虑循环体语句的执行次数，而忽略该语句中部长加一、终值判别、循环转移等成份。因此，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度所决定的。 例： x=0;y=0; for (k=1;k=n;k++) x++; for (i=1;i=n;i++) for (j=1;j=n;j++) //n*n y++; 一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，而忽略循环体中步长加1、终值判断、控制转移等成分。 例： x=1; for (i=1;i=n;i++) for (j=1;j=i;j++) for (k=1;k=j;k++) x++; 3、选择执行的成分，如 if 语句的执行时间，决定于then 子句、else 子句耗时较多的部分 4、如果算法的执行时间是一个与问题规模n无关的常数，则算法的时间复杂度为常数阶，记作T(n)=O(1)。 例： temp = i; i = j; j = temp; 5、很多算法的时间复杂度不仅与问题的规模有关，而且还与它所处理的数据集的状态有关。通常是根据数据集中可能出现的最坏情况估计出算法的最坏时间复杂度。 例： i=n-1; whil