我想知道Java对于元素的时间复杂程度是多少。PriorityQueue.Add()n
我知道插入单个元素的潜在更糟糕的情况是，但是我不清楚插入元素集合的时间复杂度是多少？O(log(n))n
我看过来自各种来源（没有证据）的声明，即构建元素的优先级队列堆的时间是，并且还看到过它是，这是有道理的，因为插入是，乘以时间确实等于nO(n)O(nlog(n))O(log(n))nO(nlog(n))
注意：我只对更糟糕的情况感兴趣，而不是摊销。
这个问题假设有一种逻辑方法来描述用元素填充数据结构（堆）的行为，这与简单地单独考虑x插入不同。nnlog(n)
我没有对输入做任何假设（例如输入值集的边界，或部分有序的输入）。
似乎插入n个元素应该是O（n log n）
Java PriorityQueue （Java Doc)
排队和去排队方法的 O（log n） 时间（提供、轮询、删除（） 和添加）
O（n） 表示 remove（Object） 和 contains（Object） 方法
O（1） 表示检索方法（透视、元素和大小）
这些时间复杂性似乎都是最坏的情况（wiki），除了.质疑边界是正确的，因为Java文档也指出了这个未绑定结构的扩展：.add()
未指定增长策略的详细信息
正如他们在文档中也指出的那样，优先级队列基于具有特定初始容量的数组。我假设增长将花费O（n）时间，那么这也是最坏的情况时间复杂度。.add()
要获得有保证的O（n log n）时间来添加n个元素，您可以声明n个元素的大小以省略容器的扩展：
PriorityQueue(int initialCapacity)
编辑：对于O（n）的主张，构造时间是正确的（如注释中@pjs所述）。此过程通常称为堆化，它处理预先存在的数组，该数组用于在 O（n） 时间内在其上构造二叉树。
在一般情况下是 O（N log N）。对于输入已排序的特殊情况，存在 O（N） 算法，但 中未提供此算法。java.util.PriorityQueue
