为什么此循环返回的值为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;
}

问题是要确定以下哪个最接近函数的返回值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

这个问题很棘手- 代码的运行时间和返回值之间是有区别的。

第一个循环的运行时确实为O（log n），而不是O（log log n）。我在这里转载了它：

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

在每次迭代中，j的值都会降低两倍。这意味着，该循环终止所需的步数由k的最小值，使得n / 2的给定^ķ ≤1.求解，我们看到，K =为O（log ₂ N）。

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

对于（k = 1; k <p; k = k * 2）++ q; }

其原因在于，使用与上一节类似的推理，此循环的运行时间为Θ（log p），由于p =Θ（log n），因此最终为Θ（log log n）。

但是，问题不在于运行时间是什么。它在询问返回值是什么。在每次迭代中，最终返回的q的值将增加Θ（log log n），因为在时间Θ（log log n）中运行的循环的每次迭代都将q的值增加一次。这意味着q的净值为Θ（n log log n）。因此，尽管该算法在时间O（n log n）上运行，但它返回的值为O（n log log n）。

希望这可以帮助！