リカーシブスローダウン

リカーシブスローダウン (recursive slow-down, recursive slowdown)とは、再帰的データ構造を処理する際、親ノードをm回処理する間に子ノードに対する再帰処理をm未満であるn回のみ呼び出すようにして計算量をO(1)とする手法である(2節の定義より)。O(1)で連結や両端への追加・削除ができる両端キューなどの実装に使われる。狭義には再帰呼び出しのパターンを工夫して1回の演算で高々定数個のノードのみを処理するようにして、償却計算量ではなく最悪計算量をO(1)とする手法である(の要旨には最悪計算量が定数時間であるという記述がある)。さらに狭義にはその実現のために各ノードの状態を緑黄赤の色に分け、その並びに対して不変条件を設定する手法である。サイズがnである再帰的データ構造に対する演算の計算量をT(n)と置くと一般的にT(n)は次のように書ける。 T(n) = X + c T(f(n))ここでXは1つのノードに必要な計算量で、cは定数、fは部分構造のサイズを返す関数である。ここではXがO(1)、f(n) = n − 1の場合を考える。もしcを1未満にできれば等比数列の性質からT(n)はO(1)となる。例えばc = 1/2の場合、1 + 1/2 + 1/4 + 1/8 + ... = 2であるので全体の計算量は最初の要素の最悪計算量の2倍を超えない。そのため親ノードをO(1)で処理し、子ノードをその半分の計算量で処理できれば全体の計算量は定数時間となる。しかし計算量は離散的であるため再帰処理の中で計算量を半分にし続けることはできない。そこで、代わりに親ノードを2回処理する間に子ノードを1回だけ処理するようにする。