リカーシブスローダウン
出典: フリー百科事典『ウィキペディア(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]。
- ^ 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
- ^ a b c d Chris Okasaki, Purely Functional Data Structures, New York, NY, USA: Cambridge University Press, 1998.
- ^ 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
- 1 リカーシブスローダウンとは
- 2 リカーシブスローダウンの概要
- 3 亜種
- リカーシブスローダウンのページへのリンク