求循环次数和时间复杂度 - C语言论坛

| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛 |

编程论坛 → 开发语言 → 『 C语言论坛』 → 求循环次数和时间复杂度

我的收件箱(0)

共有 1480 人关注过本帖

标题：求循环次数和时间复杂度

取消只看楼主加入收藏

zzsy04et138

等　级：新手上路
帖　子：113
专家分：0
注　册：2006-10-18

楼主

问题点数：0 回复次数：6

求循环次数和时间复杂度

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

zzsy04et138

等　级：新手上路
帖　子：113
专家分：0
注　册：2006-10-18

第 2 楼

得分:0

它说时间复杂度是0(n*n)

2007-10-07 09:12

zzsy04et138

等　级：新手上路
帖　子：113
专家分：0
注　册：2006-10-18

第 3 楼

得分: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

zzsy04et138

等　级：新手上路
帖　子：113
专家分：0
注　册：2006-10-18

第 4 楼

得分: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

zzsy04et138

等　级：新手上路
帖　子：113
专家分：0
注　册：2006-10-18

第 5 楼

得分: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

zzsy04et138

等　级：新手上路
帖　子：113
专家分：0
注　册：2006-10-18

第 6 楼

得分:0

以下是引用死了都要C在2007-10-7 10:10:06的发言：
意思就是先DO一下````

就是说要先进行初始化吗?

2007-10-07 10:21

zzsy04et138

等　级：新手上路
帖　子：113
专家分：0
注　册：2006-10-18

第 7 楼

得分:0

回复：（死了都要C）就是这个意思```还有你的程序有点...

呵呵,这个是考研题目...可能是题目出得有问题吧.

2007-10-07 12:06

快速回复：求循环次数和时间复杂度