1

有一个关于今天到期的作业的问题已经发布了解决方案，我不明白正确的答案。该问题以不相交集合森林的形式处理不相交集合的最佳情况性能，该森林利用加权联合算法来提高性能（较小的树的根作为子节点连接到两棵树中较大的树的根) 但不使用路径压缩算法。

问题是在 n 个单例节点上执行 (n-1) 联合操作和 m>=n 以任何顺序查找操作的最佳情况是否是 Omega(m*logn) 解决方案确认是正确的，如下所示：

有一个由 n-1 个联合组成的序列 S，后跟 m >= n 的查找需要 Omega(m log n) 时间。序列 S 以序列 n-1 Unions 开始，该序列构建一棵深度为 Omega(log n) 的树。然后它有 m>=n 查找，每个查找该树的最深叶子，因此每个查找都需要 (log n) 时间。

我的问题是，为什么这证明下限是 Omega(m*logn) 是正确的？这不只是一个孤立的例子，当界限是 Omega(m*logn) 时，它不能证明所有输入的情况？我确信在反驳一个主张时只需要展示一个反例，但需要为所有可能的输入证明一个谓词以证明其正确性。

在我的回答中，我指出了这样一个事实，即当您开始将两个单例节点连接在一起时，您可能会有一个案例。然后，您将另一个单例加入到该 2 节点树中，其中 3 个节点共享同一个父节点，然后是另一个节点，等等，直到您将所有 n 个节点连接在一起。然后，您有一个树，其中 n-1 个节点都指向同一个父节点，这本质上是您使用路径压缩获得的结果。然后每个 FIND 在 O(1) 时间内执行。因此，一系列 (n-1) 个并集和 m>=n 发现最终成为 Omega(n-1+m) = Omega(n+m) = Omega(m)。

这是否意味着 Omega(m*logn) 界限不严格，因此主张不正确？我开始怀疑我是否不完全了解 Big-O/Omega/Theta：/

编辑：将问题解决得更清楚一点

EDIT2：这是原始问题的呈现方式和解决方案（我花了一点时间才意识到甘巴里诺和其他人完全编造了；铁杆意大利教授）

4

1 回答 1

2

看来我确实误解了Big-Omega的概念。出于某种奇怪的原因，我假设 Big-Omega 等同于“导致最佳性能的函数的输入是什么”。实际上，对于读者来说很可能并不奇怪，但对我来说却是一个启示，Big-Omega 只是描述了一个函数的下限。就是这样。因此，最坏情况输入将具有下限和上限（big-O 和 omega），最佳输入也将如此。在大欧米茄的情况下，我们所要做的就是想出一个场景，在最坏情况的限制下，我们选择“最佳”输入，即有一些大小为 n 的输入将使算法在最少m*logn 步骤。如果存在这样的输入，则下限很紧。

于 2011-03-18T01:41:36.940 回答