这个片段有 O(log^2(n)) 复杂度吗？

Question

如果不是，女巫复杂性会是什么？谢谢：

    public static int f(int n, int x) {
        for (int i = n; i > 0; i /= 2) {
            for (int j = 0; j < i; j++) {
                x += j; // Assume, this operation costs 1.
            }
        }
        return x;
    }

Answer 1

这是一个有趣的。的假设log^2(n)是错误的。亨利给出了一个很好的简化广告荒谬的解释，为什么它不能出现log^2(n)在评论中：

• 我们可以看到，O(log^2(n)) ? O(n)。
• 内循环的第一次迭代需要O(n).
• 因为O(log^2(n)) ? O(n)，假设一定是错误的，因为仅第一次迭代就是? O(n)。

这也为我们提供了算法的下限：由于算法的第一次迭代是? O(n)，那么整个算法至少需要?(n)。

现在让我们开始估算执行时间。通常，第一种方法是分别估计内循环和外循环，然后将它们相乘。显然，外循环具有复杂性log(n)。然而，估计内部循环并非易事。所以我们可以用n（这是一个高估）来估计它并得到 的结果n log(n)。这是一个上限。

为了得到更精确的估计，让我们做两个观察：

1. 内循环基本上将外循环变量的所有值相加 i
2. 循环变量i遵循n, n/2, n/4, ..., 1,0

让我们假设n = 2^k, k ? ?, k > 0，ien是 的幂2。然后n/2= 2^(k-1), n/4 = 2^(k-2), ... 从这个假设概括，如果n不是 的幂2，我们将它设置为 的下一个较小的幂2。事实上，这是一个准确的估计。我将原因的推理留给读者作为练习。

众所周知的事实是2^k + 2^(k-1) + 2^(k-2) + ... + 1 (+ 0) =sum_(i=0)^k 2^i = 2^(k+1) - 1。由于我们的输入是n = 2^k，我们知道2^(k+1)= 2 * 2^k = 2 * n ? O(n)。该算法的运行时复杂度实际上是?(n)，即这是一个上限和一个下限。它也是一个下限，因为我们所做的估计是准确的。或者，我们可以使用我们对算法存在的观察，? ?(n)从而以这种方式得出?(n)。