java - 这段代码复杂度为 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) 的假设是错误的。 Henry gave a good reductio ad absurdum why it cannot be log^2(n) in the comments :

• 我们可以看到，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，即 n 是 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)。