代码之家 › 专栏 › 技术社区 › James Wierzba

Java PriorityQueue(堆)插入n个元素的时间复杂度?[副本]

priority-queue heap time-complexity java

James Wierzba · 技术社区 · 7 年前

我想知道Java的时间复杂度是多少 PriorityQueue.Add() 是用于 n 元素。

我理解,单个元素可能会导致更糟糕的情况 O(log(n)) ,但我不清楚插入一个 n 元素?

我从各种来源(没有证据)看到过这样的说法,即构建优先级队列堆的时间是 n 它是元素 O(n) O(nlog(n)) ,这是有意义的,因为插入是 O(对数(n)) ,相乘 n 时间确实相等 O(nlog(n))

注:我只对更坏的情况感兴趣,而不是摊销。

这个问题假设有一种合乎逻辑的方式来描述填充数据结构(堆)的行为 n 元素,这与简单考虑不同 n x log(n) 单独插入。

我没有对输入进行任何假设(例如输入值集的边界或偏序输入)。

2 回复 | 直到 7 年前

gue 7 年前

似乎n个元素的插入应该是O(n log n)

Java优先级队列 ( Java Doc

O(log n)授予和取消授予方法(要约、投票、, 删除()并添加)

O(n)表示remove(Object)和contains(Object)方法

O(1)检索方法(peek、元素和大小)

这些时间复杂性似乎都是最糟糕的情况( wiki ),除了 .add() . 您对边界的质疑是正确的,因为Java文档还声明了此未绑定结构的扩展:

未指定增长政策的详细信息

正如他们在文档中所述,PriorityQueue基于具有特定初始容量的数组。我假设增长将花费O(n)时间,这也是 .添加() .

为了获得添加n个元素的保证O(n log n)时间,您可以声明n个元素的大小,以省略容器的扩展:

PriorityQueue(int initialCapacity)

编辑: 对于O(n)的索赔,施工时间是正确的(如@pjs在评论中所述)。此过程通常称为 heapify 并处理一个预先存在的数组,该数组用于在O(n)时间内在其上构建二叉树。

user207421 7 年前

它是 O(N log N) 在一般情况下。一 O(N) 算法适用于输入已排序的特殊情况,但在 java.util.PriorityQueue .

推荐文章

hackrack · 在javascript中,如何返回时间复杂度为O(n)的相同字母元素?

6 年前

data-oil · 在字符串列表中搜索的高效快捷方法

6 年前

user8514739 · 该算法查找长度为X的所有有序排列的算法复杂性

6 年前

Monk · 为什么大Oh不总是算法的最坏情况分析?

6 年前

Qasim Idrees · 三个嵌套相关循环的算法时间复杂度分析

6 年前

sdweldon · O(n)vs O(nlogn)时间复杂度

6 年前

Dazcii · 如何找到3个嵌套循环的复杂性

6 年前

Kodean · Java:循环字符串长度时间复杂性

6 年前

Hal · 循环的时间复杂度是多少?

6 年前

J. Doe · 按O(n)排序的列表中的数字平方?

6 年前