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