リカーシブスローダウン
リカーシブスローダウン (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回だけ処理するようにする。
一般化
この例のカウンタは3種類の数字から成り、増加のみをサポートする。しかし減算など別の演算を定数時間の計算量でサポートする場合、さらに多くの数字を使う必要があり、不変条件は複雑になってしまう。そこで各ノードの状態を3つの状態に分類して不変条件を統一する。
ノードをその状態により緑・黄・赤に分類する。前の例では0, 1, 2の桁がそれぞれ緑・黄・赤となる。赤はそのままでは処理できないが、次の桁を変化させて自身を緑にできるような状態である。緑は黄に変化する場合はあるが、1回の変化で赤になることはない。黄はそれ以外であり、1回の変化で赤になる可能性がある。このとき不変条件は次のようになる。
「赤である任意の桁の下には0個以上の黄が続き、さらにその下の桁に緑が必ずある」
連続する黄は1つのノードとして表現する。
亜種
遅延評価を導入し、計算量を最悪計算量から償却計算量ヘ緩めて簡略化したものをimplicit recursive slowdownと呼び、2-3 フィンガーツリーの実装などに使われている。