要过程！！！
简单点模拟一下每次循环里面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我
第一次执行完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我
温馨提示：答案为网友推荐，仅供参考
第1个回答 2011-11-18
设运行时间为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))
则显然循环是在做一个等差数列求和，当和大于等于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))
