n 요소가있는 이항 힙의 이항 트리 수를 증명하십시오. O (log n)

Question

이 문장에 대한 좋은 증거를 찾는 데 문제가 있습니다. 바이너리 트리의 수를 결정하는 방법은 n의 이진 표현을 사용하여 결정됩니다. 예를 들어, 13 개의 요소는 이진수가 1101이고 2^{3} + 2^{2} + 2^{0}이므로 이항 나무가 필요하며 ln (13) +1 = 3.56> 3

나는 log (n)에 의해 그 경계를 증명하는 방법을 모른다. 일반적으로 log (n)과 관련된 알고리즘에 대한 많은 개념을 고수하고 있습니다.

누군가이 진술을 깨끗하고 간결하게 증명할 수 있습니까?

Answer 1

필요한 이항 트리의 수를 n의 이진 표현에서 1의 수로 나타내면 1의 수는 최대 (lg n) + 1 인 2 진수 수로 제한됩니다 여기서 lg n은 밑이 2 인 대수, 즉 lg n = ln (n)/ln (2))입니다. 그러면 O (log n)의 big-O 경계가 생깁니다.