入れ子ループの実行回数

同じ n でも、回数は変わる

前回、1重のループはn回まわると数えました。nが1000なら1000回です。ところが、その中で毎回もう1000回まわすと、合計は100万回になります。同じ件数でも、すぐ返ってくる画面と長く待つ画面の差につながります。

1回が軽くても、回数は1000倍になっています。入れ子では、内側が外側の1回ごとに最後までまわるため、足し算ではなく掛け算で数えます。

並べれば足し算、入れ子なら掛け算

3人の名前を出し、その後に4部屋の名前を出すなら、出力は 3 + 4 = 7 行です。片方が終わってからもう片方が始まります。

次は、サイズと色の全組み合わせを出す例です。

sizes = ["S", "M", "L"]
colors = ["白", "黒"]
for s in sizes:
    for c in colors:
        print(s, c)
# S 白、S 黒、M 白、M 黒、L 白、L 黒の6行

外側のサイズが1つ進むたびに、内側は白と黒の2回動きます。だから 3 × 2 = 6 行です。内側の1行が何回実行されるかに注目します。

外側も内側もn件なら、回数は n × n、つまり O(n^2) です。一方、内側が常に2色なら2n回なので O(n) です。入れ子という形だけでは決まりません。

n を 10 倍すると、n の2乗は 100 倍

同じn同士を掛けると、件数を10倍にするたび回数は100倍になります。全組み合わせを画面に出す処理では、データが増えたときの負担を先に見積もる必要があります。

内側を短くする場合もあります。n人から異なる2人の組を重複なく選ぶなら、回数は (n - 1) + (n - 2) + … + 1 = n × (n - 1) / 2 です。全組み合わせのおよそ半分でも、増え方は O(n^2) のままです。

例題で確かめる

8人の参加者それぞれに5部屋の候補を表示します。1人につき5回なので 8 × 5 = 40 回です。人と部屋を別々に一覧表示するだけなら 8 + 5 = 13 回です。同じデータでも、「各人に全候補を出す」のか「別々に出す」のかで、数え方が変わります。