[計算量をざっくり理解] ループを使う場合の計算量

for ループを使う場合の計算量について考えます。

\( O(n) \)

for ループの中に\( O(1) \)の処理がある場合は、\( O(n) \) になります。

for i=0 to N:
    # O(1) の処理

for ループの中に for ループがネストされ、その中に\( O(1) \)の処理がある場合は、\( O(n^2) \) になります。

for i=0 to N:
    for j=0 to N:
        # O(1) の処理

漸近的挙動を考えるので、例えば以下のように処理を減らしたとしても、計算量は \( O(n^2) \) のままです。

for i=0 to N:
    for j=0 to i:
        # O(1) の処理

一般的に、for ループの中に for ループが\(k-1\)個ネストされていて、その中に\( O(1) \)の処理がある場合は、\( O(n^k) \) になります。