算法分析应用举例.ppt

《算法分析应用举例.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析应用举例算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作T(n)=O(f(n))，称作算法的渐近时间复杂度(AsymptoticTimecomplexity)，简称时间复杂度。一般地，常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。表示时间复杂度的阶有：O(1)：常量时间阶O(n)：线性时间阶O(㏒n)：对数时间阶O(n㏒n)：线性对数时间阶O(nk)：k≥2，k次方时间阶例１两个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

2、]*b[k][j];}由于是一个三重循环，每个循环从1到n，则总次数为：n×n×n=n3时间复杂度为T(n)=O(n3)例２{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)。如果将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)=amnm+am-1n

3、m-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)例５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)

4、n2)sqrt(n))printf(“&d是一个素数”,n);elseprintf(“&d不是一个素数”,n);}

5、嵌套的最深层语句是i++；其频度由条件((n%i)!=0&&i*1.01&&change;--i)for(j=0;ja[j+1]){a[j]←→a[j+1];change=TURE;}}最好情况：0次最坏情况：1+2+3+⋯+n-1=n(n-1)/2平均时间复杂度为：O(n2)