削除コストの証明の概略
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/02 05:57 UTC 版)
「スケープゴート木」の記事における「削除コストの証明の概略」の解説
スケープゴート木が n {\displaystyle n} 要素を持ち、再構築された直後とする（つまり、完全二分木であるとする）。 高々 n / 2 − 1 {\displaystyle n/2-1} 回の削除は、木を再構築する前に実行できる。 これらの削除には、それぞれ O ( log n ) {\displaystyle O(\log {n})} 時間（要素を探索し、削除済みとしてフラグを立てる時間）しかかからない。その後、 n / 2 {\displaystyle n/2} 回目の削除において木が再構築され、 O ( log n ) + O ( n ) {\displaystyle O(\log {n})+O(n)} （あるいは単に O ( n ) {\displaystyle O(n)} ）の時間がかかる。以上を考慮すると以下のように償却コストが O ( log n ) {\displaystyle O(\log {n})} である。 ∑ 1 n 2 O ( log n ) + O ( n ) n 2 = n 2 O ( log n ) + O ( n ) n 2 = O ( log n ) {\displaystyle {\sum _{1}^{n \over 2}O(\log {n})+O(n) \over {n \over 2}}={{n \over 2}O(\log {n})+O(n) \over {n \over 2}}=O(\log {n})\ }
※この「削除コストの証明の概略」の解説は、「スケープゴート木」の解説の一部です。
「削除コストの証明の概略」を含む「スケープゴート木」の記事については、「スケープゴート木」の概要を参照ください。
- 削除コストの証明の概略のページへのリンク
