時空間トレードオフ

コンピュータサイエンスにおける空間と時間のトレードオフ（時間とメモリのトレードオフ、またはアルゴリズムの空間と時間の連続体とも呼ばれる）とは、アルゴリズムやプログラムが時間短縮のために空間使用量を増やすトレードオフのことです。ここで、空間とは特定のタスクを実行する際に消費されるデータストレージ（ RAM、HDDなど）を指し、時間とは特定のタスクを実行する際に消費される時間（計算時間または応答時間）を指します。

特定の空間・時間トレードオフの有用性は、関連する固定費および変動費（例えば、CPU速度、ストレージ容量など）によって影響を受け、収穫逓減の法則が働く。

時間と記憶のトレードオフという生物学的な概念は、動物の行動の初期段階に見られる。蓄積された知識を利用したり、刺激に対する反応を「本能」としてDNAに符号化したりすることで、時間的に切迫した状況での「計算」を回避できる。コンピュータにおいては、ルックアップテーブルは初期のオペレーティングシステムから実装されてきた。

1980年、マーティン・ヘルマンは暗号解読に時間とメモリのトレードオフを用いることを初めて提案した。^{[ 1 ]}

空間と時間のトレードオフを利用するアルゴリズムには、以下のようなものがある。

• 離散対数を計算するための、段階的かつ段階的なアルゴリズム
• レインボーテーブルは、暗号学において、総当たり攻撃に必要な指数関数的な時間よりも短い時間でパスワードを解読しようとする攻撃者によって用いられる手法です。レインボーテーブルは、暗号学的ハッシュ関数のハッシュ空間にあらかじめ計算された値の一部を利用することで、数週間ではなく数分でパスワードを解読します。レインボーテーブルのサイズを小さくすると、ハッシュ空間を走査するのに必要な時間が増加します。
• 中間一致攻撃は、空間と時間のトレードオフを利用して、わずか数秒で暗号鍵を見つけ出します。$2^n+1$暗号化（および${\displaystyle O(2^{n})}$空間）と予想される$2^2n$暗号化（ただし、${\displaystyle O(1)}$単純な攻撃の空間）
• 動的計画法とは、より多くのメモリを使用することで、問題の計算時間を大幅に削減できる手法である。
• 時間・メモリ・データのトレードオフ攻撃。空間・時間トレードオフにデータという追加パラメータを加える。

• アルゴリズムの効率性
• ブルムのスピードアップ定理– 任意の関数に計算複雑度を割り当てることを排除する 
• 計算複雑度– アルゴリズムを実行するために必要なリソースの量 
• 計算資源― 計算複雑性理論の一側面 
• サビッチの定理– 決定論的空間複雑性と非決定論的空間複雑性の関係 

• フィリップ・エクスリン：より高速な暗号解読における時間とメモリのトレードオフを実現する。
• 昔々、時間と記憶のトレードオフがありました。