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

出典: フリー百科事典『ウィキペディア（Wikipedia）』

計算機科学における時間と空間のトレードオフ (space-time tradeoff) または時間と記憶域のトレードオフ (time-memory tradeoff) とは、メモリの使用量が削減できる代わりにプログラムの速度が低下する、または逆に、計算にかかる時間を削減できる代わりにメモリの使用量が増える、という状況のことを言う。時間と空間がトレードオフの関係にある場合、最適な選択は、CPUの速度、RAMの量、ハードディスクの容量の価格比によって大きく異なる（例えば最近では、ハードディスクはコンピュータの他の構成要素と比べて価格の下落が速い^[要出典]）。しばしば、時間と空間のトレードオフを利用して、問題のcomplexity classを変えるということも行われる。

時間と空間のトレードオフの例として最も一般的なのはルックアップテーブルを利用したアルゴリズムである。テーブルの全てを最初から持つようにした実装では、処理時間は削減できるが、必要なメモリの量は増加する。また、テーブルの要素をその都度計算することもでき、これは計算時間は増加するが、必要なメモリの量を削減できる。

時間と空間のトレードオフは、データストレージにも当てはまる。データを圧縮せずに保存すると、圧縮した場合と比べ、消費する容量は多く、必要な時間は短かく（データの圧縮によって保存に必要な領域を減らすことができるが、データ圧縮処理を行う時間が必要になる）。どちらが適切かは場合によって異なる。

もう一つの例として、数式をウィキペディアで表示する方法が挙げられる。LaTeXのソースだけを保存しておき、ページを表示する度にそれをレンダリングする方法をとれば、空間を時間でまかなうことができる（時間はかかるが、記憶装置の使用量は少なくて済む）。ページが保存されたときに画像をレンダリングし、それを保存しておく方法をとれば、時間を空間でまかなうことができる（記憶装置の使用量は多くなるが、時間は短かくて済む）。

時間と空間のトレードオフを利用して実行時間を短くしているアルゴリズムとして、離散アルゴリズムの計算で利用されるbaby-step giant-stepアルゴリズムがある。

他の分野では、暗号システムに対する総当たり攻撃におけるレインボーテーブルの作成が、時間と空間のトレードオフにあたる。中間一致攻撃も時間と空間のトレードオフの応用である。

[編集] 外部リンク

• Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off.
• Once Upon a Time-Memory Tradeoff.
• Password Cracking and Time-Memory Trade Off