ビッグオー記法: 空間計算量

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

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

空間計算量とは

時間計算量は、入力サイズが実行時間にどう影響するかを示します
空間計算量は、入力サイズがメモリ使用量にどう影響するかを示します

空間計算量を理解することは、次のようなアプリケーションを構築する上で重要です

必要な分だけのメモリを使用する
OutOfMemoryError のようなエラーでクラッシュしない

ビッグオー記法

記法は時間計算量と同じです。

代表的な計算量クラス:

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

最大値を求めるメソッド

public int findMax(int[] array) {
    int max = Integer.MIN_VALUE;
    for (int value : array) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

整数配列の要素数が10個でも1,000万個でも、使用するメモリは変数 max 1つ分だけです
空間計算量は O(1)、つまり定数空間です

値を2倍にするメソッド

public int[] doubleValues(int[] array) {
    int[] result = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        result[i] = array[i] * 2;
    }
    return result;
}

入力に n 個の要素がある場合、追加で n 個分のスペースが必要です
必要な追加メモリが入力サイズに比例して増加するため、空間計算量は O(n) です

乗算表を作るメソッド

public int[][] multiplicationTable(int n) {
    int[][] table = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            table[i][j] = (i + 1) * (j + 1);
        }
    }
    return table;
}

n が10の場合は100マス、n が100の場合は10,000マスが必要です
これは O(n²) に分類されます

空間計算量が重要な理由

メモリは有限のリソースです

これまでの例を入力サイズ10,000要素で比較してみましょう

findMax、O(1) -> 数バイトの追加メモリのみ
doubleValues、O(n) -> 約40KBの追加メモリ
multiplicationTable、O(n²) -> 約400MBの追加メモリ

findMaxは8バイト、doubleValuesは40KB、multiplicationTableは400MBのメモリ使用量増加を示す棒グラフ

空間計算量 vs. 時間計算量

忘れないでください:

空間を犠牲にして時間を節約することがあります
時間を犠牲にして空間を節約することがあります
最適な選択は、状況ごとの制約によって異なります

時間と空間のトレードオフを象徴する図

練習しましょう！

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