入れ子ループの実行回数｜コードで実践

入れ子ループの実行回数

このレッスンで分かること

この差は、データ量が増えると劇的に効いてきます

外側が i = 0..n-1 まで n 回、その内側で j = 0..n-1 まで n 回まわるので、内側の本体は n × n 回呼ばれます

O(n^2) は 2 次関数 的に増えます

入れ子ループの実行回数とは

2 重ループの実行回数を数えて、O(n^2) が n の 2 乗で増えていく挙動を体感する。本レッスンでは、入れ子ループの実行回数の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

前のレッスンでは 1 重ループの実行回数が n 回であることを確認しました。本レッスンでは 入れ子ループ (nested loop) を扱います。2 重の for ループは、外側のループ 1 回ごとに内側のループが n 回まわるため、合計の実行回数は n × n = n^2 回になります。

この差は、データ量が増えると劇的に効いてきます。n = 1000 のとき、1 重ループは 1000 回ですが、2 重ループは 1000000 回。n を 10 倍すれば、2 重ループの実行回数は 100 倍になります。これが O(n^2) のアルゴリズムが「スケールしない」と言われる理由です。

1 重ループは O(n) 、2 重ループは O(n^2) 、3 重ループは O(n^3) 。深さがそのままべき乗の指数になる。

2 重ループの構造

Python

for i in range(n):
    for j in range(n):
        # ここは n * n 回実行される

外側が i = 0..n-1 まで n 回、その内側で j = 0..n-1 まで n 回まわるので、内側の本体は n × n 回呼ばれます。これを可視化すると、ちょうど n × n の正方形マスを全部踏むイメージになります。

diagram (will load when visible)

Big-O の感覚

O(n^2) は 2 次関数 的に増えます。n が 2 倍になれば実行時間は 4 倍、10 倍になれば 100 倍です。実際の現場では n が大きくなる箇所で 2 重ループを書くと、すぐに性能問題に直結します。

n = 10 なら 100 、n = 100 なら 10000 、n = 1000 なら 1000000 。指数的ではないが、線形よりはるかに速く膨らむ。

Python での実装例

Python

def countNested(n):
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    return count

外側と内側でそれぞれ n 回まわり、内側の count += 1 は n * n 回実行されます。

JavaScript での実装例

JavaScript

function countNested(n) {
  let count = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      count += 1;
    }
  }
  return count;
}

よくある間違い

1 つ目は 外側と内側で違う変数を使い忘れる ケースです。外側を i 、内側を j のように別の変数にしないと、同じ変数を使うと内側ループがカウンタを書き換えてしまい、意図した n×n 回ではなく外側の進行が乱れて結果が壊れることがあります。

2 つ目は 計算量を直感で n + n と勘違いする ケースです。並列に並んでいる 2 つのループ (上下に並ぶループ) なら n + n = 2n = O(n) ですが、入れ子になると n × n = O(n^2) に跳ね上がります。

3 つ目は n^2 を実際に書き出さないと体感しにくい こと。n = 0 で 0 、n = 3 で 9 、n = 10 で 100 、と手元で計算してみると「2 乗で増える」感覚がつかめます。

やってみよう

n = 10 で 100 、n = 100 で 10000 を返すことを確認する。
もし内側のループを for j in range(i) に変えたら、合計は 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 になり、これも O(n^2) 。
3 重ループの実行回数を予想して書いてみる。n^3 に比例することが分かるはず。

O(n^2) のアルゴリズムは n = 10^4 あたりが現実的な限界。それ以上を扱うときは別のアプローチを考える。

Java と Go での実装

Java

public static int countNested(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            count += 1;
        }
    }
    return count;
}

func countNested(n int) int {
    count := 0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            count += 1
        }
    }
    return count
}

上三角ループの計算量

内側の範囲を range(i) にすると、内側の本体は 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 回しか実行されません。これは厳密には n の 2 乗 / 2 ですが、Big-O では定数倍を無視するので O(n^2) です。実装の細かい違いで定数倍は変わっても、オーダーは変わりにくいというのが Big-O の使い勝手の良さです。

ループの回数を「n^2」「n(n-1)/2」「n(n+1)/2」のように厳密に書ける必要はない。O(n^2) という大雑把な見積もりで十分。

`O(n log n)` という中間

O(n) と O(n^2) の間には O(n log n) があります。これはマージソートやクイックソートが達成する計算量で、n = 100万 でも 2000万 ステップ程度で済みます。O(n^2) なら 100万 × 100万 = 10^12 ステップなので、桁違いに速いです。多くの実用的なソートアルゴリズムは O(n log n) を目指して設計されています。

よくある質問

Q. このトピックを覚える意味は何ですか？

A. ループのネストが性能に与える影響を定量的に見積もれると、大量データを扱うコードが遅い原因をすぐ特定できます。「このロジックは O(n²) だから n=10万では現実的に動かない」と判断できることが、アルゴリズム選定や設計改善の第一歩になります。

Q. 実務でこの知識を使う場面は？

A. 重複検出・総当たりマッチング・距離行列計算など、全ペアを比較するロジックはほぼ 2 重ループになります。データ件数が 1 万を超えると突然重くなる、という現象は O(n²) の壁そのものです。この感覚があると、コードレビューや設計判断で早期に問題を検知できます。

Q. 他の章とどう繋がりますか？

A. 後続の章で扱うアルゴリズム（探索・ソート）の効率比較の土台になります。バブルソートが O(n²) でマージソートが O(n log n) である理由も、ループの構造を追えば自然に理解できます。計算量の読み方が身につくと、後続トピックの実装の意味が腹落ちしやすくなります。

次のレッスン

次は 線形探索 (O(n)) に進みましょう。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

入れ子ループの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 入れ子ループとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

入れ子ループの実行回数