题目
[同02题是母子题]下列程序段[1]的时间复杂度是intsum=0;for(inti=1;i< n;i^ ( * ) =2)for(intj=0;j< i;j+ +)sum+ +; A. O(logn)B. 0(n)C. O(nlogn)D. O(n^2)
$$ [同02题是母子题]下列程序段[1]的时间复杂度是intsum=0;for(inti=1;i< n;i^ { * }\ \ =2)for(intj=0;j< i;j+ +)sum+ +; $$
- A. O(logn)
- B. 0(n)
- C. O(nlogn)
- D. $$ O(n^2) $$
题目解答
答案
B
解析
步骤 1：分析外层循环
外层循环的条件是 `i < n`，并且每次循环 `i` 的值乘以 2。因此，外层循环的次数是 `log_2(n)`，因为每次循环 `i` 的值翻倍，直到 `i` 达到或超过 `n`。
步骤 2：分析内层循环
内层循环的条件是 `j < i`，并且每次循环 `j` 的值加 1。因此，内层循环的次数是 `i`。由于外层循环每次 `i` 的值翻倍，内层循环的次数分别为 `1, 2, 4, 8, ...`，直到 `i` 达到或超过 `n`。
步骤 3：计算总的时间复杂度
外层循环的次数是 `log_2(n)`，内层循环的次数是 `1, 2, 4, 8, ...`，直到 `i` 达到或超过 `n`。因此，总的时间复杂度是 `1 + 2 + 4 + 8 + ... + n`，这是一个等比数列的求和，其和为 `2n - 1`。因此，总的时间复杂度是 `O(n)`。
外层循环的条件是 `i < n`，并且每次循环 `i` 的值乘以 2。因此，外层循环的次数是 `log_2(n)`，因为每次循环 `i` 的值翻倍，直到 `i` 达到或超过 `n`。
步骤 2：分析内层循环
内层循环的条件是 `j < i`，并且每次循环 `j` 的值加 1。因此，内层循环的次数是 `i`。由于外层循环每次 `i` 的值翻倍，内层循环的次数分别为 `1, 2, 4, 8, ...`，直到 `i` 达到或超过 `n`。
步骤 3：计算总的时间复杂度
外层循环的次数是 `log_2(n)`，内层循环的次数是 `1, 2, 4, 8, ...`，直到 `i` 达到或超过 `n`。因此，总的时间复杂度是 `1 + 2 + 4 + 8 + ... + n`，这是一个等比数列的求和，其和为 `2n - 1`。因此，总的时间复杂度是 `O(n)`。