時空間トレードオフとは（全体像）
時空間トレードオフは、処理時間（時間）と使うメモリ（空間）が、たいてい引っぱり合う関係にあること。片方をよくすると、もう片方が悪くなりやすい。
身近な例が暗算と電卓。暗算は道具（メモリ）がいらないが時間がかかる。電卓は一瞬で答えが出る（速い）が、道具がいる。このように「速さ」と「道具（メモリ）」は引っぱり合う。
押さえたいのは、ふつうは両方を同時にはよくできないこと。だから設計では「今は速さを取るか、メモリ節約を取るか」を場面に応じて選ぶことになる。
詳しく：手法と判断基準だけ覚えれば戦える
ここが記事の心臓部。時空間トレードオフを使った代表的な手法を押さえよう。
時空間トレードオフの代表的な手法
| 手法 | やること | 効果 |
|---|---|---|
| メモ化 | 計算結果を覚えて使い回す | 時間↓・空間↑ |
| ルックアップ表 | あらかじめ答えを表にしておく | 時間↓・空間↑ |
| インプレース | 追加メモリを使わず元のデータを書き換える | 空間↓ |
| 圧縮 | データを小さくして保存する | 空間↓・解凍に時間↑ |
たとえばメモ化は、一度計算した答えを覚えておき、同じ計算が来たら使い回す。これで時間は大きく減るが、覚えるためのメモリは増える。逆にインプレースは、追加のメモリを使わず元のデータの上で書き換えるので、空間を節約できる。
では、どちらを優先するか。これは使える環境しだいだ。
どちらを優先するかの判断基準
| 環境 | 優先すること | よく使う手法 |
|---|---|---|
| メモリが潤沢（サーバーなど） | 速さ（時間） | メモ化・ルックアップ表 |
| メモリが少ない（組込み機器など） | 節約（空間） | インプレース |
つまり、メモリにゆとりがあれば速さを取り、メモリが厳しければ節約を取る。これが判断の基本、というわけだね。
わかりやすく言い換えると
要するに、時空間トレードオフは「速さとメモリは引っぱり合う」という話だ。
①速くしたい … メモ化やルックアップ表で答えを覚える（メモリは増える）
②メモリを節約したい … インプレースで元のデータを書き換える（時間は方式しだい）
③どちらを選ぶか … メモリにゆとりがあるかどうかで決める
「あちらを立てればこちらが立たず」を、設計でうまく選ぶのがコツ。
試験のツボ
🔴 一番出る：時間と空間は引っぱり合う
①速くするとメモリが増えやすい
②メモリを節約すると時間がかかりやすい
🔴 次に出る：代表的な手法
①メモ化・ルックアップ表は時間↓・空間↑
②インプレースは空間↓
🟡 押さえると安定：どちらを優先するか
①メモリが潤沢なら速さ優先（メモ化など）
②メモリが少ないなら節約優先（インプレース）
よくある間違い
①「時間もメモリも同時にいくらでも減らせる」→ ✗ ふつうは引っぱり合う。片方をよくすると、もう片方が悪くなりやすい。
②「メモ化はどんなときも有利」→ ✗ メモリが足りない環境では、覚えるための場所が確保できず逆効果になることもある。
③「インプレースは時間を必ず速くする手法」→ ✗ インプレースが節約するのは空間（メモリ）。時間はやり方しだい。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（トレードオフの本質）
時空間トレードオフに関する次の記述のうち、正しいものはどれか。
- 時間とメモリはいつも一緒に減らせるので、どちらも気にせず最小にできるものだ
- 処理を速くするとメモリが増えやすく、メモリを節約すると時間がかかりやすい
- 時間とメモリにはなんの関係もなく、片方を変えてももう片方は決して動かない
- メモリを増やすほど処理は必ず遅くなるという、一方向だけの関係になっている
解答は 2 だよ。
時空間トレードオフは処理を速くするとメモリが増えやすく、メモリを節約すると時間がかかりやすいという引っぱり合いなんだ。暗算と電卓の関係だよ。
選択肢1の「両方減らせる」、選択肢3の「関係がない」、選択肢4の「メモリを増やすほど遅い」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | ふつうは引っぱり合う |
| 2 | ✓ | 速さとメモリは相反する |
| 3 | ✗ | 互いに関係がある |
| 4 | ✗ | メモリを使うと速くなる場面が多い |
オリジナル問題2（メモ化）
メモ化に関する次の記述のうち、正しいものはどれか。
- メモ化は計算結果を覚えて使い回し、時間を減らすそのかわりにメモリが増える手法だ
- メモ化は計算結果をいっさい覚えず、毎回ゼロから計算をやり直すだけの手法とされる
- メモ化はメモリも時間も同時に減らせる、欠点のまったくない万能な手法のことである
- メモ化はメモリを節約するための手法で、時間はかえって長くかかるものとされている
解答は 1 だよ。
メモ化は計算結果を覚えて使い回し、時間を減らすかわりにメモリが増える手法なんだ。同じ計算をくり返さずに済むから速くなるよ。
選択肢2の「覚えない」、選択肢3の「欠点なし」、選択肢4の「メモリを節約する」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 時間↓のかわりに空間↑ |
| 2 | ✗ | 結果を覚えて使い回す |
| 3 | ✗ | メモリは増える |
| 4 | ✗ | メモリは増え、時間は減る |
オリジナル問題3（判断基準）
時空間トレードオフの判断基準に関する次の記述のうち、正しいものはどれか。
- 環境にかかわらず、つねにメモリ節約だけを優先するのが正しい判断とされている
- 環境にかかわらず、つねに速さだけを優先するのが唯一の正しい判断であるとされる
- メモリが潤沢なら速さを優先、メモリが少ないなら節約を優先と、環境で使い分ける
- 判断の基準はいっさいなく、どの手法を選んでも結果はまったく同じになるものだ
解答は 3 だよ。
判断は環境しだいなんだ。メモリが潤沢なら速さを優先（メモ化など）、メモリが少ないなら節約を優先（インプレース）と使い分けるよ。
選択肢1や2の「つねに片方だけ」、選択肢4の「基準がない」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | つねに節約とは限らない |
| 2 | ✗ | つねに速さとは限らない |
| 3 | ✓ | 環境で使い分ける |
| 4 | ✗ | 判断の基準がある |
まとめ
押さえどころ
- 🔴 本質 ＝ 速さとメモリは引っぱり合う。ふつうは両方を同時にはよくできない。
- 🔴 手法 ＝ メモ化・ルックアップ表は時間↓・空間↑、インプレースは空間↓。
- 🟡 判断基準 ＝ メモリが潤沢なら速さ優先、少なければ節約優先と、環境で使い分ける。
次に学ぶ
執筆: SikakuQuest編集部