数据结构课程PPT第1章绪论.ppt

在一个算法中,进行基本运算的次数越少,其运行时间也就相对地越少；基本运算次数越多,其运行时间也就相对地越多。 所以,通常把算法中包含基本运算次数的多少称为算法的时间复杂度，也就是说，一个算法的时间复杂度是指该算法的基本运算次数。 算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作： 　　　 T(n)=O(f(n)) 记号“O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。“O”的形式定义为： 若f(n)是正整数n的一个函数，则T(n)=O(f(n))表示存在一个正的常数M，使得当n≥n0时都满足： |T(n)|≤M|f(n)| 也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样既可简化T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。 例如，T(n)=3n2-5n+10000=O(n2) 本质上讲，是一种最高数量级的比较 一个没有循环的算法的基本运算次数与问题规模n无关，记作O(1)，也称作常数阶。 一个只有一重循环的算法的基本运算次数与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。 其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。 各种不同数量级对应的值存在着如下关系： O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!) 思考题： 　　为什么要进行算法的时间复杂度分析？ 例1.4 求两个n阶方阵的相加C=A+B的算法如下,分析其时间复杂度。 #define MAX 20 //定义最大的方阶 void matrixadd(int n,int A[MAX][MAX], int B[MAX][MAX],int C[MAX][MAX]) { int i,j; for (i=0;in;i++) for (j=0;jn;j++) C[i][j]=A[i][j]+B[i][j]; } 该算法中的基本运算是两重循环中最深层的语句C[i][j]=A[i][j]+B[i][j]，分析它的频度，即： 　T(n)= =O(n2) 例1.5 　分析以下算法的时间复杂度。 int fun(int n) { int i,j,k,s; s=0; for (i=0;i=n;i++) for (j=0;j=i;j++) for (k=0;k=j;k++) s++; return(s); } 基本语句或基本操作 解：该算法的基本操作是语句s++，其频度： T(n)= =O(n3) 则该算法的时间复杂度为O(n3)。 例1.6 　分析以下算法的时间复杂度。 void func(int n) { int i=0,s=0; while (sn) { i++; s=s+i; } } 基本语句 解：对于while循环语句，设执行的次数为m，i从0开始递增1，直到m为止，有： s=0+1+2+…+(m-1)=m(m-1)/2， 并满足s=m(m-1)/2n，则有m＜ 。 T(n)=O( ) 所以，该算法的时间复杂度为O( )。 例1.7 有如下算法： void fun(int a[],int n,int k) //数组a共有n个元素 { int i; if (k==n-1) for (i=0;in;i++) 　　//n次 printf(%d\n,a[i]); else { for (i=k;in;i++)　　//n-k次 a[i]=a[i]+i*i; fun(a,n,k+1); } } 调用上述算法的语句为fun(a,n,0)，求其时间复杂度。 解：设fun(a,n,0)的时间复杂度为T(n)，则fun(a,n,k)的执行时间为T1(n,k)，由fun()算法可知： T1(n,k)=n 当k=n-1时 T1(n,k)= (n-k)+T1(n,k+1) 其他情况 则 T