union-by-rank をせずに path compression のみの場合の最悪計算量ってどうやって出すんだ？

2010-04-15 (Thu) 19:36
一般

Union/Find アルゴリズムで path compression はするけど union-by-rank をやらない場合の計算量の証明ってどうやるのだろうか？　結果は色々なところで見つかるけど最悪の入力が何なのか分からない．Introduction to Algorithms も結果しか載ってないし．

Newer: ことはじめ

Home > 一般 > union-by-rank をせずに path compression のみの場合の最悪計算量ってどうやって出すんだ？

Calendar

Categories

< 2024-04 >
日	月	火	水	木	金	土
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

アカデミック？(78)
ソフトウェア(362)
- Linux/coLinux(122)
- Meadow/Emacs(26)
- TeX(37)
- Windows(67)
ハードウェア(76)
- PC関係(37)
- マイコン(16)
プログラミング(352)
- C/C++/C#(80)
- Haskell(26)
- Java(33)
- sed/wake/awk(40)
一般(6675)
- カメラ／写真(567)
遊び(79)

Archives

Search

Feeds

Page Top