加载中…
个人资料
JackieWang
JackieWang
  • 博客等级:
  • 博客积分:0
  • 博客访问:137,039
  • 关注人气:142
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

时间复杂度计算实例

(2013-02-03 18:23:57)
标签:

时间

复杂度

实例

教育

分类: 数据结构及算法

时间复杂度计算实例

表示时间复杂度的阶有:

O(1) :常量时间阶          O (n):线性时间阶

O(n) :对数时间阶    O(nn) :线性对数时间阶

O (nk)k≥2k次方时间阶

例1  两个n阶方阵的乘法

              for(i=1i<=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] ; 

}

由于是一个三重循环,每个循环从1n,则总次数为: n×n×n=n3 时间复杂度为T(n)=O(n3)【立方阶】

例2  {++x; s=0 ;}

x自增看成是基本操作,则语句频度为1,即时间复杂度为O(1)【常量阶】

如果将s=0也看成是基本操作,则语句频度为2,其时间复杂度仍为O(1),即常量阶。

例3   for(i=1; i<=n; ++i)

               { ++x; s+=x ; } 

语句频度为:2n,其时间复杂度为:O(n) ,即为【线性阶】

例4   for(i=1; i<=n; ++i)

    for(j=1; j<=n; ++j)

                   { ++x; s+=x ; }

   语句频度为:n*n*2=2n2 ,其时间复杂度为:O(n2) ,即为【平方阶】

定理:若A(n)=amnm +am-1nm-1+…+a1n+a0是一个m次多项式,则A(n)=O(nm)

例5   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(nn) < O(n2) < O(n3)

  指数时间的关系为:

    O(2n) < O(n!) < O(nn)

n取得很大时,指数时间算法和多项式时间算法在所需时间上非常悬殊。

1:素数的判断算法。

void prime( int n)

 

 

int i=2 ;

while ( (n%i)!=0 && i*1.0< sqrt(n) )  

     i++ ;

if (i*1.0>sqrt(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)

或者说是O(sqrt(n))

 

2:冒泡排序法。

Void bubble_sort(int a[]int n)

 

change=false;

for (i=n-1; change=TURE; i>1 && change; --i)

for (j=0; j<i; ++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 【平方阶】                  

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有