algorithm - 二叉堆高度

Question

在具有N节点且高度为的二叉堆中h：

1 + 2^1 + 2^2 + … + 2^(h-1) + 1 <= N <= 1 + 2^1 + 2^2 + … + 2^(h-1) + 2^h 
2^h <= N < 2^(h+1)
h  <= log2(N)  <  h+1

在最后一行： 第一个不等式意味着h是O(log N)。但是为什么第二个不等式意味着h是Ω(log N)？如果是“ log2(N) < h”，我会理解，但我的问题在于“ 1”中的“ h+1”。

Answer 1

从第二个不等式，你有

h + 1 > log(N) ↠ h > log(N) - 1 ,

所以，

h = Ω(log(N) - 1)。

然而，

log(N) - 1 = Θ(log(N)) ,

你可以使用传递规则

f(N) = Ω(g(N))和g(N) = Θ(h(N))意味着f(N) = Ω(h(N))。