algorithm - 基于数组的不相交集数据结构的时间复杂度

Question

我正在解决 this关于 CodeChef 的问题并通过 editorial .

这是实现的不相交集算法的伪代码:

Initialize parent[i] = i  
Let S[i] denote the initial array.

int find(int i)
    int j
    if(parent[i]==i)
                return i
    else
        j=find(parent[i])
        //Path Compression Heuristics
        parent[i]=j
        return j

set_union(int i,int j)
    int x1,y1
    x1=find(i)
    y1=find(j)
    //parent of both of them will be the one with the highest score
    if(S[x1]>S[y1])
        parent[y1]=x1
    else if ( S[x1] < S[y1])
        parent[x1]=y1

solve()
    if(query == 0)
        Input x and y
        px = find(x)
        py = find(y)
        if(px == py)
            print "Invalid query!"
        else
            set_union(px,py)
    else
        Input x.
        print find(x)

union 和find 的时间复杂度是多少？

IMO，find 的时间复杂度是 O(depth)，所以在最坏的情况下，如果我不使用路径压缩，复杂度是在)。由于union也用到了find，所以也有O(n)的复杂度。相反，如果我们从 union 中丢弃 find 并将两个集合的父级传递给 union，union 的复杂性> 是 O(1)。如果我错了，请纠正我。

如果应用路径压缩，那么时间复杂度是多少？

Answer 1

没有路径压缩:当我们使用不相交集的链表表示和加权联合启发式时，m 个 MAKE-SET 序列，按等级联合，FIND-SET 操作发生，其中 n 个是 MAKE-SET 操作.所以，它需要 O(m+ nlogn)。

只有路径压缩:运行时间是 theta( n + f * ( 1 + (log (base( 2 + f/n)) n ) ) )其中 f 不是 find sets 操作，n 不是 make set 操作

同时使用按等级合并和路径压缩: O( m*p(n )) 其中 p(n) 小于等于 4