空間計算量 — どのくらいのメモリを使うか

このトピックを終えると

空間計算量とは何か、時間計算量との関係、そして実務でいつメモリを気にする必要があるかを理解できるようになります。

時間だけが重要だと思っていた

アルゴリズムを評価する際、「どれだけ速いか」だけを考えるのが簡単です。Big-O表記でO(n)、O(n log n)、O(n^2)を比較しながら時間計算量を検討します。

しかし、コンピューターにはCPUだけがあるわけではありません。**メモリ（RAM）**もあります。どんなに高速なアルゴリズムでも、メモリを100GBも使うと、普通のコンピューターでは実行できません。

空間計算量は、アルゴリズムが入力サイズに応じてどれだけのメモリを使用するかを分析するものです。時間計算量と同様にBig-O表記を使用します。

O(1) — 入力に関係のない固定メモリ

def find_max(arr):
    result = arr[0]
    for x in arr:
        if x > result:
            result = x
    return result

配列が100個でも100万個でも、追加で使う変数はresultの1つだけです。空間計算量は**O(1)**です。「定数空間」と言います。

O(n) — 入力に比例するメモリ

def get_squares(arr):
    result = []
    for x in arr:
        result.append(x * x)
    return result

入力配列と同じサイズの新しい配列を作成します。入力がn個の場合、メモリもn個分追加で使います。空間計算量は**O(n)**です。

def reverse_string(s):
    return s[::-1]

これもO(n)です。元の文字列と同じ長さの新しい文字列を作成するためです。

O(n^2) — 2次元構造

def create_matrix(n):
    return [[0] * n for _ in range(n)]

n×nの行列を作成すると、空間計算量は**O(n^2)**です。隣接行列が代表的な例です。

再帰の隠れた空間

再帰関数は、呼び出されるたびにコールスタックにフレームを積み重ねます。これもメモリです。

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

factorial(1000)を呼び出すと、コールスタックに1000個のフレームが積み重ねられます。空間計算量は**O(n)**です。Pythonでは、デフォルトの再帰深度が1000に制限されているため、これを超えるとRecursionErrorが発生します。

ループに置き換えるとO(1)に減らすことができます。

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

同じ結果ですが、スタックを使用しません。このように、再帰をループに置き換えると、空間を節約できます。

時間と空間のトレードオフ

「時間を節約すると空間を多く使い、空間を節約すると時間がかかる」これを**時間空間トレードオフ（Time-Space Tradeoff）**と言います。

代表的な例がキャッシュです。

# 空間 O(1), 時間 O(n) — 毎回計算
def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# 空間 O(n), 時間 O(1) 参照 — 事前に計算して保存
cache = {}
def fib_cached(n):
    if n in cache:
        return cache[n]
    if n <= 1:
        result = n
    else:
        result = fib_cached(n - 1) + fib_cached(n - 2)
    cache[n] = result
    return result

メモリをより多く使用する代わりに、同じ値を2回計算しません。動的プログラミング（DP）の核心が、まさにこのトレードオフです。

ハッシュテーブルも同様です。配列をソートして二分探索すると、追加空間O(1)ですが、ハッシュテーブルを作成すると、追加空間O(n)を使用する代わりに、参照がO(1)で高速になります。

実務で空間が問題になる瞬間

一般的なWeb開発では、空間計算量を気にする必要はあまりありません。RAMが十分だからです。しかし、次の状況ではメモリがボトルネックになります。

大規模データ処理 — 10GBのログファイルを分析する場合、すべてをメモリにロードすると破綻します。1行ずつ読みながら処理する必要があります（ストリーミング）。

モバイル/組み込み — スマートフォンやIoTデバイスはRAMが限られています。アルゴリズムがメモリを少なく使用するように設計する必要があります。

コーディングテスト — 問題に「メモリ制限：256MB」などの条件があります。O(n^2)の空間を使用する解法が、メモリ不足で失敗する可能性があります。

重要なポイント

空間計算量は、アルゴリズムが入力サイズに応じてどれだけのメモリを使用するかを分析するものです。 再帰のコールスタックも空間です。再帰をループに置き換えると、O(n) → O(1)に減らすことができます。 時間と空間はトレードオフの関係であり、状況に応じてどちらを優先するかを判断する必要があります。