题16

题16

题目

[!error]+
Q:【2022 统考真题】下列程序段的时间复杂度是 ( ).

int sum = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

A.O(logn)
B.O(n)
C.O(nlogn)
D.O(n^2)

分析

[!NOTE]+
A:外层执行logn次，内层是1+2+4+8+…+n
最后就是

解

[!done]+
B
对于单层循环如 for (j = 0; j <= i; j++) sum++; ,可以直接数出执行次数为 i ,因此可将多层循环转换成多个并列的单层循环,且列出每个单层循环如下 (假设 t 为循环变量的幂次):
进入外层循环的条件是 i < n ,当循环结束时,循环变量的幂次 t 满足 2^t < n <= 2^(t + 1) 。总执行次数 T = 1 + 2^1 + 2^2 + ... + 2^t = 2^(t + 1) - 1 ,即 n - 1 <= T 且 T < 2n - 1 ,所以时间复杂度为 O(n) 。