pol*_*nts 16 algorithm time-complexity disjoint-sets amortized-analysis data-structures
以下是维基百科上不相交集合林的联合/查找算法的细分:
O(n))
O(log(n))
O(a(n))有效O(1))按等级实现联合需要每个节点保留一个rank字段用于比较目的.我的问题是,是否值得这个额外的空间？如果我按级别跳过联合而只是做路径压缩会发生什么？它够好吗？现在摊还的复杂性是多少？
发表评论意味着没有路径压缩的等级联合(摊销O(log(n)复杂性)足以满足大多数实际应用.这是对的.我要问的是另一种方式:如果你按级别跳过联合而只做路径压缩怎么办？
从某种意义上说,路径压缩是通过排名改进联合的额外步骤,这就是为什么可以省略额外步骤而不会带来灾难性后果的原因.但是联盟是否是路径压缩的必要中间步骤？我可以跳过它直接进行路径压缩,还是会发生灾难性的？
还有人指出,如果不按等级联合,重复的工会可以创建一个类似链表的结构.这意味着单一路径压缩操作可能O(n)在最坏的情况下采取.这当然会影响未来的运营,因此当我对许多运营进行摊销时,这种情况如何,这是我更感兴趣的.