问题描述
创建堆所需的时间为O(n)
,而插入到堆(或优先级队列)中的时间为O(log(n))
.
接收n个输入并将它们插入优先级队列,操作的时间复杂度是多少? O(n)或O(n * log(n)).
此外,如果也清空整个堆(即n个删除),结果将保持不变,对吧?
如果您有一个大小为n
的数组,并且想要一次从所有项目中构建一个堆,则Floyd的算法可以使用O(n)来做到这一点.复杂.请参见构建堆.这对应于接受容器参数的 std :: priority_queue构造函数.
如果您有一个空的优先级队列想要一次添加一个n
个项目,那么复杂度为O(n * log(n)).
因此,如果在构建队列之前已将所有项目放入队列,则第一种方法将更有效.当您需要维护队列时,可以使用第二种方法(分别添加项目):在一段时间内添加和删除元素.
从优先级队列中删除n
个项目也是O(n * log(n)).
std :: priority_queue 的文档包括所有操作的运行时复杂性./p>
Creating a heap takes O(n)
time while inserting into a heap (or priority queue) takes O(log(n))
time.
Taking n inputs and inserting them into the priority queue, what would be the time complexity of the operation? O(n) or O(n*log(n)).
Also, the same result would hold in case of emptying the entire heap too (i.e. n deletions), right?
If you have an array of size n
and you want to build a heap from all items at once, Floyd's algorithm can do it with O(n) complexity. See Building a heap. This corresponds to the std::priority_queue constructors that accept a container parameter.
If you have an empty priority queue to which you want to add n
items, one at a time, then the complexity is O(n * log(n)).
So if you have all of the items that will go into your queue before you build it, then the first method will be more efficient. You use the second method--adding items individually--when you need to maintain a queue: adding and removing elements over some time period.
Removing n
items from the priority queue also is O(n * log(n)).
Documentation for std::priority_queue includes runtime complexity of all operations.
这篇关于C ++中优先级队列的时间复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!