algorithm - 证明优先队列操作的时间复杂度

Question

我最近参加了一个考试，有一个问题说:你的 friend 提出了一组优先级队列算法，执行以下操作:Insert(S, x) in O(1)，Peek-Max(S) 在 O(1) 中，Remove-Max(S) 在 O(1)，和Increase-Key(S, x, k) 在(logn)。你会如何向你的 friend 证明这套算法是不可能的？

我一直压力很大，因为我确定我得到了错误的答案。我说过优先级队列必须具有这样的属性，即对于一组元素 [A1, A2, ... An] 它需要具有关系 [A1 >= A2 >=.. .>= An] 我现在意识到这不是真的。只有第一个元素需要比其余元素大(假设最大优先队列)。因此，插入函数不能在 O(1) 中，因为对于一组 n 个元素，您无法确保放置的项目在恒定时间内位于正确的位置。

你们中有人对如何解决这个问题有任何见解吗？昨晚我无法休眠，以为我可能答错了这个问题。

Answer 1

反驳某事的一个简单方法是想一个反例。在这种情况下，您想找到一个显然不可能的操作序列。

例如，假设您将 n 个元素插入到队列中，然后删除最多 n 个元素。由于这是一个优先级队列，我们​​提取的元素应该按排序顺序排列。因此，使用您 friend 的算法，我们能够以 O(n) 的时间复杂度对 n 元素进行排序。我们知道排序充其量是 O(nlogn) - 在 O(n) 中排序是不可能的!