heapify堆的时间复杂度是多少

问题描述：

数据结构讲义表明heapify的公式为： T（n）≤T（2n/3）+Θ（1）。但是它说 “通过主定理的情况2，T（n）= O（lg n），所以Heapify需要对数时间。”我真的不明白，a，b，c和d的值是什么，为什么这个案例属于定理的第二种情况，结果是O（lg n）？heapify堆的时间复杂度是多少

THX

主定理是这里

查看您的递归关系并将其与链接中给出的一般形式进行比较。你应该能够从那里推出'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.

heapify堆的时间复杂度是多少

相关推荐