时间戳

首页 > 解决方案 > 使用路径压缩证明联合查找的时间复杂度

disjoint-sets - 使用路径压缩证明联合查找的时间复杂度

问题描述

维基百科页面：维基百科页面指出

如果对 n 个元素应用 m 个操作（Union 或 Find），则总运行时间为 O(m log*n)。

得出这个结果的详细分析是：

在此处输入图像描述

我的问题是：

  1. 总和不应该(m+n)log*n代替mlog*n吗？
  2. 1000 次 Find 操作的平均时间复杂度是否与每个 Find 操作的时间复杂度相同？

标签： disjoint-setsunion-find

解决方案

免责声明：我仍在尝试自己理解这些证明，所以不要声称自己是专家！我想我可能有一些见解。

1）我认为他们假设m = O（n），从而使O（（m + n）lg *（n））变为O（mlg *（n））。在 Tarjan 的原始证明（逆阿克曼函数界）（可在此处找到：https ://dl.acm.org/doi/pdf/10.1145/321879.321884?download=true ）中，他假设 FIND 操作的数量 m 超过 n。在算法简介（CLRS - ch.21）中，他们证明的界限是 m 操作，其中 n 是 MAKE-SET。人们似乎在假设 m 将渐近大于或等于 n。

2) 他们证明的是每次操作的摊销成本。这是一种分析技术，它将一系列操作所花费的时间限制在一个常数因子内，您可以从中轻松计算每个操作的平均时间。有几种不同的方法可以解决它（我相信这是聚合分析的一个例子？）。值得研究！

推荐阅读