Question

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

1 分析下面算法，该算法的时间复杂度是____。 i=s=0; while (s { 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满足循环退出的条件。