1

任务是找出“find”和“union”的Union-Find结构中m个操作的最坏情况下的时间复杂度，此时所有“union”操作都发生在所有“find”操作之前。

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 参数。也许还需要在分析中使用逆阿克曼函数，但我不知道如何。

4

1 回答 1

1

“查找”操作（FindSet）

  • 跟随从 v“向上树”到根的指针，找到 v 的集合标识符
  • 当递归调用返回集合标识符时，每个节点将其指针从其父节点更改为根节点，从而压缩树
  • 在“查找”操作期间不更新树等级（树的高度上限）

“联合”操作

  • 对于每个集合或“树”，保持一个作为树高度上限的等级
  • 具有较小等级的根（较短的树）指向具有较大等级的根（较高的树）
  • 让树木“矮”
  • 如果两棵树的等级相同，则选择一棵指向另一棵。然后树的等级增加 1

时间复杂度

  • 我们将执行 O(E)“查找”和“联合”操作
  • 我们执行 V MakeSet 操作
  • “find”、“union”和 MakeSet 需要 α(V) 时间（阿克曼函数的倒数，增长非常缓慢）
  • 这给了我们 O((V+E) α(V))
  • |电子| >= |V|-1，因此联合查找需要 O(E α(V))
  • α(V) 在 O(log V) 中，在 O(log E) 中
  • 因此Union-Find结构的时间复杂度为O(E log E)或O(E log V)
于 2019-12-02T13:50:13.200 回答