算法分析，算法的时间复杂度

Question

m=1;
for(i=1;i<=n;i++){
    m=m*2;
    for(j=1;j<=m;j++){
        do something that is O(1)
    }
}

以上代码的时间复杂度将是什么？请告诉我如何解决这些问题。

- Ashok Naval

Answer 1

我更喜欢从内部向外看这些问题。去掉m，我们有：

for(i=1;i<=n;i++){
    for(j=1;j<=2^i;j++){
        do something that is O(1)
    }
}

或者：

for(i=1;i<=n;i++){
    O(2^i)
}

总体而言：sum_1^n O(2^i)=O(2^(n+1))=O(2^n)。

- Teepeemm

Answer 2

内部循环将迭代1次，然后2次，然后......，最后2的n次方次。所以我们有1 + 2 + 4 + ... + 2^n = 2^(n + 1) - 1 = O(2^n)内部循环迭代次数。

内部循环的每次迭代具有恒定的复杂度，因此summed_inner_loop_complexity = O(2^n)。

整个复杂度为O(2^n)。

- Ari

---

不可以。你可以乘以 n，或者获取内部循环复杂度的总和（更好），但这两种方法都会导致计数过多。答案应该是 O(2^n)。 - Teepeemm

我认为应该是O(2^n)，就像Teepeemm所解释的那样。 - Ashok Naval

Answer 3

正式而系统地，您可以使用Σ符号表示：

- Mohamed Ennahdi El Idrissi