从集合构造PriorityQueue的时间复杂度是多少？

  • Z时代
  • 2024-01-10
  • 分类：问答

Java的PriorityQueue构造函数与的复杂度是Collection多少？我使用了构造函数：

PriorityQueue(Collection<? extends E> c)

复杂度是O（n）还是O（n * log（n））？

回答：

PriorityQueue从集合（甚至是未排序的集合）初始化a的时间复杂度为O（n）。在内部，它使用一个过程siftDown()来就地“堆化”数组。（这在文献中也称为下推式）。

这是违反直觉的。似乎将元素插入到堆中是O（log n），所以插入n个元素会导致O（n log

n）复杂性。如果您一次插入一个元素，则为true。（在内部，使用插入单个元素可以完成此操作siftUp()。）

堆放单个元素肯定是O（log n），但是“窍门”

siftDown()在于，随着每个元素的处理，必须筛选通过的元素数量不断减少。因此，总复杂度不是n个元素乘以log（n）；它是筛选剩余元素的成本降低的n项之和。

请参阅此答案，还请参阅本文，该文章适用于数学。

以上是 从集合构造PriorityQueue的时间复杂度是多少？ 的全部内容， 来源链接： utcz.com/qa/411397.html

回到顶部