Big-O のコード例で学ぶ：アルゴリズム計算量を簡単に理解する

1. 概要

Big-O は、入力サイズが増加するときに実行時間（またはメモリ）の増加速度を説明する方法です。この記事では難しい数式を使わず、実際の Java コードを通じて一般的な計算量の各レベルを紹介し、どの行がコストを生じるかを分析します。この記事を読み終わった後、コードを見るだけで、手作業で計算することなく、それが O(1)、O(n)、O(n log n)、O(n²) のいずれであるかをすぐに判定できるようになります。

2. Big-O とは、そしてなぜ重要なのか

Big-O は「入力が 2 倍になったら、実行時間は何倍になるか？」という質問に答えます。定数と小さな要因を無視し、n（入力サイズ）が無限大に向かうときの増加傾向だけを保持します。

n = 1.000      -> O(n) は ~1.000 ステップを実行
n = 1.000.000  -> O(n) は ~1.000.000 ステップを実行（線形増加）
n = 1.000.000  -> O(n²) は ~10^12 ステップを実行（急速に増加）

2 つのコードは「見た感じは同じ」でも、一方にループが隠れた関数呼び出しがある場合、計算量が大きく異なります。Big-O を理解することで、テストデータ 100 件では正常に動作するコードが、本番環境で 1000 万件になると「固まる」という状況を避けられます。

注記： Big-O は最も一般的な慣例として最悪ケース（worst case）を表します。明示的に best-case または average-case と述べられていない限り。

3. O(1) – 定数時間

実行時間は入力サイズに関わらず一定です。

public class InventoryCache {

    private final Map<String, Integer> stockBySku = new HashMap<>();

    public Integer getStock(String sku) {
        return stockBySku.get(sku); // HashMap.get は平均 O(1)
    }
}

HashMap の get() はキーをハッシュして対応するバケットに直接ジャンプするため、マップの要素数に依存しません。同様に、array[i] または ArrayList の list.get(i) へのアクセスも、単にオフセット アドレスを計算するだけなので O(1) です。

4. O(n) – 線形時間

実行時間は入力サイズに比例して増加します。

public class OrderValidator {

    public boolean hasExpiredItem(List<Order> orders) {
        for (Order order : orders) {
            if (order.isExpired()) {
                return true; // 早く終わる可能性もありますが、最悪ケースでは全体をスキャンします
            }
        }
        return false;
    }
}

for ループは orders の最大 n 要素をスキャンします。最悪ケースは期限切れの注文がない場合に発生し、リスト全体をチェックする必要があります。これは典型的な O(n) パターンです：1 つの単純なループ、ネストしていません。

4.1. よくある落とし穴：ループ内の contains()

public class DuplicateChecker {

    // O(n²)。リストの contains() は O(n)、n 回ループするため
    public boolean hasDuplicateSlow(List<String> emails) {
        List<String> seen = new ArrayList<>();
        for (String email : emails) {
            if (seen.contains(email)) {
                return true;
            }
            seen.add(email);
        }
        return false;
    }
}

ArrayList の seen.contains(email) は O(n) です。線形探索が必要だからです。ループ内でこれを呼び出すと、関数全体が O(n²) になります。データ構造に気付かないと陥りやすい落とし穴です。

public class DuplicateChecker {

    // O(n)。HashSet の add/contains は O(1) だから
    public boolean hasDuplicateFast(List<String> emails) {
        Set<String> seen = new HashSet<>();
        for (String email : emails) {
            if (!seen.add(email)) { // add() は既に存在する場合は false を返します
                return true;
            }
        }
        return false;
    }
}

List を HashSet に変更するだけで、計算量は O(n²) から O(n) に低下します。これは正しいデータ構造の選択が「マイクロ最適化」より重要であることを示す最も実用的な例です。

5. O(log n) – 対数時間

各ステップで検索空間の半分を削除します。

public class PriceLookup {

    // sortedPrices は事前に昇順でソートされている必要があります
    public int findIndex(int[] sortedPrices, int target) {
        int low = 0;
        int high = sortedPrices.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (sortedPrices[mid] == target) {
                return mid;
            } else if (sortedPrices[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

二分探索は while ループのたびに配列を二分割するため、n = 1.000.000 の場合、約 20 ステップ（log₂ 1.000.000 ≈ 20）で結果が得られます。百万個の要素を線形探索する代わりに。

class PriceLookupTest {

    @Test
    void shouldFindIndexInSortedArray() {
        int[] prices = {10, 20, 30, 40, 50};
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(prices, 40);

        assertThat(index).isEqualTo(3);
    }

    @Test
    void shouldReturnMinusOneWhenNotFound() {
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(new int[] {1, 2, 3}, 99);

        assertThat(index).isEqualTo(-1);
    }
}

このテストは、見つかった場合（index を返す）と見つからない場合（-1 を返す）の両方の正しい動作を確認します。これは二分探索の 2 つの最も重要な分岐です。

6. O(n log n) – 線形時間と対数時間の組み合わせ

これは merge sort、quick sort（平均ケース）、または Collections.sort() などの効率的なソート アルゴリズムの計算量です。

public class RevenueReport {

    public List<Order> sortByAmountDescending(List<Order> orders) {
        List<Order> copy = new ArrayList<>(orders);
        copy.sort(Comparator.comparing(Order::amount).reversed()); // O(n log n)
        return copy;
    }
}

Java の Collections.sort()/List.sort() は Timsort（merge sort の変種）を使用し、最悪ケースで O(n log n) を保証します。sort() を n 回実行するループ内で呼び出すコードが見つかった場合、総計算量は O(n² log n) になります。リファクタリングが必要なサイン。

7. O(n²) – 二次時間

2 つの入れ子になったループで、各ループが入力全体（またはほぼ全体）をスキャンします。

public class PairFinder {

    // 合計が target と等しい商品のすべてのペアを探します
    public List<int[]> findPairsSlow(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[i] + prices[j] == target) {
                    result.add(new int[] {prices[i], prices[j]});
                }
            }
        }
        return result;
    }
}

外側のループは n 回、内側のループは外側のループの各実行ごとに最大 n 回実行されます。比較の総数は約 n²/2 なので、計算量は O(n²) です。n = 10.000 の場合、これは 5000 万回の比較です。実行は可能ですが、明らかに遅い。

public class PairFinder {

    // O(n)。HashSet で既に見た値を保存するため
    public List<int[]> findPairsFast(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        for (int price : prices) {
            int complement = target - price;
            if (seen.contains(complement)) {
                result.add(new int[] {complement, price});
            }
            seen.add(price);
        }
        return result;
    }
}

各ペアを比較する代わりに、1 つのループと HashSet での O(1) 検索が必要です。これは「時間をスペースで交換する」という一般的なテクニックです。seen を保存するために追加のスペースが必要ですが、計算量は O(n²) から O(n) に削減されます。

8. O(2^n) – 指数時間

実行時間は入力が 1 増えるたびに 2 倍になります。すべての部分集合を計算する再帰関数に一般的に見られます。

public class SubsetGenerator {

    public List<List<Integer>> generateAllSubsets(List<Integer> items) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(items, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(List<Integer> items, int index,
                            List<Integer> current, List<List<Integer>> result) {
        if (index == items.size()) {
            result.add(new ArrayList<>(current));
            return;
        }
        // ブランチ 1: item[index] を選択しない
        backtrack(items, index + 1, current, result);

        // ブランチ 2: item[index] を選択する
        current.add(items.get(index));
        backtrack(items, index + 1, current, result);
        current.remove(current.size() - 1);
    }
}

各要素は 2 つの再帰分岐（選択または非選択）を作成するため、n 要素で 2^n 個の部分集合があります。n = 20 の場合、既に 100 万を超える部分集合があります。n = 40 の場合、合理的な時間内に完了する機械がありません。これは、問題が許可する場合、動的計画法（dynamic programming）アルゴリズムの検討が必要なサインです。

9. 実際のベンチマークで素早く比較する

O(n) と O(n²) の違いを「目で見る」ための簡単なテスト例：

class DuplicateCheckerBenchmarkTest {

    @Test
    void fastVersionShouldHandleLargeInputQuickly() {
        List<String> emails = new ArrayList<>();
        for (int i = 0; i < 100_000; i++) {
            emails.add("user" + i + "@example.com");
        }
        DuplicateChecker checker = new DuplicateChecker();

        long start = System.nanoTime();
        boolean hasDuplicate = checker.hasDuplicateFast(emails);
        long elapsedMs = (System.nanoTime() - start) / 1_000_000;

        assertThat(hasDuplicate).isFalse();
        assertThat(elapsedMs).isLessThan(500); // O(n) なので 100k 要素でも非常に高速です
    }
}

同じ 100,000 メールで hasDuplicateFast を hasDuplicateSlow に置き換えると、実行時間は 500ms をはるかに超えます。実際のデータで O(n) と O(n²) の違いを明確に示しています。

10. まとめの表と素早い判定ルール

Big-O	コード内の兆候	例
O(1)	ループなし、直接アクセス（配列インデックス、HashMap.get）	map.get(key)
O(log n)	各ステップで検索空間を半減	二分探索
O(n)	入力をスキャンする単一ループ	List をループ
O(n log n)	ループと sort の組み合わせ、または分割統治法	Collections.sort()
O(n²)	ネストされたループ、両方とも入力をスキャン	各ペアを比較
O(2^n)	各ステップで 2 つの再帰分岐、枝刈りなし	すべての部分集合を生成

素早く数える規則：ループの入れ子の数を数える 入力をスキャンするもの。ループの各レベルが「n の累乗」を追加します。

ループ内でライブラリ関数（contains、sort、indexOf）を呼び出す場合、その関数の計算量を合計に足す前に確認してください。

注記： Big-O は実際の定数については何も言いません。大きな定数を持つ O(n) アルゴリズム（例えば、ループの各イテレーションでファイルを読む）は、n がまだ十分に大きくない場合、小さな定数を持つ O(n log n) より遅い可能性があります。実際にプロファイルするまで、盲目的に Big-O を最適化しないでください。

11. 結論

Big-O は傾向を予測するツールであり、絶対値ではありません。ただし、その傾向が、データが成長するときにコードが生き残るか崩壊するかを決定します。最も実用的なヒント：ループを書くたびに、「このループ内で O(n) 関数を呼び出していないか？」と自問してください。これが実務で不注意に生じる O(n²) エラーの原因のほとんどです。上記の 6 つの計算量レベルをしっかり理解すれば、毎日遭遇するアルゴリズム コードのほとんどを読み、理解し、議論するのに十分です。