为什么这个循环返回的值是O(n log log n)而不是O(n log n)？

Question

为什么这个循环返回的值是O(n log log n)而不是O(n log n)？

loopsfor-looptime-complexitynested-loopsasymptotic-complexity

4

考虑以下C函数：

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 是错误的答案吗？

- coder101

3个回答

1

答案是(D) O(n * log(log n))。原因如下：

第一个for循环包含另外两个for循环，这两个循环基于j和k的值。同时，j从n开始除以2，直到大于1为止。因此，p将等于最大整数(log n)。而k则会翻倍，直到它等于p——其中p已经在之前的循环中被设置，并且将等于[log n]，其中[x]等于x的最大整数。

因此，第三个循环将运行log(log n)次，因此q的值将为log(log n)。因此，内部循环都是外部for循环的一部分，而外部for循环将运行n次。

q的近似值= n*log(log n) = O(n log(log n))。

- Am_I_Helpful

1

仔细重新阅读问题 - 它询问的是返回值而不是运行时间。我第一次也犯了同样的错误。 - templatetypedef

@templatetypedef-已经添加了答案，但是可能太晚了。 :( - Am_I_Helpful

这是为了尝试帮助我 :) - coder101

@coder101-哦，我以为templatetypedef点了赞。不管怎样，谢谢。 :) - Am_I_Helpful

兄弟，你能不能也看一下这个问题啊 :) https://dev59.com/n4vda4cB1Zd3GeqPfuzp - coder101

1

我看到这里唯一的问题在于第二个循环： for (j=n; j>1; j=j/2) 你在注释中说：这个循环运行Θ(Log Log n)次 据我观察，这个循环运行O(Log n)次

第一个和第三个循环的运行时间是正确的（O(n)和O(Log Log n)）。

编辑：我同意之前的回答。我没有注意到问题是关于返回值，而不是运行时间！

- A.S.H

兄弟，你能不能也看一下这个问题啊 :) https://dev59.com/n4vda4cB1Zd3GeqPfuzp - coder101

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

这个问题有点难 - 代码的运行时间和返回值之间存在差异。

第一个循环的运行时间确实是O(log n)，而不是O(log log n)。我在此重新打印它：

p = 0;
for (j=n; j > 1; j=j/2)
  ++p;

在每次迭代中，j的值都会减少一半。这意味着此循环终止所需的步骤数由k的最小值给出，使得n / 2^k ≤ 1。解决后，我们可以看到k = O(log₂ n)。

注意，此循环的每次迭代都会将p的值增加一。这意味着在循环结束时，p的值为Θ(log n)。因此，下一个循环确实在O(log log n)时间内运行：

for (k=1; k < p; k=k*2) ++q; }

原因是，使用类似于上一节的推理，此循环的运行时间为Θ(log p)，而p = Θ(log n)，因此结果为Θ(log log n)。

然而，问题并不是在问运行时间，而是在问返回值。在每次迭代中，最终返回的q的值会增加Θ(log log n)，因为它是在运行时间为Θ(log log n)的循环的每次迭代中增加一次。这意味着q的净值为Θ(n log log n)。因此，尽管该算法的运行时间为O(n log n)，但它返回的值为O(n log log n)。

希望这有所帮助！