我的朋友和我在这个问题上有不同的看法。问题是:在具有 n 个元素的最大堆中查找第 7 大的元素的时间复杂度是多少?
我认为它应该是 O(n),而她认为它应该是 O(1)。我的逻辑是,假设 n 是 7,那么第七个最大的元素将是堆中的最后一个元素,所以如果考虑最坏情况,时间复杂度应该是 O(n)。然而,她说既然它是最大堆,那么查找第七个最大的元素应该只需要常数时间。但按照她的逻辑,甚至第 50 个或第 100 个最大的元素也可以在 O(1) 的时间内找到。此外,在我们遇到这个问题的书中,答案是 O(logn)。
请问哪种解决方案是正确的?
我认为它应该是 O(n),而她认为它应该是 O(1)。我的逻辑是,假设 n 是 7,那么第七个最大的元素将是堆中的最后一个元素,所以如果考虑最坏情况,时间复杂度应该是 O(n)。然而,她说既然它是最大堆,那么查找第七个最大的元素应该只需要常数时间。但按照她的逻辑,甚至第 50 个或第 100 个最大的元素也可以在 O(1) 的时间内找到。此外,在我们遇到这个问题的书中,答案是 O(logn)。
请问哪种解决方案是正确的?
最大值
而不是最小值
吧?删除了最小的六个元素后,新的最小值却是原来第七个 最大的 元素,听起来不太合理。 - Silly Freakk
是项目数量。不是O(log n)。 - Jim Mischeldel-max
,它还可以被称为delete
、extract-max
等等。 - Fred Foo