algorithm - 如何证明数据结构的下界 logn？

Question

我有一个家庭作业问题如下(请注意，我不是在寻找确切的答案，只是在寻找简单的建议以继续前进)。

S is a data structure which supports Insert(x,S), Delete(x, S) and Find_Smallest_Item(S) in time <= T(n). Prove a lower bound for T(n) such as Ω(logn).

到目前为止，这是我的想法:

我想我需要找到一个化简方法，将这个问题化简为一个更简单的问题，并证明它不能低于 logn。我读了很多关于下界的教程，其中大部分都将问题简化为排序，然后他们将排序用作黑盒并证明算法不能低于 nlogn。

但是在这里，我们正在处理 logn，我不知道要减少到这样的算法。也许它必须对树结构的深度做一些事情，logn。但我不知道从哪里开始。

你能给我一些提示吗？

编辑:实际上我想到了一些事情，但我不知道我是否应该用这样的技巧来证明下界。因此，我假设我有插入、删除和 find_smallest 操作，每个操作都有一个 logn 时间复杂度。

例如，要构造一个排序列表，我可以使用 delete 和 find_smallest 函数，例如我可以第一次运行 find_smallest，在找到列表中的最小元素后，我将删除该元素。我将再次运行它，因此我会找到第二小的元素，依此类推。

因此，我可以使用删除和find_smallest函数来实现排序。因此，如果我继续这样做 n 次，它们中的每一个都将占用 logn(用于删除)+ logn(用于查找最小值)，因此总的来说，排序将占用 nlogn。

不过，我不知道如何调整它以进行插入。

编辑2: 为了使用插入来证明:找到列表中第i个最小的元素后，如果我将它插入到第i处会怎么样？例如使用上述过程找到第三个最小元素后，我可以将它插入到数据结构的第三个索引中。因此，最后我将得到一个排序的数据结构。

Answer 1

将您的问题简化为另一个问题将为您提供 O() 的上限，而不是下限。

另一方面，如果您可以使用问题的任何解决方案来实现具有众所周知下限的其他算法(有效地将问题减少到您的问题)，则可能会给出您正在寻找的下限.

---

回答:

正如其他人所建议的，您可以使用数据结构 S 来实现排序:

for i in range(input):
    Insert(S, input[i])
for i in range(input):
    x = Find_Smallest_Item(S)
    output[i] = x
    Delete(S, x)

对于大小为 N 的输入，此算法对您的三个操作中的每一个都进行 N 次调用。然而，我们知道任何通用排序算法必须有 O(N log N) 的最坏情况。

这意味着在某些情况下，上述排序中数据结构调用的平均时间为每次调用 O(log N)。由于这与渐近优于 log N 的任何 T() 不兼容，因此您有下限。

一些注意事项:

• 您的问题中描述的数据结构类型称为 priority queue .

• 由于您试图证明任何可能优先级队列的下限，您不能对实现做出假设。仅仅因为特定的数据结构为您提供了特定的 O() 性能，并不意味着一些完全不同的数据结构再好不过了。

• 有许多优先级队列数据结构满足所有调用的 O(log N)，因此这实际上是一个紧下限。