3

所以我和我的朋友在这个问题上意见不一致。它要求在 n 个元素的最大堆中搜索第 7 大元素的时间复杂度？

我认为应该是 O(n)，她认为应该是 O(1)。我的逻辑是假设 n 是 7，那么第 7 大元素将是堆中的最后一个元素，所以如果我们考虑最坏的情况，它应该是 O(n)。然而，她说，因为它是一个最大堆，所以找到第 7 个最大的元素应该花费恒定的时间。但是使用她的逻辑，即使是第 50 大元素或第 100 大元素也可以在 O(1) 时间内找到。我们遇到这个问题的书也说解决方案将是 O(logn)。

有人可以告诉我哪个解决方案是正确的吗？

4

3 回答 3

6

在最大堆中找到第七大元素的简单算法是

repeat 6 times:
    del-max(heap)
return max(heap)

第一个循环执行恒定数量的del-max操作，每个操作花费 O(lg n ) 时间。该max操作需要恒定的时间。del-max操作占主导地位，导致总复杂度为 O(lg n ) 。我并不是说这是最优的。

于 2014-02-06T10:44:35.717 回答
4

有一个 O(1) 的解决方案。假设堆表示为树，最大元素是根。比第 7 个最大元素的节点到根的距离小于或等于 6。到根的距离 <= 6 的节点数永远不会大于 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127。它是一个常数。它们可以在恒定时间内遍历。

于 2014-02-06T11:42:54.550 回答
3

有一个 O(k) 算法用于选择大小为 n 的堆中的第 k 个元素，其中 n >> k。请参阅Greg Frederickson的 An Optimal Algorithm for Selection in a Min-Heap。

您可以从该页面下载 PDF（链接在左上角）。

所以答案是你、你的朋友和你正在阅读的书都是错误的。

于 2014-02-06T15:08:53.633 回答