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)。しかし、2 番目の 2 番目の不等式が であることを意味するのhはΩ(log N)なぜですか? それが「log2(N) < h」であれば理解できますが、私の問題は「1」の「h+1」にあります。