英文:
Has this snippet O(log^2(n)) complexity?
问题
如果不是的话，它将是哪种复杂度？谢谢：```java
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; // 假设这个操作花费1。
}
}
return x;
}
<details>
<summary>英文:</summary>
If not, witch complexity it would be? Thanks:
```java
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;
}
答案1
得分: 6
这是一个有趣的问题。log^2(n) 的假设是错误的。Henry 在评论中提供了一个很好的反证法，解释为什么它不能是 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的模式。
假设 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)。
英文:
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:
- 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).
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).
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:
- The inner loop basically adds up all values of outer loop variable
i - Loop variable
ifollows the pattern ofn,n/2,n/4, ...,1,0
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.
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).
答案2
得分: 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)。
英文:
First of all, look at the outer loop. You can see it iterates until i < 1 or i = 0. So, outer loop executes for values for i = N, N/2, N/4 … N/2^k (executing k number of times)
N/2^k < 1
N<2^k
k>log(N)
so, outer loop executes logN times.
Now, looking at inner loop. First of all, it executes for N times, then N/2 times then N/4 times until it reaches 1. Basically, executing logN times.
So, time complexity will be N + N/2 + … logN terms.
By Geometric progression:
a=N, r= 1/2, n= logn (Remember logn has base 2)
Also, using a^logb = b^loga and log2 is 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)
So, time complexity is O(N)
答案3
得分: 0
线性 O(n)
总成本 = n（第一个外部循环迭代）+ n/2（第二个外部循环迭代）+ n/4（第三个）+ ... 以此类推，总共 log(n) 次迭代。这个总和受到 2n 的限制（等比数列之和，a = n，r = 1/2）。
英文:
Linear O(n)
Total cost = n (first outer loop iteration) + n/2 (second outer loop iteration) + n/4 (third) + ... etc to a total of log(n) iterations. This sum is bounded by 2n (sum of a geometric series with a = n, r = 1/2).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论