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))。