优先级队列消除了复杂性时间

Question

优先级队列消除了复杂性时间

sam*_*ner 28 java complexity-theory priority-queue time-complexity

remove()Java中Priority Queue类的函数的复杂性(大哦)是多少？我无法在任何地方找到任何记录,我认为它是O(n),考虑到你必须在删除之前找到该元素然后重新洗牌.但我看到其他人不同意并认为这是O(登录).有任何想法吗？

Answer 1

小智 33

这种混淆实际上是由你的"删除"功能引起的.在java中,有两个删除函数.

remove() - >这是删除头/根,它需要O(logN)时间.
remove(Object o) - >这是删除任意对象.查找此对象需要O(N)时间,删除它需要O(logN)时间.

@SeanL，我们不需要从零开始重建堆。删除根后恢复堆属性的算法也可以在删除任意对象后起作用。 (2认同)
关于乔治的评论。javadoc 说方法 **remove(Object)** 需要线性时间。> remove(Object) 和 contains(Object) 方法的线性时间；[参考](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html) (2认同)

Answer 2

Har*_*ari 27

删除的复杂性是O(N),因为contains的复杂性是O(N)(在java的优先级队列类中)

在您自己的优先级队列实现中,O(logN)的一种方法是维护一个辅助数据结构,如HashMap,它维护从优先级队列中的值到其在队列中的位置的映射.因此,在任何给定时间 - 您将知道任何值的索引位置.

请注意,此修改不会影响任何现有操作的运行时间 - 您只需要在heapify操作期间更新映射.

@novalain 不幸的是，Java API 没有公开一种通过索引访问优先队列中元素的方法，因此您必须使用自己构建的优先队列实现。 (3认同)
为什么从我们自己的实现中删除是 O(logN) 而不是 O(1)？我确定我遗漏了一些细节，但优先级队列只是一个从高优先级到低优先级排序的数据结构。如果它是使用链表实现的，并且我们知道索引，我们不能删除该元素并将前一个节点连接到下一个节点吗？ (3认同)
@ user3125693 不确定链接列表中的索引是什么意思。但是，如果您的意思是您持有指向要删除的节点的实际指针，那么，是的，删除是 O(1)。但是，通常您不会将链表用于优先级队列，因为您的插入/查找操作变成了 O(n)。虽然优先队列的更常见实现（例如二进制堆）为所有三个提供了 O(log n)：插入/查找/删除。 (2认同)
关于您提到的映射和自定义实现，我已经看到这只是通过向正在存储的项目类添加索引属性来完成的，并在 heapify 操作期间更新。如果索引处的项目是项目，则包含为真且 O(1)，而 remove(item) 将是 O(log n) 最坏的情况。非常适合寻路。 (2认同)

Answer 3

小智 6

根据Oracle文档：“实施说明：此实现为入队和出队方法（提供，轮询，remove（）和add）提供O（log（n））时间；为remove（Object）和contains（Object）提供线性时间）方法；以及检索方法的固定时间（窥视，元素和大小）。”

链接到Oracle文档

我认为他的意思是remove（object）不是remove（）第一个是O（n），后者是O（log n） (3认同)

除了缺少元素语义之外，“remove()”和“poll()”是相同的。删除特定项目（“remove(Object)”）的时间复杂度为“O(n)”。我认为这个问题不清楚，这也是一个有效的答案...... (2认同)

归档时间：	13 年前
查看次数：	30112 次
最近记录：	9 年，2 月前