时间复杂度 — 编程爱好者社区

主题：时间复杂度

quhailiang1984 [专家分：1720] 发布于 2010-03-06 13:23:00

高手帮我看一下下面这个算法的时间复杂度是多少，用大O表示，并解释一下原因！答案和我的不一样。
[code=c]
int fun(int n)
{
   int i=1,s=1;
   while(s<n)
      s+=++i;
   return i;
}
[/code]

本来这个是数据结构的问题，只不过数据结构板块太冷清了就发在这边了！呵呵！

本帖地址： http://bbs.pfan.cn/post/317808.html

回复列表（共8个回复）

沙发

雪光风剑 [专家分：27190] 发布于 2010-03-06 17:28:00

好歹我也是数据结构板斧……你这么说让我太伤心了……

板凳

quhailiang1984 [专家分：1720] 发布于 2010-03-06 17:31:00

先把这个问题解决了再说其他的！呵呵！

3 楼

雪光风剑 [专家分：27190] 发布于 2010-03-06 17:47:00

说一下你想的结果和答案也许我能给你解释，时间复杂度这东西好久没用过了

4 楼

quhailiang1984 [专家分：1720] 发布于 2010-03-06 18:05:00

答案用大O表示为：O(n^(1/2))；我理解不了这个答案，为什么会是根号下n呢？

5 楼

雪光风剑 [专家分：27190] 发布于 2010-03-06 18:32:00

s是关于i的平方的函数，计算的最后s跟i的关系满足s=i(i+1)/2
这个值小于等于n
算法的时间复杂度=循环次数不大于根号n。明白了没

6 楼

elst5523183 [专家分：210] 发布于 2010-03-06 23:41:00

我也看懂了......
s最后等于1+2+3+4+5+...+i
=i(i+1)/2
n=i(i+1)/2 ,i等于多少,就相当于循环次数多少...
i=[-1 +/- (1+8n)^1/2]/2
O(n^1/2)

7 楼

yansheng [专家分：1530] 发布于 2010-03-07 09:46:00

学习学习！！

8 楼

雪光风剑 [专家分：27190] 发布于 2010-03-07 10:46:00

[quote]我也看懂了......
s最后等于1+2+3+4+5+...+i
=i(i+1)/2
n=i(i+1)/2 ,i等于多少,就相当于循环次数多少...
i=[-1 +/- (1+8n)^1/2]/2
O(n^1/2)[/quote]
不用算这么复杂，只看最高次就可以了

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：时间复杂度

回复列表（共8个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：时间复杂度

回复列表 （共8个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共8个回复）