Big-O 記法：時間計算量

Java におけるコードの最適化

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

時間計算量とは？

時間計算量：入力サイズに対する実行時間の増加度合いを表す指標
「データが10倍に増えたらどうなるか」という問いに答えるのに役立ちます
絶対的な時間には着目しません

Big-O 記法

最悪のケースを表す数学的記法です。

よく使われる計算量クラス:

O(1): 定数時間 - サイズに依存しない

O(1) を理解する

O(1) 操作の例として、ArrayList の get() が挙げられます

Strings を保持する ArrayList の内部実装（簡略化）:

public class ArrayList {}
    private String[] data; // Internal array
    private int size;

    // Get operation - direct array access
    public String get(int index) {
        return data[index]; // O(1)
    }
}

Big-O 記法

最悪のケースを表す数学的記法です

よく使われる計算量クラス:

O(1): 定数時間 - サイズに依存しない
O(n): 線形時間 - 入力サイズに比例して増加

O(n) を理解する

同様の例として、ArrayList の contains() を見てみましょう

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // Linear search through array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Not found
}

Big-O 記法

最悪のケースを表す数学的記法です

よく使われる計算量クラス:

O(1): 定数時間 - サイズに依存しない
O(n): 線形時間 - 入力サイズに比例して増加
O(n²): 二次時間 - 入力サイズの2乗に比例して増加

二次計算量の実践例

// Finding a pair of numbers that sum to a target value
// Time complexity: O(n²)

public int[] findPairWithSum(ArrayList<Integer> numbers, int targetSum) {
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers.get(i) + numbers.get(j) == targetSum) {
                console.log("Found them!")
            }
        }
    }
}

時間計算量が重要な理由

入力サイズによる影響:

O(1): 1,000 -> 1,000,000 件 = 同じ時間！
O(n): 1,000 -> 1,000,000 件 = 1,000倍遅くなる
O(n²): 1,000 -> 1,000,000 件 = 1,000,000倍遅くなる

Screenshot 2025-05-10 at 2.27.06 PM.png

練習しましょう！

Java におけるコードの最適化