计算机考研科目数据结构中题型求时间复杂度，i=1；while（i<=n）i=i*2;

Question

如题所述

Answer 1

分析过程：

i 是否执行循环 i
------------------------------
1<n 是 2 = 2(1) 表示2的1次方，以下类同
2<n 是 4 = 2(2)
4<n 是 8 = 2(3)
8<n 是 16= 2(4)
...
2(k-1)<n 是 = 2(k) 最后一次

则有2(k) <= n，取“=”，有
2(k) = n，
得k = log(2)n 表示以2为底n的对数。

去掉较低次方和最高次方的系数，得
时间复杂度 = log(n)

Answer 2

i 是否执行循环 i
1<n 是 2 = 2(1) 表示2的1次方，以下类同
2<n 是 4 = 2(2)
4<n 是 8 = 2(3)
8<n 是 16= 2(4)
...
2(k-1)<n 是 = 2(k) 最后一次

则有2(k) <= n，取“=”，有2(k) = n，得k = log(2)n 表示以2为底n的对数。

去掉较低次方和最高次方的系数，得时间复杂度 = log(n)