PriorityQueue 的 addAll 方法的复杂度是多少。它是一次添加一个元素导致 O(n log n) 还是使用构建堆过程在 O(n) 时间内从无序元素中创建一个堆？
问问题
5105 次
3 回答
8
Javadoc似乎暗示它是从AbstractQueueaddAll继承的，它是作为一个序列实现的。
这使我相信复杂性在于O(mlogn)m 是插入集合的大小。
于 2013-01-14T01:15:44.050 回答
3
从优先队列
...此实现为入队和出队方法提供 O(log(n)) 时间...
所以你只能假设n log(n)。
然而——显然——这只是你可以假设的。根据您计划使用的具体实现，您可能会发现一些可以为您改善问题的技巧。
于 2013-01-14T01:17:34.897 回答
2
查看 OpenJDK，看起来 PriorityQueue 从 AbstractQueue 继承了 addAll 实现，它遍历集合并在每个元素上调用 add。
于 2013-01-14T01:16:12.323 回答