数据结构的题目（c语言的）

答案:5 悬赏:10 手机版

解决时间 2021-05-17 20:55

提问者网友：原来太熟悉了会陌生
2021-05-16 21:15

求下面程序的时间复杂性的量级为（）

int prime(int n)
{
int i=1;
int x=(int)sqrt(n);
while(++i<=x)
if(n%i==0)break;
if(i>x)return 1;
else return 0;
}

A：O（1） B：O（log2n） C: O(n) D: O(n的平方根)

要解释答案啊！

最佳答案

五星知识达人网友：梦中风几里
2021-05-16 22:13

应该是D吧，while会最多运行n的平方根-1次，
比如n=9，x=3；则第一次n%i是9%2不为零，第二次9%3为零，运行了9的平方根-1次
再如n=81，x=9，第一次n%i是81%2不为零，第二次81%3为零，运行了2次
然而n=49，x=7，则第一次n%i是49%2不为零，第二次49%3不为零……第6次49%7为零，运行了49的平方根-1次
由此可见，while最多会允许n的平方根-1次

全部回答

1楼网友：舊物识亽
2021-05-17 02:39

画一个X轴和Y轴模拟一个N=4,就可以看出,描的点是一条零为顶点的斜线 ,得出的就是N的复杂度了

所以,方法就是画X轴和Y轴,描几个点连一下线,就可以推出时间复杂度.

2楼网友：枭雄戏美人
2021-05-17 01:05

因为肯定一次过终止循环

3楼网友：逐風
2021-05-17 00:17

算法复杂度量级时间推理得出

首先这里While循环就证明，而条件是活得。自然不是Ａ

你自己设定一个数字，看要走多少步，再看结果的规律！

4楼网友：躲不过心动
2021-05-16 22:45

好像是N

不过我也刚学的，不太懂，感觉

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！