時間・空間計算量とは（全体像）
アルゴリズムの効率は、2つの面から見る。
- 時間計算量 … アルゴリズムが、どれくらい時間がかかるか。
- 空間計算量 … アルゴリズムが、どれくらいメモリを使うか。
ここで一番のポイント。時間と空間は、別の指標だ。「時間＝空間」と思い込むと誤りになる。しかも、片方を良くすると、もう片方が悪くなる「トレードオフ」の関係になることがある。
たとえば、計算した答えをメモしておく（メモ化）と、メモリは多く使う（空間↑）が、次からは計算しなくてすむので速くなる（時間↓）。このように、時間とメモリは、交換になることがある。
詳しく：トレードオフと、3つのケース
ここが心臓部。ポイントを表で押さえよう。
時間・空間計算量のポイント
| 項目 | やさしい意味 |
|---|---|
| 時間計算量 | 実行にかかる時間 |
| 空間計算量 | 使うメモリの量 |
| トレードオフ | 片方を良くすると、もう片方が悪くなることがある |
| 3つのケース | 最悪・平均・最良の3つで分析する |
まず、トレードオフ。たとえば、メモ化（答えを覚えておく）は、メモリを多く使うが、時間は速くなる。逆に、メモリを節約すると、時間が増えることもある。
そして、計算量を見るときは、1つの値だけでなく、3つのケースで考える。最悪のとき（Worst）・平均のとき（Average）・最良のとき（Best）だ。「いつも最悪ケースだけを見る」と思い込むと誤りで、平均や最良も分析の対象になる。
わかりやすく言い換えると
身近なたとえで整理しよう。
時間計算量と空間計算量は、「どれだけ速いか（時間）」と「どれだけメモリを使うか（空間）」の、2つのものさし。別ものだ。
トレードオフは、「答えをメモしておけば（メモリを使う）、次から計算せず速くなる」こと。要するに、時間とメモリは、交換になることがある。
3つのケースは、「いちばん悪いとき・ふつう・いちばん良いとき」で見ること。つまり、最悪だけでなく、平均や最良も考える。
試験のツボ
🔴 一番出る：時間と空間は別
①時間計算量＝実行にかかる時間
②空間計算量＝使うメモリの量（別の指標）
🔴 次に出る：トレードオフ
①片方を良くすると、もう片方が悪くなることがある
②例：メモ化（メモリ↑）で、時間↓になる
🟡 押さえると安定：3つのケース
①最悪・平均・最良の3つで分析する
②いつも最悪ケースだけを見るわけではない
よくある間違い
①「時間計算量と空間計算量は、同じ指標だ」→ ✗ 別の指標。しかも、片方を良くすると片方が悪くなるトレードオフになることもある。
②「計算量は、いつも最悪ケースだけを見る」→ ✗ 最悪・平均・最良の3つのケースで分析する。
③「メモ化は、メモリも時間も、両方とも節約できる」→ ✗ メモ化は、メモリを多く使うが、時間は速くなる（トレードオフ）。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（時間・空間計算量の正体）
時間・空間計算量に関する次の記述のうち、最も適切なものはどれか。
- 社員の出退勤を記録して、毎月の給与を計算するためのしくみである
- 取引先へ毎月の請求書を郵送する、決まった事務作業のことを指す
- 完成したシステムを宣伝して、より多く売るための広告活動である
- 時間は実行時間、空間はメモリの量を表す、2つの指標なのである
解答は 4 だぱん。
時間・空間計算量は、時間は実行時間、空間はメモリの量を表す、2つの指標なんだぱん。別ものだから、まちがえないようにするといいぱん。
選択肢1は給与計算、選択肢2は請求書の事務、選択肢3は広告で、どれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算のしくみではない |
| 2 | ✗ | 請求書の事務の話 |
| 3 | ✗ | 広告活動ではない |
| 4 | ✓ | 時間は実行時間・空間はメモリで正しい |
オリジナル問題2（トレードオフ）
時間と空間のトレードオフに関する次の記述のうち、最も適切なものはどれか。
- 社員の給与の計算しだいで、時間と空間が決まるとされているものだ
- 片方を良くすると、もう片方が悪くなることがある（メモ化など）
- 取引先への請求書の枚数しだいで、時間と空間が決まるとされている
- 時間と空間は、両方とも同時に節約できるものだとされている
解答は 2 だぱん。
時間と空間は、片方を良くすると、もう片方が悪くなることがある（メモ化など）んだぱん。メモ化はメモリを使うけど、時間は速くなるんだぱん。
選択肢1の給与、選択肢3の請求書、選択肢4の「両方同時に節約」は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算で決まるのではない |
| 2 | ✓ | 片方を良くすると片方が悪くなるで正しい |
| 3 | ✗ | 請求書の枚数で決まるのではない |
| 4 | ✗ | 両方同時に節約とは限らない |
オリジナル問題3（3つのケース）
計算量のケース分析に関する次の記述のうち、最も適切なものはどれか。
- 最悪・平均・最良という3つのケースで分析するものである
- いつも最悪ケースだけを見るものだとされているものである
- 社員の給与を計算するケースだけを見るとされているものだ
- 取引先へ請求書を郵送するケースだけを見るとされている
解答は 1 だぱん。
計算量は、最悪・平均・最良の3つのケースで分析するんだぱん。いつも最悪だけ、ではないんだぱん。
選択肢2の「最悪だけ」、選択肢3の給与、選択肢4の請求書は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 最悪・平均・最良で分析で正しい |
| 2 | ✗ | 最悪だけではない |
| 3 | ✗ | 給与計算のケースではない |
| 4 | ✗ | 請求書の事務のケースではない |
まとめ
押さえどころ
- 🔴 時間・空間計算量 ＝ 時間計算量は実行時間、空間計算量はメモリの量。別の指標。
- 🔴 トレードオフ ＝ 片方を良くすると、もう片方が悪くなることがある（メモ化はメモリ↑・時間↓）。
- 🟡 3つのケース ＝ 最悪・平均・最良の3つで分析する。いつも最悪だけではない。
次に学ぶ
- 計算量（ビッグオー記法） ── 計算量をO(n)などで表す書き方。時間・空間の効率を比べる。
- メモ化 ── 計算した答えを覚えておく工夫。メモリを使って、時間を速くする。
執筆: SikakuQuest編集部