將k個元素插入包含n個元素的二進制堆的時間複雜度

-1

將k個新元素插入包含n個元素的二進制堆的時間複雜度是多少？我有約束，我需要在0（k + Log n）複雜度中插入k個元素。將k個元素插入包含n個元素的二進制堆的時間複雜度

提示：使用類似於堆構造的自下而上的方法。

來源

2014-05-08 user2454830

要插入1個元素，您需要記錄n次。所以要插入k個元素，它將是O（k log n）。 –

這個問題沒有簡單的答案。

二進制堆插入的平均複雜度爲O(1)，最壞的情況爲O(log N)。不管k如何，複雜度都會保持在這個範圍內，但是完成操作所花費的實際時間（不是時間複雜度;我相信你可能會混淆這些術語）將取決於實施方式，平臺和風的方式。

該關閉的事情在時間上的具體回答是，所用的時間充其量插入k元素是線性正比向和k在最壞的情況成正比log (x)集成從N到k+N。對於N顯着大於k，我們可以近似地將所需的時間估計爲比例至k log N。

欲瞭解更多信息，請參閱：http://en.wikipedia.org/wiki/Binary_heap

來源

2014-05-08 10:54:13 arman

那麼爲什麼答案比以下更復雜：O（k）對於平均值和O（k log（n））對於最壞情況？ –

由於'k log（N）'與第一次插入所用的時間成乘以'k'成正比，所以對於OP沒有指定的k << N是一個很好的近似值。實際的數量將與第一次插入的'log N'和第二次的'log（N + 1）'成比例，直到我們達到'log（N + k）'。所需的總時間因此是該範圍上的積分乘以「k」。 – arman

好的，所以我們有O（k log（n + k）） –

將k個元素插入包含n個元素的二進制堆的時間複雜度

回答

相關問題