Question

分析下面算法（程序段）给出最大语句频度 ，该算法的时间复杂度是__ __。

分析下面算法（程序段）给出最大语句频度 ，该算法的时间复杂度是__ __。
i=s=0;
while (s<n)
{ i++;
s+=i; //s=s+i
}

Answer 1

分析每一次循环可以发现，当循环执行10次后x>100，y方才减1，此时x被复原为91；
如此下去，由于每执行10次循环才使y减1，所以循环体执行100*10次，也就是说if语句判断执行了1000次（但里面的y--执行了100次）。至于时间复杂度，你现在数据都给定值了那不就是o(1)吗……如果x、y没给初值，则粗略地说应该为o(y)（或者说是o(10y)）。

Answer 2

一楼的回答是SB，希望那些没好好学算法的人就别在这里祸害学生。
时间复杂度很好算，实际上它是一个1+2+3.....+m=n的过程。等于n后循环终止。m好算吧？m=根号下（2n+1/4）-1/2.
所以时间复杂度是O(根号n).

Answer 3

这段程序是错的。.
正确的应该是:
i=s=0;
while (s<n)
do{
i++;
s+=i; //s=s+i
}
复杂度是n 只有一次循环 没有嵌套循环.

Answer 4

s=1+2+3+.....+i=【（1+i）i/2】<n
所以时间复杂度是o（√n）
根号不好打 反正就是根号下的n