implicit recursive slowdown
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/05/15 07:59 UTC 版)
「2-3 フィンガーツリー」の記事における「implicit recursive slowdown」の解説
2-3フィンガーツリーはimplicit recursive slowdownという構成手法に基づくデータ構造である。implicit recursive slowdownとは、recursive slowdownに遅延評価を導入し、計算量を最悪計算量から償却計算量ヘ緩めて簡略化したものである。recursive slowdownは親ノードをn回処理する間に子ノードをnより少ないm回処理する。そのため等比数列の性質により全体の計算量は親ノードの計算量のたかだか定数倍となる。この性質により2-3フィンガーツリーも要素の追加演算や削除演算の計算量が償却定数時間となっている。
※この「implicit recursive slowdown」の解説は、「2-3 フィンガーツリー」の解説の一部です。
「implicit recursive slowdown」を含む「2-3 フィンガーツリー」の記事については、「2-3 フィンガーツリー」の概要を参照ください。
ウィキペディア小見出し辞書の「implicit recursive slowdown」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- implicit recursive slowdownのページへのリンク
