8

最近，我读到这篇文章，惊讶地发现，仅使用路径压缩的 union & find 算法的时间复杂度是O((m+n) log n)，其中m'find' 查询n的数量是 'merge' 查询的数量。

我对这种复杂性很感兴趣，（因为我通常在没有秩的情况下实现这个算法，即使我按秩倒置应用联合，性能也不错！）并试图找到一个可以使时间复杂度提高的例子。但是因为路径压缩的威力很大，所以真的很难……

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

4

2 回答 2

6

是的， Michael J. Fischer 在 1972 年给出了一个匹配的下限（见第 3 节）。他的示例使用深度为 log n 的二叉树，其中深度为 0 的二叉树是单个节点，深度为 k 的二叉树是深度为 k - 1 的两棵二叉树，其中一个的根指向另一个的根. 通过重复将二叉树的根联合指向一个单例并在最深的节点上进行查找，我们执行了一个昂贵的（对数步骤）操作，留下另一个嵌入的二叉树可供利用。

Python 演示：这将打印(k+1) * 2**kwherek的参数，表示对键example的操作的近似操作计数。O(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)
于 2014-07-21T17:50:38.003 回答
2

还是这种复杂性只是理论上的，而不是实际的？

是的。算法的复杂性是一种纯粹的理论构造，用于描述算法针对不同输入大小（在本例中为查找和联合的数量）的扩展程度。

这并不能保证特定输入实例（例如：5查找和联合）所需的步数3- 当然，除了是有限的。事实上，大 O 表示法使用了任意大的乘法常数的概念，这无助于计算精确的运行时间，但足以区分复杂度类中的算法。

于 2014-07-21T13:54:00.067 回答