Java | アルゴリズムの計算量

Javaで学ぶ「アルゴリズムの計算量」（前半）

アルゴリズムの計算量は、「そのコードがどれくらい遅くなる可能性があるか」を見抜くためのものです。 小さい入力では気にならなくても、データ量が増えた瞬間に「急に重くなるコード」と「まだ余裕があるコード」の差がはっきり出ます。 前半では、難しい記号に飛びつく前に、まず「考え方」と「直感」を育てることをテーマにします。 Javaの具体例を交えながら、時間計算量の基本をかみ砕いて整理していきます。

計算量とは何か（まずはざっくりしたイメージから）

計算量とは、「入力サイズが大きくなったとき、処理時間やメモリ使用量がどう増えるか」を表す指標です。 ここでは特に「時間計算量」に焦点を当てます。

重要なのは、「正確な秒数」ではなく「増え方の傾向」を見るという点です。 例えば、次のような違いがあります。

入力が2倍になったとき、処理時間もほぼ2倍になるコード 入力が2倍になったとき、処理時間が4倍、8倍…と爆発的に増えるコード

この「増え方の違い」を言葉にするのが、計算量の役割です。

Javaの具体例で「増え方」を感じてみる

まずは、非常にシンプルなコードから始めます。

public static void printAll(int[] arr) {
    for (int value : arr) {
        System.out.println(value);
    }
}

public static void printAll(int[] arr) {
    for (int value : arr) {
        System.out.println(value);
    }
}

このメソッドは、配列の要素数が増えれば増えるほど、 ループの回数が増えていきます。

要素が 10 個なら 10 回 要素が 100 個なら 100 回 要素が 10,000 個なら 10,000 回

このように、「入力サイズ n に対して、処理回数がほぼ n に比例して増える」コードです。 この増え方を、後で「O(n)」という形で表現しますが、 今は「入力が増えた分だけ素直に増えるコード」としてイメージしておいてください。

二重ループで「増え方」が一気に変わる

次に、二重ループの例を見てみます。

public static void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}

public static void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}

このコードは、「すべてのペア」を表示しています。 ループの回数はどうなるでしょうか。

外側のループが n 回 内側のループも n 回 合計で n × n 回、つまり n² 回になります。

要素が 10 個なら 100 回 要素が 100 個なら 10,000 回 要素が 1,000 個なら 1,000,000 回

ここで重要なのは、「入力が増えたときの増え方が、さっきとはまったく違う」ということです。 一重ループは「素直に増える」 二重ループは「急に重くなる」

この違いを見抜けるようになることが、計算量を学ぶ最大の目的です。

計算量を「O( )」で表す理由

計算量は、一般的に「Big-O記法（ビッグオー）」で表現します。 例えば

O(1) O(n) O(n²) O(log n)

といった形です。

ここで大事なのは、「細かい定数は気にしない」という姿勢です。 例えば、次の二つのコードを比べてみます。

public static void printAllA(int[] arr) {
    for (int value : arr) {
        System.out.println(value);
    }
}

public static void printAllB(int[] arr) {
    for (int value : arr) {
        System.out.println(value);
        System.out.println(value * 2);
    }
}

public static void printAllA(int[] arr) {
    for (int value : arr) {
        System.out.println(value);
    }
}

public static void printAllB(int[] arr) {
    for (int value : arr) {
        System.out.println(value);
        System.out.println(value * 2);
    }
}

printAllA は 1 回のループで 1 回表示 printAllB は 1 回のループで 2 回表示

実行時間は printAllB の方が「だいたい2倍」ですが、 計算量としてはどちらも「O(n)」と表現します。

理由は、「入力サイズが大きくなったときの増え方」が同じだからです。 定数倍の違いは、計算量の議論では切り捨てて、 「n に比例して増える」という本質だけを見ます。

代表的な計算量のイメージをつかむ

ここで、代表的な計算量の「感覚」をざっくり整理しておきます。

O(1) 入力サイズに関係なく、処理時間がほぼ一定。 例えば「配列の特定インデックスを読む」「変数を代入する」など。

O(n) 入力サイズに比例して処理時間が増える。 一重ループが典型。

O(n²) 入力サイズの二乗に比例して増える。 二重ループが典型。

O(log n) 入力サイズが増えても、増え方が非常にゆるやか。 二分探索などが代表例。

O(2ⁿ) 入力サイズが少し増えただけで、処理時間が爆発的に増える。 全探索や一部の再帰アルゴリズムが該当。

この中で、初心者がまず押さえるべきなのは O(1), O(n), O(n²), O(log n) の4つです。 O(2ⁿ) は「危険な計算量」として覚えておくと良いです。

Javaの具体例で「O(1)」と「O(log n)」を感じる

O(1) の例として、配列アクセスを考えます。

public static int getFirst(int[] arr) {
    return arr[0];
}

public static int getFirst(int[] arr) {
    return arr[0];
}

配列の先頭要素を返すだけなので、 配列の長さが 10 でも 10,000 でも、処理時間はほぼ同じです。 これが「O(1）」のイメージです。

O(log n) の例として、二分探索を考えます。 ソート済み配列から特定の値を探すアルゴリズムです。

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

このコードは、毎回「範囲を半分にする」ことで探索を進めます。 要素数が 1,000 でも、2,000 でも、4,000 でも、 必要なステップ数は「半分にする回数」に比例するため、 増え方が非常にゆるやかです。

これが「O(log n）」の感覚です。

計算量を理解することがなぜ重要か

計算量を理解すると、次のような力が身につきます。

コードを書いたときに、「この処理はデータが増えたら危ないな」と予測できる アルゴリズムを選ぶときに、「どれがスケールするか」を判断できる セキュリティの観点から、「計算量を悪用した攻撃（DoS）」を意識できる

特に、再帰や全探索を使うときには、 計算量を意識しないと「小さい入力では動くけど、大きくした途端に固まるコード」を量産してしまいます。

前半では、「増え方の違い」と「代表的な計算量のイメージ」を中心に整理しました。 後半では、より実務寄りに

ソートアルゴリズムの計算量 再帰と計算量の関係 計算量とセキュリティ（DoS攻撃の観点） 実際にアルゴリズムを比較する視点

などを、Javaコードとともに深掘りしていきます。