如果在空的最小堆上，我们执行n任意插入和删除操作，（在最小堆中给定删除位置）。为什么插入O(1)和删除的摊销分析是O(log n)？
a) insert O(log n), delete O(1)
b) insert O(log n), delete O(log n)
c) insert O(1), delete O(1)
d) insert O(1), delete O(log n)
任何人都可以为我澄清吗？
5519 次
1 回答
9
根据您的问题和对评论的回复，我将假设一个二进制堆。
首先，插入的最坏情况是 O(log n)，而删除最小项的最坏情况是 O(log n)。这是从堆的树结构得出的。也就是说，对于 n 个项目的堆，树中有 log(n) 个级别。
插入涉及（逻辑上）将项目添加为树中最右下角的节点，然后将其“冒泡”到所需的级别。如果新项目小于根，那么它必须一直冒泡到顶部——所有 log(n) 级别。因此，如果将数字 10、9、8、7、6、5、4、3、2、1 插入最小堆，每次插入都会遇到最坏的情况。
删除最小元素涉及用最后一项替换最低项（根），然后将该项“筛选”到适当的位置。同样，这可能需要 log(n) 个操作。
那是最坏的情况。平均情况有很大不同。
请记住，在二叉堆中，一半的节点是叶子——它们没有子节点。因此，如果您以随机顺序插入项目，那么您插入的项目的一半时间将属于最低级别，并且没有“冒泡”可做。因此，插入操作的一半时间是 O(1)。在另一半中，其中一半将属于第二层。等等。您在插入时实际执行 log(n) 操作的唯一时间是当您插入的项目小于现有根项目时。那么，观察到的运行时行为很可能是插入是 O(1)。事实上，如果将排序数组插入到最小堆中，就会出现这种情况。也就是说，如果您要按顺序插入值 1、2、3、4、5、6、7、8、9、10。
从最小堆中删除最小的项目时，您从堆中取出最后一个项目并从顶部向下筛选。“一半时间”规则再次发挥作用，但这一次它对你不利。您从堆中取出的最后一项可能属于最低级别。所以你必须把它一直向下筛选，这需要 log(n) 操作。所有 log(n) 操作都需要一半的时间。剩下的一半你需要做除了其中一个之外的所有，等等。事实上，你必须筛选的最小级别数将取决于树的深度。例如，如果您的堆中包含三个以上的项目，那么您知道删除最小的项目将需要至少一个筛选操作，因为次低的项目总是在树的第二层。
事实证明，在平均情况下，插入二进制堆所需的时间远少于 O(log n) 时间。它可能更接近 O(1)。从二叉堆中移除更接近 O(log n) 的最坏情况。
于 2015-03-17T18:53:59.350 回答