考虑以下C函数:
问题是决定以下哪个最接近函数
(A) n^3 (B) n (logn)^2 (C) nlogn (D) nlog(logn)
这是给出的解释:
int fun1 (int n)
{
int i, j, k, p, q = 0;
for (i = 1; i<n; ++i)
{
p = 0;
for (j=n; j>1; j=j/2)
++p;
for (k=1; k<p; k=k*2)
++q;
}
return q;
}
问题是决定以下哪个最接近函数
fun1
的返回值?(A) n^3 (B) n (logn)^2 (C) nlogn (D) nlog(logn)
这是给出的解释:
int fun1 (int n)
{
int i, j, k, p, q = 0;
// This loop runs T(n) time
for (i = 1; i < n; ++i)
{
p = 0;
// This loop runs T(Log Log n) time
for (j=n; j > 1; j=j/2)
++p;
// This loop runs T(Log Log n) time
for (k=1; k < p; k=k*2)
++q;
}
return q;
}
但是,如果循环变量被除以/乘以一个常量量,则循环的时间复杂度被认为是O(Logn)。
for (int i = 1; i <=n; i *= c) {
// some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
// some O(1) expressions
}
但是提到内部循环每个需要 Θ(Log Log n) 的时间,有人能解释一下为什么 ar 是错误的答案吗?