C++中優先級隊列的時間複雜度

-1

創建堆佔用O（n）時間，而插入堆（或優先級隊列）需要log（n）時間。取n個輸入並將它們插入優先級隊列中，操作的時間複雜度是多少。 O（n）或O（n * log（n））。C++中優先級隊列的時間複雜度

此外，同樣的結果將保持清空整個堆的情況下（即n刪除），對不對？

讓我引導你到文檔：['std :: priority_queue']（http://en.cppreference.com/w/cpp/container/priority_queue） – Rakete1111

獲取一個算法教科書，它比隨機更好問題 –

如果您有一個大小爲n的數組，並且您想要一次從所有項目構建一個堆，Floyd算法可以用O（n）複雜度來完成。見Building a heap。這對應於接受容器參數的std::priority_queue constructors。

如果您有一個空的優先級隊列，您希望添加n項，一次一個，則複雜度爲O（n * log（n））。

所以，如果你有所有的項目將進入你的隊列之前，你建立它，那麼第一種方法將更有效率。您可以使用第二種方法 - 單獨添加項目 - 當需要維護隊列時：在一段時間內添加和刪除元素。

從優先隊列中刪除n項也是O（n * log（n））。

std::priority_queue的文檔包含所有操作的運行時複雜性。

2017-06-20 14:00:23

回答