Как это бинарное дерево с n! листья имеют высоту омега (n log n)

Я наткнулся на это предложение, что бинарное дерево с n! листьями имеет высоту omega(n log n). Я не могу понять, как это возможно. Я понимаю, что высота бинарного дерева с n узлами равна log n <= h <= n, т.е. высота не менее log n (в случае complete binary tree), но я не вижу намека на то, как приведенное выше утверждение может быть верным или оказаться верным.

Какие-либо предложения?


algorithm depth binary-tree
person brain storm    schedule 20.01.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вы уже заявили, что нижняя граница для двоичного дерева с n узлами равна log n. Это хорошо известный факт (формула Стирлингса), что log(n!) приблизительно равен n log n. См., например, здесь, чтобы узнать о производных.

Дерево с n! листья и минимальная высота примерно 2n! узлы. Это дает log(2n!) = log 2 + log(n!) приблизительно log 2 + n log n, который находится в omega(n log n)

person Henry    schedule 20.01.2014
comment
не знал о формуле Стирлингса. посмотрю на это. но н! листья означали бы больше, чем n! узлы, как вы можете заменить, чем в журнале (n)? - person brain storm; 21.01.2014
comment
m листьев означает до 2m-1 узлов. - person Lior Kogan; 21.01.2014
comment
@LiorKogan: как насчет n! листья? - person brain storm; 21.01.2014
comment
Конечно, это будет до 2(n!)-1 узлов, то есть O(n!) узлов. - person Lior Kogan; 21.01.2014