algorithm - 为什么不相交集的运行时间是根据操作次数而不是输入大小来计算的？

Question

CLRS 说“我们将根据两个参数分析不相交集的运行时间:

1. n, MAKE-SET操作次数
2. m，MAKE-SET、UNION和FIND-SET操作的总数"

为什么这与大多数根据输入大小计算复杂度的其他算法的分析不同？

Answer 1

任何使用 Disjoint-Set 数据结构的算法都将使用这 3 个操作。我们需要根据输入大小分析所有这些操作的运行时间。

通常，

1. 我们首先使用 - 'n' 个 MAKE-SET 操作创建 n 个集合(输入中的每个项目 1 个)。
2. 我们将根据需要进行 MAKE-SET、UNION 和 FIND-SET 操作。让我们以最大操作数为界 - 假设为“m”(包括最初的 n 个初始化操作)。

这些是 CLRS 中描述的 2 个数字 n，m。让我改一下

• n - 实际输入大小(用于创建初始集的 MAKE-SET)
• m - 根据算法的操作数量(MAKE-SET、UNION 和 FIND-SET)。

根据定理 21.14:

要执行“m”个操作，对于具有按等级联合和路径压缩 实现的不相交集森林，您将拥有 O(m * α(n))

的最坏情况运行时间

希望对您有所帮助!