✏️ 纠错
第 190 题 / 共 201 题
14. 下面 count_triple 函数的时间复杂度为()。
int gcd(int m, int n) {
if (n == 0)
return m;
return gcd(n, m % n);
}
int count_triple(int n) {
int cnt = 0;
for (int v = 1; v + v + v <= n; v++)
for (int u = v; u + u + v <= n; u += 2) {
int a = u + v;
int b = u - v;
int c = u * 2;
cnt += n / (a + b + c);
}
return cnt;
}
int gcd(int m, int n) {
if (n == 0)
return m;
return gcd(n, m % n);
}
int count_triple(int n) {
int cnt = 0;
for (int v = 1; v + v + v <= n; v++)
for (int u = v; u + u + v <= n; u += 2) {
int a = u + v;
int b = u - v;
int c = u * 2;
cnt += n / (a + b + c);
}
return cnt;
}
你真棒！
📝 题目解析
答案：C
知识点：多重循环与GCD的时间复杂度
解析：外层循环v的范围为O(√n)，内层循环u的范围为O(√n)，总循环次数为O(n)；GCD的时间复杂度为O(log n)，因此总复杂度为O(nlogn)。
外层循环的时间复杂度是 O (√n)，内层循环的时间复杂度也是 O (√n)。gcd（最大公约数）算法的时间复杂度为 O (log n)。将三者的时间复杂度相乘，得到总时间复杂度为 O (√n * √n * log n)，计算后结果为 O (n log n)。
知识点：多重循环与GCD的时间复杂度
解析：外层循环v的范围为O(√n)，内层循环u的范围为O(√n)，总循环次数为O(n)；GCD的时间复杂度为O(log n)，因此总复杂度为O(nlogn)。
外层循环的时间复杂度是 O (√n)，内层循环的时间复杂度也是 O (√n)。gcd（最大公约数）算法的时间复杂度为 O (log n)。将三者的时间复杂度相乘，得到总时间复杂度为 O (√n * √n * log n)，计算后结果为 O (n log n)。