15问答网 > 下面程序段的时间复杂度是 i=s=0; while(s<n) { i++; s+=i; }

下面程序段的时间复杂度是 i=s=0; while(s<n) { i++; s+=i; }

要过程！！！

2025-04-13 16:33:11

推荐回答（2个）

回答1：

简单点模拟一下每次循环里面s的值:

第一次执行完s+=i
s == 1
第二次s == 3 == 1+2
第三次s == 6 == 1+2+3
第四次s == 10 == 1+2+3+4

第k次 1+2+3+4+...+k == k*(k+1)/2

那么当k*(k+1)/2 >=n 的时候停止
也就是k == (根号(8*n+1) - 1 ) /2

关于n的表达式是根号的, 所以复杂度是根号n

还有不懂得欢迎继续hi我

回答2：

设运行时间为T(n)，循环次数为k，则T(n)=k
则显然循环是在做一个等差数列求和，当和大于等于n时停止，即k(k+1)/2>=n时停止
解得k=ceil((sqrt(8n+1)-1)/2)<=(sqrt(8n+1)-1)/2+1
即T(n)=k<=sqrt(2n+1/4)+1<=c*sqrt(n) （取c=2即成立）
故时间复杂度为T(n)=O(sqrt(n))