算法(4th ed)(211):基础——案例研究:union-find 算法 7.2.8

阅读数:8 2019 年 11 月 9 日 15:59

算法(4th ed)(211):基础——案例研究:union-find 算法 7.2.8

(实现:最优算法)

我们可以找到一种能够保证在常数时间内完成各种操作的算法吗?这个问题非常困难并且困扰了研究者们许多年。在寻找答案的过程中,大家研究了 quick-union 算法和加权 quick-union 算法的各种变体。例如,下面这种路径压缩方法很容易实现。理想情况下,我们希望每个节点都直接链接到它的根节点上,但我们又不想像 quick-find 算法那样通过修改大量链接做到这一点。我们接近这种理想状态的方式很简单,就是在检查节点的同时将它们直接链接到根节点。这种方法乍一看很激进,但它的实现非常容易,而且这些树并没有阻止我们进行这种修改的特殊结构:如果这么做能够改进算法的效率,我们就应该实现它。要实现路径压缩,只需要为find() 添加一个循环,将在路径上遇到的所有节点都直接链接到根节点。我们所得到的结果是几乎完全扁平化的树,它和 quick-find 算法理想情况下所得到的树非常接近。这种方法即简单又有效,但在实际情况下已经不太可能对加权 quick-union 算法继续进行任何改进了(请见练习 1.5.24)。对该情况的理论研究结果非常复杂也值得我们注意:路径压缩的加权 quick-union 算法是最优的算法,但并非所有操作都能在常数时间内完成。也就是说,使用路径压缩的加权 quick-union 算法的每个操作在在最坏情况下(即均摊后)都不是常数级别的,而且不存在其他算法能够保证 union-find 算法的所有操作在均摊后都是常数级别的(在非常一般的 cell probe 模型之下)。使用路径压缩的加权 quick-union 算法已经是我们对于这个问题能够给出的最优解了。

评论

发布