第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全，請及時綁定郵箱和手機立即綁定
已解決430363個問題，去搜搜看，總會有你想問的

如何構(gòu)建堆是O(N)時間復(fù)雜度？

如何構(gòu)建堆是O(N)時間復(fù)雜度？

如何構(gòu)建堆是O(N)時間復(fù)雜度？有人能幫助解釋如何構(gòu)建堆是O(N)復(fù)雜性嗎？將項插入堆是O(log n)，插入重復(fù)n/2次(剩余的是葉子，不能違反堆屬性)。因此，這意味著復(fù)雜性應(yīng)該是O(n log n)我想。換句話說，對于我們“堆化”的每一項，到目前為止，對于堆(這是logn級)，它可能必須對每個級別過濾一次。我遺漏了什么？
查看完整描述

3 回答

?
慕沐林林

TA貢獻2016條經(jīng)驗 獲得超9個贊

你的分析是正確的。然而，它并不緊。

要解釋為什么構(gòu)建堆是一種線性操作并不容易，最好讀一讀。

A 大分析可以看到的算法這里.

主要的想法是在build_heap算法實際heapify成本不是O(log n)所有元素。

什么時候heapify調(diào)用時，運行時間取決于在進程終止之前元素在樹中向下移動的距離。換句話說，它取決于堆中元素的高度。在最壞的情況下，元素可能會一直下降到葉級。

讓我們逐級計算所做的工作。

在最底層，2^(h)節(jié)點，但我們不調(diào)用heapify所有這些，所以工作是0。在水平的旁邊有2^(h ? 1)節(jié)點，每個節(jié)點可能向下移動一個級別。在第三層，從底部，有2^(h ? 2)節(jié)點，每個節(jié)點可能向下移動2個級別。

如您所見，并非所有堆化操作都是O(log n)，這就是為什么你要O(n).


查看完整回答
反對 回復(fù) 2019-07-04
  • 3 回答
  • 0 關(guān)注
  • 1891 瀏覽

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯(lián)系客服咨詢優(yōu)惠詳情

 幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

 公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號