| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1480 人关注过本帖
标题:求循环次数和时间复杂度
只看楼主 加入收藏
zzsy04et138
Rank: 1
等 级:新手上路
帖 子:113
专家分:0
注 册:2006-10-18
收藏
 问题点数:0 回复次数:14 
求循环次数和时间复杂度
for(i=0;i<n;i++)
for(j=0;j<i;j++){
p=i*j;
printf("%d",p);
}
则执行语句"p=i+j;"的次数是多少?且时间复杂度为多少?

搜索更多相关主题的帖子: 时间 
2007-10-07 08:42
limeng_HOHO
Rank: 2
来 自:上海
等 级:论坛游民
帖 子:49
专家分:50
注 册:2007-7-16
收藏
得分:0 
次数是n(n-1)/2
复杂度是O(P*n*(n-1)/2) 其中P是执行一次乘法操作所用的时间

世界并不美丽 然而又因此而美丽
2007-10-07 08:55
zzsy04et138
Rank: 1
等 级:新手上路
帖 子:113
专家分:0
注 册:2006-10-18
收藏
得分:0 
它说时间复杂度是0(n*n)

2007-10-07 09:12
zzsy04et138
Rank: 1
等 级:新手上路
帖 子:113
专家分:0
注 册:2006-10-18
收藏
得分:0 
再问一题哈.
有如下程序段:
int x,y;
scanf("%d%d",&x,&y);
do{
x*=1.8;
y/=3;
}while(y-x>=10);
将上述do-while结构的程序段改写为:
(1)while结构
(2)for结构

2007-10-07 09:14
死了都要C
Rank: 4
来 自:四川成都
等 级:贵宾
威 望:13
帖 子:1582
专家分:116
注 册:2006-12-7
收藏
得分:0 
回复:(zzsy04et138)它说时间复杂度是0(n*n)
O(P*n*(n-1)/2)

==》O( P * (n*n+n) / 2 ) 当n很大的时候``如n=1000000 这个时候得到的值就是``1000001000000/2==50000500000

这个时候项n对结果的影响很小了``只有 500000/50000500000==1/100001大概就是%0。001``所以可以忽略项n

那么结果就是 O( P * (n*n/2) ) 2只是系数``所以转化一下``O( P * n*n )``这个是求总时间的``

那么复杂度当然就是 O(n*n)



女施主``我给你``送茶来了```师太``你就从了老衲吧``
代码本天成~~~妙头偶得之```
2007-10-07 09:50
limeng_HOHO
Rank: 2
来 自:上海
等 级:论坛游民
帖 子:49
专家分:50
注 册:2007-7-16
收藏
得分:0 
恩 谢谢ls指正

世界并不美丽 然而又因此而美丽
2007-10-07 09:55
limeng_HOHO
Rank: 2
来 自:上海
等 级:论坛游民
帖 子:49
专家分:50
注 册:2007-7-16
收藏
得分:0 
int x,y;
scanf("%d%d",&x,&y);
x*=1.8;
y/=3;
while(y-x>=10)
{
x*=1.8;
y/=3;
}
**********************
int x,y;
scanf("%d%d",&x,&y);
for(;y-x>=10;x*1.8,y/3);

世界并不美丽 然而又因此而美丽
2007-10-07 09:59
zzsy04et138
Rank: 1
等 级:新手上路
帖 子:113
专家分:0
注 册:2006-10-18
收藏
得分:0 
下面的for语句
for(x*=1.8,y/=3;y-x>=10;x*=1.8,y/=3);
这样和你上面写的有区别吗?

---------------------
这题,我主要不明白的是,为什么
int x,y;
scanf("%d%d",&x,&y);
x*=1.8; -------------这两行,为什么要加上去?
y/=3; ----------------
while(y-x>=10)
{
x*=1.8;
y/=3;
}

2007-10-07 10:08
死了都要C
Rank: 4
来 自:四川成都
等 级:贵宾
威 望:13
帖 子:1582
专家分:116
注 册:2006-12-7
收藏
得分:0 
意思就是先DO一下````

女施主``我给你``送茶来了```师太``你就从了老衲吧``
代码本天成~~~妙头偶得之```
2007-10-07 10:10
zzsy04et138
Rank: 1
等 级:新手上路
帖 子:113
专家分:0
注 册:2006-10-18
收藏
得分:0 
以下是引用死了都要C在2007-10-7 9:50:23的发言:
O(P*n*(n-1)/2)

==》O( P * (n*n+n) / 2 ) 当n很大的时候``如n=1000000 这个时候得到的值就是``1000001000000/2==50000500000

这个时候项n对结果的影响很小了``只有 500000/50000500000==1/100001大概就是%0。001``所以可以忽略项n

那么结果就是 O( P * (n*n/2) ) 2只是系数``所以转化一下``O( P * n*n )``这个是求总时间的``

那么复杂度当然就是 O(n*n)





呵呵谢谢了,写得很详细.


2007-10-07 10:10
快速回复:求循环次数和时间复杂度
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018059 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved