證明具有n個元素的二叉樹堆中的二叉樹數量最多爲O（log n）

Question

我無法找到此語句的良好證據。我知道如何確定二叉樹的數量是通過使用n的二進制表示來確定的。 例如，13個元素是二進制的1101，2^{3} + 2^{2} + 2^{0}所以需要3個二叉樹，並且ln（13）+ 1 = 3.56> 3

我只是不知道如何證明它由log（n）所界定。一般來說，我在涉及log（n）的算法中遇到很多概念。

有人可以提供一個簡潔明瞭的證明嗎？

Answer 1

如果所需的二項式樹的數量由n的二進制表示中的1的數量給出，那麼1的數量以二進制數字的數量爲界，其最多爲（lg n）+ 1（其中lg n是以2爲底的對數，即lg n = ln（n）/ ln（2））。所以這會給O（log n）的大O界限。