begin: 20170613
version: 20170724
第八章 不相交集ADT
1.等价关系
- 自反性
- 对称性
- 传递性
2. 动态等价性问题
- 保存每个元素所属的等价类i，等价类更新时更新每个元素的相应值，单次 Union运行时间O（N），连续N-1次运行时间大Omiga（N^2），Find时间O（1）；
- 改进：添加关系时修改元素相对少的类中元素的等价类值，N-1次Union时间O（NlogN），任意M次Find和N-1次Union用时O（M+NlogN）。
3. 更优方法的基本数据结构
构建等价类森林，它们非显式地存储在一个数组P中，P[i]值代表节点i父节点位置索引，等价类树根节点指向0（0位置不存储有效元素）：
- Find:向上找到根节点位置，O（N），M次连续操作O（MN）；
- Union:将其中一个节点所在树根节点指向另一个节点所在树根节点，平均时间分析依赖于模型。
4. 灵巧求并算法
- 按大小求并：
- Find:最坏（logN），M次连续操作O（MlogN）；
- Union:M次连续操作平均时间O（M）。
- 按高度求并：
对按大小求并的简单修改。
5. 路径压缩
连续M次操作最坏O(MlogN)
6. 按秩求并和路径压缩的最坏时间
M次Find和Union操作的最坏时间O(Mlog*N),加强结论是O（Mα（M,N））,说明其几乎是线性的。
