C ++中优先级队列的时间复杂度 [英] Time complexity of a Priority Queue in C++

问题描述

创建堆所需的时间为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 ++中优先级队列的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！