begin: 20170613
version: 20170724
第八章 不相交集ADT
1.等價關(guān)系
- 自反性
- 對稱性
- 傳遞性
2. 動態(tài)等價性問題
- 保存每個元素所屬的等價類i，等價類更新時更新每個元素的相應(yīng)值，單次 Union運(yùn)行時間O（N）伙判，連續(xù)N-1次運(yùn)行時間大Omiga（N^2）境钟，F(xiàn)ind時間O（1）误证；
- 改進(jìn)：添加關(guān)系時修改元素相對少的類中元素的等價類值蛀醉，N-1次Union時間O（NlogN）著摔，任意M次Find和N-1次Union用時O（M+NlogN）绎谦。
3. 更優(yōu)方法的基本數(shù)據(jù)結(jié)構(gòu)
構(gòu)建等價類森林管闷，它們非顯式地存儲在一個數(shù)組P中，P[i]值代表節(jié)點(diǎn)i父節(jié)點(diǎn)位置索引窃肠，等價類樹根節(jié)點(diǎn)指向0（0位置不存儲有效元素）：
- Find:向上找到根節(jié)點(diǎn)位置包个，O（N），M次連續(xù)操作O（MN）冤留；
- Union:將其中一個節(jié)點(diǎn)所在樹根節(jié)點(diǎn)指向另一個節(jié)點(diǎn)所在樹根節(jié)點(diǎn)碧囊，平均時間分析依賴于模型树灶。
4. 靈巧求并算法
- 按大小求并：
- Find:最壞（logN），M次連續(xù)操作O（MlogN）糯而；
- Union:M次連續(xù)操作平均時間O（M）天通。
- 按高度求并：
對按大小求并的簡單修改。
5. 路徑壓縮
連續(xù)M次操作最壞O(MlogN)
6. 按秩求并和路徑壓縮的最壞時間
M次Find和Union操作的最壞時間O(Mlog*N),加強(qiáng)結(jié)論是O（Mα（M,N））,說明其幾乎是線性的歧蒋。
