證明$ \ lceil \ lg n \ rceil -1 = \ lfloor \ lg n \ rfloor $


0

我最近遇到了一個問題:

顯示在任何nn元素堆中,最多有高度為hh的 $ \ lceil n / 2 ^ {h + 1} \ rceil $ 節點。

我尋找了一些解決方案,並找到了以下解決方案:Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} \rceil$

但是我對使用表達式的答案感到困惑: $$ \ lceil {\ log_2n} \ rceil-1 $$ 作為樹的高度。

但是,我很困惑,因為我早先證明了樹的高度是:

$$ \ lfloor \ lg n \ rfloor $$

即使我認為兩者相同,也只有在 $ \ lg n $ 返回一個十進制值而不是一個整數時,這才是正確的。

例如,考慮一個使用 $ n = 4 $ 的示例,該示例將失敗,因為:

$$ \ lfloor \ lg n \ rfloor \ le \ lg n \ le \ lceil \ lg n \ rceil $$

請幫助。

謝謝。

1

The expression $\lceil \log_2 n \rceil - 1$ for the height of a $n$-element heap is wrong. For $n=1$ the expression yields $-1$ instead of $0$, for $n=2$ it yields $0$ instead of $1$, etc...

In general, for $i \in \mathbb{N}^+$, an heap with $2^i$ nodes has height $i$ but $\lceil \log_2 2^i \rceil - 1 = i-1$.

The equality $\lceil \log_2n \rceil -1=\lfloor \log_2 n\rfloor$ is also wrong, as it can be seen by picking $n=2^i$ for any $i \in \mathbb{N}^+$.