有没有一个例子可以通过在Omega(q log n)中运行的秩来使Union和find算法没有联合？

Question

最近,我读到了这一点,并且惊讶于联合和查找算法的时间复杂性与路径压缩一致O((m+n) log n),m"查找"查询的数量在哪里,是n"合并"查询的数量.

我对这种复杂性感兴趣,(因为我通常没有排名实现这个算法,即使我按排名颠倒应用联合,性能也不差!)并试图找到一个可以使时间复杂度的例子.但是由于路径压缩的强大功能,它真的很难......

有没有可以实现的例子Omega((m+n) log n),或者这种复杂性只是理论上的,不实用的？

Answer 1

是的,由于Michael J. Fischer在1972年有一个匹配的下限(参见第3节).他的例子使用了深度log n的二叉树,其中深度为0的二叉树是单个节点,深度为k的二叉树是两个深度为k-1的二叉树,其中一个根指向另一个的根. .通过反复地将二叉树的根的并集指向单个并在最深的节点上执行查找,我们执行昂贵的(对数步骤)操作,使得另一个嵌入的二叉树被利用.

Python演示:这将打印参数(k+1) * 2**k所在的位置,表示键操作的近似操作计数.kexampleO(2**k)O(2**k)

p = {}

def find(a):
    global count
    b = a
    while (b in p):
        count += 1
        b = p[b]
    while (a in p):
        pa = p[a]
        p[a] = b
        a = pa
    return b

def union(a, b):
    p[find(a)] = find(b)

def deepest():
    maxd = (0, None)
    for (a, pa) in p.items():
        d = 1
        while (pa in p):
            d += 1
            pa = p[pa]
        maxd = max(maxd, (d, a))
    return maxd[1]

def example(k):
    global count, p
    count = 0
    p.clear()
    for a in range(((2 ** k) - 1), 0, (- 1)):
        union(a, (a & (a - 1)))
    r = 0
    for a in range((2 ** k), (2 ** (k + 1))):
        union(r, a)
        find(deepest())
        r = a
example(9)
print(count)