1

我收到了这个作业问题

“詹姆斯声称他成功地实现了从最大堆 (ExtractMax) 中提取，这需要 O((log n)^0.5)

解释詹姆斯犯错的原因

我知道从最大堆中提取需要 O(log n) 但我如何证明 James 是错误的？

4

2 回答 2

2

从这里可以看出，构建堆可以在 O(n) 中完成。现在如果提取最大值可以在 O((log n)^0.5) 中完成，那么可以通过重复提取最大元素来对整个集合进行排序 n * O((log n)^0.5)。然而，这是不可能的，因为排序的下限是 n*logn。

因此，詹姆斯的不存在。

于 2012-06-02T22:34:33.383 回答
1

@Duh 将您的提取问题转换为排序问题的解决方案实际上非常有创意。找到一些证明排序是 O(n * log n) 的证据应该不难，并且在算法研究中将一个问题转换为另一个问题是很常见的（例如，所有 NP-Complete 问题都是彼此。这就是你如何证明它们是 NP 完全的）。也就是说，我认为有一个更简单的解决方案。

您在问题中直接说明了这一点：从二进制堆中提取是 O(log n)。想想为什么它是 O(log n)。二叉堆的结构是什么？从二叉堆中提取需要哪些操作？为什么最坏的情况是 log n 次操作？这些限制是否受到实施的影响？

现在，请记住詹姆斯的主张有两个部分：

  1. 他可以在 O((log n)^0.5) 中提取
  2. 他正在使用二进制堆。

鉴于您对二进制堆的了解，这两种说法都成立吗？为什么或者为什么不？有矛盾吗？如果有，为什么会有矛盾？最后，想想这对詹姆斯意味着什么。

于 2012-06-03T10:06:40.093 回答