入れ子ループの実行回数
同じ n なのに、待ち時間が 100 倍違う
前回、1 重のループは n 回まわると数えました。ところが同じ n でも、書き方ひとつで回数は桁違いに変わります。n = 1000 のとき、1 重なら 1000 回で終わります。ループの中にもう 1 つループを入れると、100 万回です。体感で言えば、すぐ返ってくる画面と、開いたまま固まる画面の差になります。
この差はどこから来るのか。答えは単純で、入れ子にすると回数は足し算ではなく掛け算になる からです。
並べて書けば足し算、入れ子にすれば掛け算
まず、ループを 2 つ並べて書いた場合です。
Python
for m in members:
print(m)
for r in rooms:
print(r)members を全部見てから、rooms を全部見ます。3 人と 4 部屋なら 3 + 4 = 7 行です。片方が終わってからもう片方が始まるので、当然そうなります。
次に、片方をもう片方の中に入れます。
Python
sizes = ["S", "M", "L"]
colors = ["白", "黒"]
for s in sizes:
for c in colors:
print(s, c)出るのは 6 行です。S 白 S 黒 M 白 M 黒 L 白 L 黒 と、すべての組み合わせが並びます。外側が 1 つ進むあいだに、内側は最後まで一往復します。だから 3 × 2 = 6 です。
外側も内側も同じ n 件を見るなら、回数は n × n になります。これが O(n^2) の正体です。
n を 10 倍すると、待ち時間は 100 倍
O(n^2) の怖さは、増え方が加速するところにあります。n = 10 なら 100 回、n = 100 なら 1 万回、n = 1000 なら 100 万回、n = 10000 なら 1 億回。n を 10 倍するたびに、回数は 100 倍です。
Python
n = 10000
print(n * n) # 100000000
print(n * (n - 1) // 2) # 49995000内側の範囲を外側に合わせて短くしても、結論は変わりません。1 + 2 + ... + (n - 1) は上の式のとおり n^2 のおよそ半分です。半分になっても増え方は 2 乗のままなので、オーダーは O(n^2) のままです。定数倍は無視するという約束が、ここで効いてきます。
見分け方は簡単です。ループが縦に並んでいれば足し算、字下げが深くなっていれば掛け算です。字下げの深さが、そのまま指数になります。
要件
- 2 重 for ループ (外側 n 回・内側 n 回) で実行回数を数えること
- n <= 0 の場合は 0 を返すこと
- 戻り値は整数 (int) であること
入出力例
countNested(5) → 25
countNested(0) → 0
countNested(1) → 1
countNested(3) → 9
countNested(10) → 100
countNested(-2) → 0ヒント
