algorithm - 证明具有 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 界限。