我无法为这个陈述找到一个很好的证明。我知道如何确定二叉树的数量是通过使用 n 的二进制表示来确定的。 比如13个元素二进制为1101，2^{3}+2^{2}+2^{0} 所以需要3棵二叉树，ln(13) + 1 = 3.56 > 3
我只是不知道如何证明它受 log(n) 的限制。总的来说，我在涉及 log(n) 的算法中纠结于许多概念
有人可以提供此声明的简洁明了的证明吗？
最佳答案
如果所需的二叉树的数量由 n 的二进制表示中 1 的数量给出，则 1 的数量受限于二进制数字的数量，最多为 (lg n) + 1(其中lg n 是以 2 为底的对数，即 lg n = ln(n)/ln(2))。所以这将给出 O(log n) 的大 O 界。
关于algorithm - 证明具有n个元素的二叉堆中二叉树的数量至多为O(log n)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21858490/