神马品牌网耳鸣一天后头晕恶心:看过数据结构的兄台们过来看看哦！
来源：百度文库 编辑：神马品牌网 时间：2024/04/30 11:49:55
请写出下面程序的时间复杂性：
i:=0;s:=0;
while s<n do
begin
i:=i+1;
s:=s+i
end;
A.O(n的平方根) B（2n的平方根） C（n） D（n的平方）
在下知道这个程序是用来计算从1加到几恰恰刚好大于等于n。经过对n取几个特殊值，发现while语句的执行次数在n的平方根附近，故答案为A。但如何从理论上证明这一结论的正确性，尚请诸位大侠指教！多谢！！
i:=0;s:=0;
while s<n do
begin
i:=i+1;
s:=s+i
end;
A.O(n的平方根) B（2n的平方根） C（n） D（n的平方）
在下知道这个程序是用来计算从1加到几恰恰刚好大于等于n。经过对n取几个特殊值，发现while语句的执行次数在n的平方根附近，故答案为A。但如何从理论上证明这一结论的正确性，尚请诸位大侠指教！多谢！！
第1次，s = 1
第2次，s = s + 2 = 1 + 2
第3次，s = s + 3 = 1 + 2 + 3
……
第k次，s = s + k = 1 + 2 + 3 + …… + k = k*(k+1)/2
假设这是最后一次循环，那么满足条件
k*(k+1)/2 >= n
当n和k很大时，因为k*(k+1)/2这时正好超过n，所以和n相差不大
近似为k*k/2 = n
k = 根号(2n)
去掉常数根号2，它的时间复杂度就为O(n的平方根)。
ps：这个题目其实可以投机，因为程序的时间复杂度都是O(*)之类的表达式，不用计算就知道BCD都是错的。
siline的最后一句正典.
复杂度一般只用n的常数项为1的表示。siline的答案很全面了。