heapify堆的時間複雜度是多少

數據結構講義表明heapify的公式爲： T（n）≤T（2n/3）+Θ（1）。但是它說「通過主定理的情況2，T（n）= O（lg n），所以Heapify需要對數時間。」我真的不明白，a，b，c和d的值是什麼，爲什麼這個案例屬於定理的第二種情況，結果是O（lg n）？heapify堆的時間複雜度是多少

THX

主定理是這裏

來源

2017-10-10 Neil Ma

查看您的遞歸關係並將其與鏈接中給出的一般形式進行比較。你應該能夠從那裏推出'b，c，d'。 'a'不重要，因爲它只是一個加法常數。 – meowgoesthedog

@meowgoesthedog它不是[Master theorm]（https://en.wikipedia.org/wiki/Master_theorem_（analysis_of_algorithms））的鏈接，而是指向圖像的鏈接。 OP，請嘗試閱讀我評論中的鏈接。 –

所以，b是3/2，d是1.d

考慮，T（n）=在（N/B）+ N^C對於n> 1

有三種情況下（注b是日誌基地）

(1) if logb a < c, T(n)=Θ(n^c), 

(2) if logb a = c, T (n) = Θ(n^c log n), 

(3) if logb a > c, T(n) = Θ(n^(logb a)).

你的情況，你有

T(n) = T(2n/3) + n^0

我們可以說，

n^0 here because Θ(1) = Θ(n^0)

所以，

a = 1, b = 3/2, and c = 0

我們可以很容易地真理是

log3/2 1 = 0

因此，我們看到，我們需要用例2

logb a = c

所以，

T(n) = Θ(n^c log n) = Θ(n^0 log n) = Θ(log n)

望着那你貼

遵守情況2.

它說的形象，

Θ(n log n) if d = b

一般是，

Θ(n^i log n) if d = b^i 

d = b^i implies logb d = i

但對於澄清起見（希望）

d = 1並且b = 3/2（和如上所示），I = 0

所以，

d = B^i是true

我在這裏使用了不同的字母，但這與我上面描述的方式相同。我曾兩次使用過相同的東西，一旦使用了帖子中的字母，希望能爲你清理一些東西。無論您想如何看待它，您都會使用案例2.

來源

2017-10-11 05:40:05 RSon1234

heapify堆的時間複雜度是多少

回答

相關問題