分析Union-Find结构中m个操作的时间复杂度
Analyzing time complexity of m operations in Union-Find structure
任务是在"find"和"union"的Union-Find结构中求m个操作最坏情况下的时间复杂度，当所有"union"操作都发生在所有操作之前"find" 个操作。
联合查找结构以 n 个不相交的集合开始，每个集合包含一个元素。此外，每个集合都表示为一棵树，结构使用路径压缩和并集。
我在想的是，首先，所有联合操作的时间复杂度为O(log(n))，因为每个联合操作时间复杂度为O(1)，而且不会超过log(n)这样的操作。
在那之后，如果我们查看查找元素，那么对于每个元素，第一次查找将花费 O(log(n))，但下一次查找其路径中的每个元素将花费 O(1)。因此它需要的时间少于 O(m*log(n)).
我不确定如何从这里继续。我认为这可能需要：
log(n) + log(n/2) + log(n/4) + .... = log(n)*log(n)
因为每次我们要上去的路段都会变短
不过。我不确定，也看不到此处使用 m 参数的位置。
也许在分析中还需要使用逆阿克曼函数，但我不知道如何。
"find" 操作（FindSet）
- 按照从 v "up the tree" 到根的指针找到 v
的集合标识符
- 当递归调用返回集合标识符时，每个节点将其指针从其父节点更改为根节点，压缩树
- 在 "find" 操作期间没有更新树等级（树的高度上限）
"union"操作
- 对于每个集合或"tree"，维护一个等级，该等级是树高度的上限
- 等级较小的根（较短的树）指向等级较大的根（较高的树）
- 保留树木"short"
- 如果两棵树的等级相同，则选择一棵指向另一棵。然后树的等级增加 1
时间复杂度
- 我们将执行 O(E) "find" 和 "union" 操作
- 我们执行 V MakeSet 操作
- "find"、"union" 和 MakeSet 需要 α(V) 时间（阿克曼函数的反函数，增长非常缓慢）
- 这给了我们 O((V+E) α(V))
- |E| >= |V|-1，因此 Union-Find 需要 O(E α(V))
- α(V) 在 O(log V) 中 O(log E)
- 因此Union-Find结构的时间复杂度为O(E log E)或O(E log V)
任务是在"find"和"union"的Union-Find结构中求m个操作最坏情况下的时间复杂度，当所有"union"操作都发生在所有操作之前"find" 个操作。
联合查找结构以 n 个不相交的集合开始，每个集合包含一个元素。此外，每个集合都表示为一棵树，结构使用路径压缩和并集。
我在想的是，首先，所有联合操作的时间复杂度为O(log(n))，因为每个联合操作时间复杂度为O(1)，而且不会超过log(n)这样的操作。
在那之后，如果我们查看查找元素，那么对于每个元素，第一次查找将花费 O(log(n))，但下一次查找其路径中的每个元素将花费 O(1)。因此它需要的时间少于 O(m*log(n)).
我不确定如何从这里继续。我认为这可能需要：
log(n) + log(n/2) + log(n/4) + .... = log(n)*log(n)
因为每次我们要上去的路段都会变短
不过。我不确定，也看不到此处使用 m 参数的位置。 也许在分析中还需要使用逆阿克曼函数，但我不知道如何。
"find" 操作（FindSet）
- 按照从 v "up the tree" 到根的指针找到 v 的集合标识符
- 当递归调用返回集合标识符时，每个节点将其指针从其父节点更改为根节点，压缩树
- 在 "find" 操作期间没有更新树等级（树的高度上限）
"union"操作
- 对于每个集合或"tree"，维护一个等级，该等级是树高度的上限
- 等级较小的根（较短的树）指向等级较大的根（较高的树）
- 保留树木"short"
- 如果两棵树的等级相同，则选择一棵指向另一棵。然后树的等级增加 1
时间复杂度
- 我们将执行 O(E) "find" 和 "union" 操作
- 我们执行 V MakeSet 操作
- "find"、"union" 和 MakeSet 需要 α(V) 时间（阿克曼函数的反函数，增长非常缓慢）
- 这给了我们 O((V+E) α(V))
- |E| >= |V|-1，因此 Union-Find 需要 O(E α(V))
- α(V) 在 O(log V) 中 O(log E)
- 因此Union-Find结构的时间复杂度为O(E log E)或O(E log V)