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)、内部ループの反復があります。

内部ループの 1 回の繰り返しの複雑さは一定であるため、summed_inner_loop_complexity = O(2^n).

全体の複雑さはO(2^n)です。

Answer 3

形式的かつ体系的に、シグマ表記を使用できます。