文档介绍：: .
算法复杂度分析算法与程序设计2010-08-3020:47:10阅读13评论0字号：大中小订阅首先阶0(n八2)、立方阶0(n八3)、k次方阶0(nAk)>指数阶0(25)时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，T(n)=0(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。
语句的频度：是该语句重复执行的次数。
例1：交换i和j的内容。
temp=i;i=j;j=temp;以上三条语句的频度均为1，该程序的执行时间是与问题规模n无关的常数，因此算法的时间复杂度为常数阶，记作T(n)=0(1)。
例2：变量计数。
x=0;y=0;for(k=1;k<=n;k++)x++;for(i=1;i<=n;i++)for(j=1;j<=n;j++)y++;以上语句中频度最大的语句是(6)，其频度为f(n)=”2,所以该程序段的时间复杂度为T(n)=0(n2)例3：求两个n阶方阵的乘积C=AXB,其算法如下:
#definen100voidMatrixMultiply(intA[n][n],intB[n][n],intC[n][n]){inti,j,k
for(i=1;i<=n;++i)/*次数n+1*/for(j=1;j<=n;++j)/*次数n*(n+1)♦/{C[i][j]=0;/*次数n2♦/for(k=1;k<=n,k++)/*次数n2(n+1)*/C[i][i]=C[i][j]+A[i][k]*B[k][i];/*次数n3*/}}T(n)=2n3+3n2+2n+1lim(T(n)/n3)=2T(n)=O(n3)例4：
{++x;s=0;}for(i=1;i<=n;++i){++x;s+=x;}(3)for(j=1;j<=n;++j)(4)for(k=1;k<=n;k++){++x;s+=x;}(5)i=1;while(i<=n)i=i*2;执行次数f(n)与n的关系是n=2Af(n)
含基本操作“x增1”的语句的频度分别为1,n,n2和log2n常见的时间复杂度，按数量级递增排列依次为：常数阶0(1),对数阶0(Log2n),线性阶0(n)，线性对数阶0(nLog2n)，平方阶0(n2)，立方阶0(n3)，指数阶0(2n)。
通常认为，具有指数阶量级的算法是实际不可计算的，而量级低于平方阶的算法是高效的。
是说明一个程序根据其数据n的规模大小所使用的大致时间和空间说白了就是表示如果随着n的增长时间或空间会以什么样的方式进行增长例for(inti=0;i<n;++i);这个循环执行n次所以时间复杂度是0(n)for(inti=0;i<n;++i)(for(intj=0;j<n;++j);}这嵌套的两个循环而且都执行n次那么它的时间复杂度就是0(n人2)时间复杂度只能大概的表示所用的时间而一些基本步骤所运行的时间不同我们无法计算所以省略如for(inti=0;i<n;++i)
a=b;和for(inti=0;i<n;++i);这个运行的时间当然是第二个快但是他们的时间复杂度都是0(n)判断时间复杂度看循环例1:交换i和j的内