一个关于时间复杂度的问题 (求解)

wangkang · 发表于 07-8-19 09:53:54

i=s=0;
         while(s<n)
         {
                  i++;
                  s+=i;
         }
         请问这段程序的时间复杂度  我算的是O(根号n)
            我的解答过程是:假设执行N次,则有1+2+3+......+N<n 则有 N(N+1)除以2<n, 得到N<O(根号n)
         习题上的答案是O(n)    我不知道是为什么    请求高手解答谢谢

dreamserver · 发表于 07-8-19 10:29:03

就是O（N）次，因为i=s=0,循环当中s 始终等于0压！

ctguyg · 发表于 07-8-19 11:55:34

ding yi xia

wangkang · 发表于 07-8-19 21:50:36

大哥能不能说明白点我还是认为是O(根号n)

sgh307 · 发表于 07-8-25 21:16:50

解的没错是根号N

n1m234 · 发表于 07-8-25 21:19:31

你看清楚，一般对于时间复杂度以几次方为基础的，就是以 n n^2 n^3 没有以根号的．所以至少都是Ｎ

libin_421 · 发表于 07-8-25 23:21:03

我的看法：
对于时间复杂度，其是针对算法的，不是针对具体的语句，因此只需选取最大的一个语句频度就行了，因此就是while判断的n次，我没看懂你的1+2+......+N是怎么来的。故时间复杂度为O(n)

		自动登录	找回密码
密码			注册