数据结构第一章合编.ppt

如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。 例３ for(i=1; i=n; ++i) { ++x; s+=x ; } 语句频度为：2n，其时间复杂度为：O(n) ，即为线性阶。 例４ for(i=1; i=n; ++i) 　　　　for(j=1; j=n; ++j) { ++x; s+=x ; } 语句频度为：2n2 ，其时间复杂度为：O(n2) ，即为平方阶。 定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m) 例５ for(i=2;i=n;++i) for(j=2;j=i-1;++j) {++x; a[i,j]=x; } 语句频度为： 1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 ∴时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。 一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。 以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(㏒n)O(n)O(n㏒n)O(n2)O(n3) 指数时间的关系为： O(2n)O(n!)O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。 例1：素数的判断算法。 Void prime( int n) /* n是一个正整数 */ { int i=2 ; while ( (n% i)!=0 i*1.0 sqrt(n) ) i++ ; if (i*1.0sqrt(n) ) printf(“d 是一个素数\n” , n) ; else printf(“d 不是一个素数\n” , n) ; } 嵌套的最深层语句是i++；其频度由条件( (n% i)!=0 i*1.0 sqrt(n) ) 决定，显然i*1.0 sqrt(n) ，时间复杂度O(n1/2)。 例2：冒泡排序法。 Void bubble_sort(int a[]，int n) { change=false; for (i=n-1; change=TURE; i1 change; --i) for (j=0; ji; ++j) if (a[j]a[j+1]) { a[j] ←→a[j+1] ; change=TURE ; } } 最好情况：0次 最坏情况：1+2+3+?+n-1=n(n-1)/2 平均时间复杂度为： O(n2) 1.3.4 算法的空间分析 空间复杂度(Space complexity) ：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作： S(n)=O(f(n)) 其中： n为问题的规模(或大小) 该存储空间一般包括三个方面： 指令常数变量所占用的存储空间; 输入数据所占用的存储空间; 辅助(存储)空间。 一般地，算法的空间复杂度指的是辅助空间。 一维数组a[n]： 空间复杂度 O(n) 二维数组a[n][m]： 空间复杂度 O(n*m) 习 题 一 1 简要回答术语：数据，数据元素，数据结构，数据类型。 2 数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？ 3 数据结构的主要运算包括哪些？ 4 算法分析的目的是什么？算法分析的主要方面是什么？ 5 分析以下程序段的时间复杂度，请说明分析的理由或原因。 ⑴ Sum1( int n ) { int p=1, sum=0, m ; for (m=1; m=n; m++) { p*=m ; sum+=p ; } return (sum) ; } ⑵ Sum2( int n ) { int sum=0, m, t ; for (m=1; m=n; m++) { p=1 ; for (t=1; t=m; t+