リカーシブスローダウンとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > リカーシブスローダウンの意味・解説 

リカーシブスローダウン

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/12/25 08:02 UTC 版)

リカーシブスローダウン (recursive slow-down[1], recursive slowdown[2])とは、再帰的データ構造を処理する際、親ノードをm回処理する間に子ノードに対する再帰処理をm未満であるn回のみ呼び出すようにして計算量をO(1)とする手法である([1]2節の定義より)。 O(1)で連結や両端への追加・削除ができる両端キューなどの実装に使われる。 狭義には再帰呼び出しのパターンを工夫して1回の演算で高々定数個のノードのみを処理するようにして、償却計算量ではなく最悪計算量をO(1)とする手法である([1]の要旨には最悪計算量が定数時間であるという記述がある)。 さらに狭義にはその実現のために各ノードの状態を緑黄赤の色に分け、その並びに対して不変条件を設定する手法である[2]


  1. ^ a b c Haim Kaplan and Robert E. Tarjan, “Persistent lists with catenation via recursive slow-down”, In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing (STOC '95), New York, NY, USA: ACM, 1995, pp. 93–102. DOI=10.1145/225058.225090 http://doi.acm.org/10.1145/225058.225090
  2. ^ a b c d Chris Okasaki, Purely Functional Data Structures, New York, NY, USA: Cambridge University Press, 1998.
  3. ^ Ralf Hinze and Ross Paterson, “Finger Trees: A Simple General-purpose Data Structure”, In Journal of Functional Programming Vol. 16, No. 2, 2006, pp. 197–217, doi:10.1017/S0956796805005769


「リカーシブスローダウン」の続きの解説一覧



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

リカーシブスローダウンのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



リカーシブスローダウンのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのリカーシブスローダウン (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2024 GRAS Group, Inc.RSS