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

Question

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

上述代码的时间复杂度是多少？请告诉我如何解决这些类型的问题。

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)。

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

Answer 3

形式上和有条理地，您可以使用 Sigma 表示法：