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

Question

考虑以下 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;
}

问题是决定以下哪个最接近函数 return 的值 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 的答案是错误的？

Answer 1

这个问题很棘手 - 代码的 运行time 和 return 是有区别的价值是。

第一个循环的运行时间确实是 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 的值增加 1。这意味着在循环结束时，p 的值为 Θ(log n)。因此，下一个循环确实运行时间 O(log log n):

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

原因是，使用与上一节类似的推理，运行这个循环的时间是 Θ(log p)，并且由于 p = Θ(log n)，所以结束是 Θ(log log n).

但是，问题是而不是询问运行时间是多少。它询问 return 值 是什么。在每次迭代中，q 的值，即最终 returned，增加 Θ(log log n)，因为它在时间为 Θ(log log n) 的循环中每次迭代增加一次运行s n).这意味着 q 的净值为 Θ(n log log n)。因此，尽管算法 运行s 的时间为 O(n log n)，但它 returns 的值是 O(n log log n ).

希望对您有所帮助！

Answer 2

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

第一个for循环包含另外2个for循环，它们分别基于j和k的值。此外，j 从 n 减半，直到它大于 1。因此，p 将等于最大整数 (log n)。并且，k 加倍直到它等于 p --- 其中 p 已从上一个循环设置并且等于 [log n]，其中 [x] 等于 x 的最大整数。

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

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

Answer 3

我在这里看到的唯一错误是第二个循环：对于（j=n；j>1；j=j/2）你在评论中说：这个循环运行 Θ(Log Log n) 时间

在我看来，这个循环运行了 O(Log n) 次

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

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

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

Why does this loop return a value that's O(n log log n) and not O(n log n)?

loops

for-loop

time-complexity

nested-loops

asymptotic-complexity