✏️ 纠错
第 189 题 / 共 201 题
13. 下面 init_sieve 函数的时间复杂度为()。
int sieve[100] = {0};
void init_sieve(int n) {
for (int i = 1; i <= n; i++)
sieve[i] = 1;
for (int i = 2; i <= n; i++)
for (int j = i; j <= n; j += i)
sieve[j]--;
}
int sieve[100] = {0};
void init_sieve(int n) {
for (int i = 1; i <= n; i++)
sieve[i] = 1;
for (int i = 2; i <= n; i++)
for (int j = i; j <= n; j += i)
sieve[j]--;
}
你真棒！
📝 题目解析
答案：C
知识点：嵌套循环的时间复杂度分析
解析：外层循环i从2到n，内层循环j的执行次数为n/i，总次数为n/2 + n/3 + ... + n/n ≈ n log n，因此时间复杂度为O(nlogn)。
第二个 for 的循环次数为 n/2 + n/3 + n/4 + … + n/n = n (1/2 + 1/3 + … + 1/n)，其中 (1/2 + 1/3 + … + 1/n) 为调和级数，时间复杂度为 O (log n)，总时间复杂度为 O (n log n)。
知识点：嵌套循环的时间复杂度分析
解析：外层循环i从2到n，内层循环j的执行次数为n/i，总次数为n/2 + n/3 + ... + n/n ≈ n log n，因此时间复杂度为O(nlogn)。
第二个 for 的循环次数为 n/2 + n/3 + n/4 + … + n/n = n (1/2 + 1/3 + … + 1/n)，其中 (1/2 + 1/3 + … + 1/n) 为调和级数，时间复杂度为 O (log n)，总时间复杂度为 O (n log n)。