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

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