2010年04月15日
union-by-rank をせずに path compression のみの場合の最悪計算量ってどうやって出すんだ？
- 2010-04-15 (Thu)
- 一般
Union/Find アルゴリズムで path compression はするけど union-by-rank をやらない場合の計算量の証明ってどうやるのだろうか？ 結果は色々なところで見つかるけど最悪の入力が何なのか分からない．Introduction to Algorithms も結果しか載ってないし．
- Comments: 0
- TrackBack (Close): -