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

count = 0;
for (k = 1; k <= n; k *= 2)
    for (j = 1; j <= n; j++)
        count++;

A.O(log₂n)

B.O(n)

C.O(nlog₂n)

D.O(n²)

[tag_link]

正确答案：C

内层循环条件 j ≤ n 与外层循环的变量无关，每次循环 j 自增 1, 每次内层循环都执行 n 次。外层循环条件为 k ≤ n , 增量定义为 k *= 2, 可知循环次数为 2 k ≤ n , 即 k ≤ l o g 2 ( n ) 。所以内层循环的时间复杂度是 O ( n ) , 外层循环的时间复杂度是 O ( l o g 2 n ) 。对于嵌套循环，根据乘法规则可知，该段程序的时间复杂度 T ( n ) = T 1 ( n ) T 2 ( n ) = O ( n ) O ( l o g 2 ( n )) = O ( n l o g 2 n ) , 选 C。