题目
下列函数的时间复杂度是()。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。
解析
步骤 1：分析循环条件
在给定的代码中，循环的条件是 `sum < n`，并且在每次循环中 `sum` 的值会增加 `i`。`sum` 的初始值是 0，而每次循环中 `i` 的值会递增。当 `sum >= n` 时，循环停止，返回最后的 `i`。
步骤 2：确定循环次数
假设最后一次循环时 `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`。
步骤 3：求解一元二次不等式
通过求解这个一元二次不等式，可以得到 `i >= (-1+√(1+8n))/2`。由于 `i` 是整数，所以最终取 `i = ceil((-1+√(1+8n))/2)`，其中 `ceil` 表示向上取整。因此，循环的次数可以近似看作是 `i`，而 `i` 的大小与输入规模 `n` 有关。因此，时间复杂度的量级是 `O(sqrt(n))`。
在给定的代码中，循环的条件是 `sum < n`，并且在每次循环中 `sum` 的值会增加 `i`。`sum` 的初始值是 0，而每次循环中 `i` 的值会递增。当 `sum >= n` 时，循环停止，返回最后的 `i`。
步骤 2：确定循环次数
假设最后一次循环时 `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`。
步骤 3：求解一元二次不等式
通过求解这个一元二次不等式，可以得到 `i >= (-1+√(1+8n))/2`。由于 `i` 是整数，所以最终取 `i = ceil((-1+√(1+8n))/2)`，其中 `ceil` 表示向上取整。因此，循环的次数可以近似看作是 `i`，而 `i` 的大小与输入规模 `n` 有关。因此，时间复杂度的量级是 `O(sqrt(n))`。