Докажите, что количество биномиальных деревьев в биномиальной куче с n элементами не больше O(log n)

Question

Докажите, что количество биномиальных деревьев в биномиальной куче с n элементами не больше O(log n)

У меня проблемы с поиском хорошего доказательства этого утверждения. Я знаю, как определить количество биномиальных деревьев, определяется с помощью двоичного представления n. Например, 13 элементов - это 1101 в двоичном виде, 2^{3}+2^{2}+2^{0}, поэтому требуется 3 биномиальных дерева, а ln(13) + 1 = 3.56 > 3

Я просто не знаю, как доказать его ограниченность log(n). В общем, я борюсь со многими понятиями в алгоритме, включающем log (n)

Может ли кто-нибудь предоставить ясное и краткое доказательство этого утверждения?

2

algorithm tree computer-science heap binomial-heap

Источник

user2399935 18 фев '14 в 15:40

1 ответ

Решение

Другие вопросы по тегам algorithm tree computer-science heap binomial-heap

user2566092 18 фев '14 в 17:55 2014-02-18 17:55 · Accepted Answer · 2014-02-18 17:55

Если количество требуемых биномиальных деревьев задается числом 1 в двоичном представлении n, то число 1 ограничивается количеством двоичных цифр, которое не более (lg n) + 1 (где lg n является логарифм по основанию 2, т.е. lg n = ln(n) / ln(2)). Так что это дало бы оценку big-O для O(log n).