为什么不相交集的 运行 时间是根据操作次数而不是输入大小来计算的？
Why is the running time of disjoint-sets calculated in terms of number of operations instead of size of input?
CLRS 说“我们将根据两个参数分析不相交集的 运行 时间：
- n，MAKE-SET操作次数
- m，MAKE-SET、UNION和FIND-SET操作的总数
为什么这与根据输入大小计算复杂度的其他算法的大多数分析不同？
任何使用 Disjoint-Set 数据结构的算法都将使用这 3 个操作。我们需要根据输入大小分析所有这些操作的运行时间。
通常，
- 我们首先使用 - 'n' MAKE-SET 操作创建 n 个集合（输入中的每个项目 1 个）。
- 我们将根据需要进行 MAKE-SET、UNION 和 FIND-SET 操作。让我们以最大操作数为界 - 比如说 'm'（包括最初的 n 个初始化操作）。
这些是 CLRS 中描述的 2 个数字 n、m。让我重新表述一下
- n - 实际输入大小（用于创建初始集的 MAKE-SET）
- m - no.of 操作（MAKE-SET、UNION 和 FIND-SET）按照算法。
根据定理 21.14:
要执行 'm' 操作，
对于具有 按秩联合和路径压缩 实现的不相交集森林，您将拥有 O(m * α(n))[=37 的最坏情况运行时间=]
希望对您有所帮助！
CLRS 说“我们将根据两个参数分析不相交集的 运行 时间：
- n，MAKE-SET操作次数
- m，MAKE-SET、UNION和FIND-SET操作的总数
为什么这与根据输入大小计算复杂度的其他算法的大多数分析不同？
任何使用 Disjoint-Set 数据结构的算法都将使用这 3 个操作。我们需要根据输入大小分析所有这些操作的运行时间。
通常，
- 我们首先使用 - 'n' MAKE-SET 操作创建 n 个集合（输入中的每个项目 1 个）。
- 我们将根据需要进行 MAKE-SET、UNION 和 FIND-SET 操作。让我们以最大操作数为界 - 比如说 'm'（包括最初的 n 个初始化操作）。
这些是 CLRS 中描述的 2 个数字 n、m。让我重新表述一下
- n - 实际输入大小（用于创建初始集的 MAKE-SET）
- m - no.of 操作（MAKE-SET、UNION 和 FIND-SET）按照算法。
根据定理 21.14:
要执行 'm' 操作， 对于具有 按秩联合和路径压缩 实现的不相交集森林，您将拥有 O(m * α(n))[=37 的最坏情况运行时间=]
希望对您有所帮助！