这段代码复杂度为 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

首先看外循环。您可以看到它一直迭代直到 i < 1 或 i = 0。因此，外循环执行 i = N、N/2、N/4 … N/2^k 的值（执行 k 个次)

N/2^k < 1

N<2^k

k>log(N)

所以，外层循环执行了logN次。

现在，看看内循环。首先执行N次，然后执行N/2次，然后执行N/4次，直到执行到1。基本上执行logN次。

因此，时间复杂度将为 N + N/2 + … logN 项。

按几何级数： a=N, r= 1/2, n= logn（记住 logn 的底数是 2）另外，使用 a^logb = b^loga 和 log2 是 1.

N((1- (1/2)^logN)/(1-1/2)) = 2N(1-(1^logN)/(N^log2)) = 2N(1-1 /N)=2(N-1) = 2*N = O(N)

所以，时间复杂度是O(N)

Answer 2

这很有趣。 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) 的结果。这是上限。

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

内循环基本上是将外循环变量的所有值相加i
循环变量 i 遵循 n、n/2、n/4、...、1、0[ 的模式=66=]

让我们假设n = 2^k, k ∈ ℕ, k > 0，即n是2的幂。那么 n/2 = 2^(k-1), n/4 = 2^(k-2), ... 为了从这个假设中推广，如果 n 不是 2 的幂，我们将它设置为2 的下一个更小的幂。事实上，这是一个精确的估计。我将关于为什么的推理留作 reader.

的练习

well-known 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).

Answer 3

线性 O(n)

总成本 = n（第一次外循环迭代）+ n/2（第二次外循环迭代）+ n/4（第三次）+ ... 等总计 log(n) 次迭代.该总和以 2n 为界（a geometric series 的总和，其中 a = n，r = 1/2）。

这段代码复杂度为 O(log^2(n)) 吗？

Has this snippet O(log^2(n)) complexity?

java

complexity-theory

big-o

function