下列程序段的时间复杂度是()。

|nt sum =0;for(Int |=1;|<n;| *=2)

for ( |nt j= 0; j<|;j ++)

sum ++ ;

A.O(log₂n)

B.O(n)

C.O(nlog₂n)

D.O(n²)

[tag_link]

正确答案：B

当外层循环的变量 i 取不同值时，内层循环就执行多少次，因此总循环次数为 的所有取值之和。假设外层循环共执行 k 次，当 i = 1 , 2 , 4 , 8 , ⋯ , 2 k − 1 ( 2 k − 1 < n ≤ 2 k ) 时，内层循 环执行 i 次，因此总循环次数 T = 1 + 2 + 4 + 8 + ⋯ + 2 k − 1 = 2 k − 1 即 n < T < 2 n ，时间复杂度为 O ( n ) 。