タイムメモリトレードオフとは - わかりやすく解説 Weblio辞書

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

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

(タイムメモリトレードオフから転送)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 06:36 UTC 版)

ナビゲーションに移動検索に移動

この項目では、計算機科学における時間と空間のトレードオフについて説明しています。一般的なトレードオフについては「トレードオフ」をご覧ください。

計算機科学における時間と空間のトレードオフ（じかんとくうかんのトレードオフ、英: space-time tradeoff）または時間と記憶域のトレードオフ（じかんときおくいきのトレードオフ、英: time-memory tradeoff、タイム・メモリ・トレードオフ）とは、メモリの使用量が削減できる代わりにプログラムの速度が低下する、または逆に、計算にかかる時間を削減できる代わりにメモリの使用量が増える、という状況のことを言う。

時間と空間がトレードオフの関係にある場合、最適な選択は、CPUの速度、RAMの量、ハードディスクの容量の価格比によって大きく異なる。しばしば、時間と空間のトレードオフを利用して、問題の複雑性クラスを変えるというテクニックも使用される。

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

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

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

時間と空間のトレードオフを利用して実行時間を短くしているアルゴリズムとして、離散対数の計算で利用されるベビーステップジャイアントステップ（英語版）アルゴリズムがある。

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