空間計算量の基本 — メモリ使用量の理解
空間計算量の分析方法を学びます：補助空間、インプレースアルゴリズム、再帰スタック空間、時間-空間トレードオフ。一般的なアルゴリズムの例付き。
Analysis Concepts
詳細な説明
空間計算量とは？
空間計算量は、アルゴリズムが入力サイズの関数としてどれだけの追加メモリを使用するかを測定します。
一般的なアルゴリズムの空間計算量
| アルゴリズム | 時間 | 空間 |
|---|---|---|
| バイナリサーチ | O(log n) | O(1) |
| マージソート | O(n log n) | O(n) |
| クイックソート | O(n log n) avg | O(log n) |
| ヒープソート | O(n log n) | O(1) |
インプレースアルゴリズム
インプレースアルゴリズムはO(1)の補助空間を使用します。例：ヒープソート、選択ソート、挿入ソート。
時間-空間トレードオフ
多くの場合、メモリを速度と交換できます：
- ハッシュテーブル — O(n)空間でO(1)検索
- メモ化 — O(n)空間でO(2ⁿ)再帰をO(n)時間に変換
ユースケース
空間計算量の分析は、組み込みシステム、モバイルアプリ、メモリが限られた環境で重要です。キャッシュパフォーマンスにも関係します。