[同02题是母子题]下列程序段的时间复杂度是intsum=0;for(inti=1;iA. O(logn)B. 0(n)C. O(nlogn)D. O(n^2)

考查要点：本题主要考查嵌套循环的时间复杂度分析，特别是外层循环呈指数增长、内层循环呈线性增长的情况。

解题核心思路：

1. 外层循环分析：外层循环变量i从1开始，每次乘以2，直到i >= n，其执行次数为O(log n)。
2. 内层循环分析：内层循环在每次外层循环中执行i次，总次数为等比数列求和，结果为O(n)。
3. 整体复杂度：外层循环次数与内层循环总次数相乘，最终时间复杂度为O(n)。

破题关键点：

• 识别外层循环的指数增长特性，明确其执行次数为对数级别。
• 正确计算内层循环的总次数，利用等比数列求和公式得出总次数与n成线性关系。

外层循环分析

外层循环为for(int i=1; i < n; i *= 2)，每次i翻倍，执行次数为：
$\text{次数} = \lfloor \log_2 n \rfloor + 1 = O(\log n)$

内层循环分析

内层循环为for(int j=0; j < i; j++)，在第k次外层循环中，i = 2^{k-1}，内层循环执行i次。总次数为：
$\sum_{k=0}^{\log_2 n} 2^k = 2^{\log_2 n + 1} - 1 = 2n - 1 = O(n)$

整体时间复杂度

外层循环次数为O(log n)，但内层循环总次数为O(n)，因此整体时间复杂度为：
$O(\log n) \times O(1) + O(n) = O(n)$