Question

数据结构中算法的时间复杂度计算

1 分析下面算法，该算法的时间复杂度是____。

i=s=0;
while (s<n)
{ i++;
s+=i; //s=s+i
}

2 分析下面算法，该算法的时间复杂度是____。

i=1;
while (i<=n)
i=i*2;

书本给出的答案是：
1.根号N
2.log(N)

我不明白为什么？求解。。。。

Answer 1

1、s的增长序列为：1,2,3,4，……，所以循环loop次后s=1+2+3+……+loop，s=n时结束循环。
由:1+2+3+……+loop=n 得到： loop=O(sqrt(n));
2、循环loop次后， i=2^loop, 由i=n，得到： loop=log(n);

就是看循环执行了多少次，看执行多少步后i满足循环退出的条件。