下列函数的时间复杂度是()。int func(int n)(int i=0,sum=0;while (sum<n)sum+=++i;return i;A.O(log2n)B.O(n^1/2)C.O(n)D.O(nlog2n)
下列函数的时间复杂度是()。
int func(int n)(
int i=0,sum=0;
while (sum<n)sum+=++i;
return i;
A.O(log2n)
B.O(n^1/2)
C.O(n)
D.O(nlog2n)
题目解答
答案
根据给定的代码：
int func(int n) {
int i=0,sum=0;
while (sum<n) {
sum+=++i;
}
return i;
}
在代码中，循环的条件是 `sum<n`，并且在每次循环中 `sum` 的值会增加 `i`。我们可以观察到 `sum` 的初始值是 0，而每次循环中 `i` 的值会递增。当 `sum>=n` 时，循环停止，返回最后的 `i`。
假设最后一次循环时 `sum` 的值为 `k`，此时 `sum>=n`，但是 `sum` 与 `n` 是最接近的，所以我们可以得到 `k` 和 `n` 之间的关系：`k >= n` 且 `sum < n`。
根据等差数列求和公式，可以得知 `sum` 的近似值为 `(i+1)*i/2`。将这个式子中的 `sum` 替换为 `n`，可以得到 `(i+1)*i/2 >= n`。整理后可以得到 `i^2 + i - 2n >= 0`。
通过求解这个一元二次不等式，可以得到 `i >= (-1+√(1+8n))/2`。由于 `i` 是整数，所以最终取 `i = ceil((-1+√(1+8n))/2)`，其中 `ceil` 表示向上取整。
因此，循环的次数可以近似看作是 `i`，而 `i` 的大小与输入规模 `n` 有关。因此，时间复杂度的量级是 `O(sqrt(n))`。
综上所述，正确答案为B。
解析
考查要点：本题主要考查对循环时间复杂度的分析能力，需要根据循环条件和变量变化推导出循环次数与输入规模n的关系。
解题核心思路：
- 确定循环变量的变化规律：观察循环体内
i和sum的更新方式，发现sum是累加i的递增序列。 - 建立数学模型：将
sum的累加过程转化为等差数列求和公式，找到sum与n的关系式。 - 求解不等式：通过近似简化，推导出循环次数
i与n的渐近关系，从而确定时间复杂度。
破题关键点：
- 等差数列求和公式的应用：
sum = 1 + 2 + 3 + ... + i = i(i+1)/2。 - 忽略低次项：将二次方程简化为
i^2 ≈ 2n，得出i ≈ √(2n)，从而得到时间复杂度为O(√n)。
循环变量分析
- 初始状态：
i = 0,sum = 0。 - 循环条件：
sum < n。 - 循环体：每次循环先执行
i++，再将新的i值加到sum中。因此，sum的值是前i项的和，即sum = 1 + 2 + 3 + ... + i = i(i+1)/2。
建立关系式
当循环终止时，sum >= n，因此有：
$\frac{i(i+1)}{2} \geq n$
忽略低次项i，近似为：
$i^2 \approx 2n \quad \Rightarrow \quad i \approx \sqrt{2n}$
这表明循环次数i与√n成正比，因此时间复杂度为O(√n)。