这个代码段是否具有O(log ^ 2(n))的复杂性? [英] Has this snippet O(log^2(n)) complexity?

问题描述

如果没有的话，女巫的复杂性会是什么?谢谢:

If not, witch complexity it would be? Thanks:

    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;
    }

推荐答案

这很有趣. log^2(n)的假设是错误的. Henry很好地还原了为什么不能在评论中log^2(n) :

This is an interesting one. The assumption of log^2(n) is wrong. Henry gave a good reductio ad absurdum why it cannot be log^2(n) in the comments:

• 我们可以看到， .
• 内部循环的第一次迭代使用O(n).
• 自O(log^2(n)) ⊊ O(n)起，该假设必定是错误的，因为仅第一个迭代就是∈ O(n).

• We can see that, O(log^2(n)) ⊊ O(n).
• the first iteration of the inner loop takes O(n).
• Since O(log^2(n)) ⊊ O(n), the assumption must be wrong because the first iteration alone is ∈ O(n).

这也为我们提供了算法的下限:由于算法的第一个迭代是∈ O(n)，因此整个算法至少需要Ω(n).

This also provides us with a lower bound for the algorithm: Since the first iteration of the algorithm is ∈ O(n), then whole algorithm takes at least Ω(n).

现在让我们来估计执行时间.通常，第一种方法是分别估计内部和外部循环并将它们相乘.显然，外循环具有复杂度log(n).但是，估计内部循环并非易事.因此，我们可以使用n进行估算(这是高估了)，并得到n log(n)的结果.这是一个上限.

Now let us get to estimating the execution time. Normally, the first approach is to estimate the inner and outer loop separately and multiplying them together. Clearly, the outer loop has complexity log(n). Estimating the inner loop, however, is not trivial. So we can estimate it with n (which is an overestimation) and get a result of n log(n). This is an upper bound.

为了获得更精确的估计，让我们进行两个观察:

To get a more precise estimation, let us make two observations:

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

1. The inner loop basically adds up all values of outer loop variable i
2. Loop variable i follows the pattern of 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幂.实际上，这是一个精确的估计.我将推理的理由留给读者.

Let us assume that n = 2^k, k ∈ ℕ, k > 0, i.e. n is a power of 2. Then n/2 = 2^(k-1), n/4 = 2^(k-2), ... To generalize from this assumtion, if n is not a power of 2, we set it to the next smaller power of 2. This is, in fact, an exact estimation. I leave the reasoning as to why as an exercise for the reader.

一个众所周知的事实是2^k + 2^(k-1) + 2^(k-2) + ... + 1 (+ 0) =

It is a well-known fact that 2^k + 2^(k-1) + 2^(k-2) + ... + 1 (+ 0) =sum_(i=0)^k 2^i = 2^(k+1) - 1. Since our input is n = 2^k, we know that 2^(k+1)= 2 * 2^k = 2 * n ∈ O(n). The algorithm's runtime complexity is, in fact, Θ(n), i.e. this is an upper and a lower bound. It is also a lower bound since the estimation we made is exact. Alternatively, we can use our observation of the Algorithm being ∈ Ω(n) and thus arrive this way at Θ(n).

这篇关于这个代码段是否具有O(log ^ 2(n))的复杂性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！