2003-2004(夏)9 陈光喜 般情况下,算法中基本操作重复执行的 次数是问题规模n的某个函数,算法的时 间量度记作T(n)=O(f(n) 称作算法的渐近时间复杂度 例1fo(=1,I<=n+1 for(=1j<=n;++j) c[=0; (k=1k<=n;++k) c团]+=a[k]*b[k
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 一般情况下，算法中基本操作重复执行的 次数是问题规模n的某个函数，算法的时 间量度记作 T(n)=O(f(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]+=a[I][k]*b[k][j]; }
2003-2004(夏)9 讲陈光喜 ●由于是一个三重循环,每个循环从1到n,则总 次数为:n×n×n=n3 ●时间复杂度为T(n)=On3) 频度:是指该语句重复执行的次数 例2for(=2;<=n;++ for(=2ij<=i-1;++j) d++x; ai,j=x ●语句频度为: 1+2+3+.+n-2=(1+n2)×(n-2)2 =(n-)(n-2)2=n2-3n+2
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ 由于是一个三重循环，每个循环从1到n，则总 次数为: n×n×n=n3 ⚫ 时间复杂度为T(n)=O(n3) 频度：是指该语句重复执行的次数 例2 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
2003-2004(夏)9 主讲,陈光喜 ●∴时间复杂度为O(n2) ●一个算法时间为O(1)的算法,它的基本 运算执行的次数是固定的。总的时间由 个常数来限界。而一个时间为Q(n)的 算法则由一个k次多项式来限界。 ●常见多项式时间算法关系 O(1<O(ogn)<o(n)o(nlogn)<O(n2 o(n3) ●常见指数时间算法关系 O(2)On!)<O(n) ●指数时间算法能否化简为多项式时间算 法?( NP-hard
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ ∴时间复杂度为O(n2) ⚫ 一个算法时间为O(1)的算法，它的基本 运算执行的次数是固定的。总的时间由 一个常数来限界。而一个时间为O(nk)的 算法则由一个k次多项式来限界。 ⚫ 常见多项式时间算法关系 O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3) ⚫ 常见指数时间算法关系 O(2n )<O(n!)<O(nn ) ⚫ 指数时间算法能否化简为多项式时间算 法?(NP-hard)
2003-2004(夏)9 讲陈光喜 ●有的情况下,算法中基本操作重复执行的次数 与问题的输入数据有关 o Void bubble-sort(int a[ int n) for(F=n-1; change=TURE; I>1 & change; -I) i change=false for(=0j<1;++j) if(a]aj+lD a]←→a[j+1] change=TURE)) ●最好情况:0次,最坏情况:n(n-1)/2 ●通常考虑最坏时间复杂度
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ 有的情况下，算法中基本操作重复执行的次数 与问题的输入数据有关。 ⚫ Void bubble-sort(int a[]，int n) for(I=n-1;change=TURE;I>1 && change;--I) { change=false; for(j=0;j<I;++j) if (a[j]>a[j+1]) { a[j] ←→a[j+1]; change=TURE}} ⚫ 最好情况：0次,最坏情况: n(n-1)/2 ⚫ 通常考虑最坏时间复杂度
2003-2004(夏)9 讲陈光喜 算法的空间复杂度(略) ●空间复杂度:算法所需存储空间的度量 1.3.4算法描述 伪语言: 1)符号表达式 2)赋值语句 3)控制转移语句 4)循环语句 5)其他语句
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 算法的空间复杂度(略) ⚫ 空间复杂度:算法所需存储空间的度量 1.3.4 算法描述 伪语言: 1)符号表达式 2)赋值语句 3)控制转移语句 4)循环语句 5)其他语句