403
правки
Изменения
→Фибоначчиевы кучи
Поскольку <tex>\left\vert (-\varphi)^{-1} \right\vert < 1</tex>, то выполняются неравенства <tex dpi="160">\frac {(-\varphi)^{-n}} {\sqrt 5} < \frac {1} {\sqrt 5} < \frac {1} {2}</tex>. Таким образом, <tex>n</tex>-е число Фибоначчи равно <tex dpi="160">\frac {\varphi^{n}} {\sqrt 5}</tex>, округленному до ближайшего целого числа. Следовательно, <tex>F_n =\Theta(\varphi^n)</tex>.
}}
{{Лемма
|id=лемма4
|statement=Максимальная степень <tex>D(n)</tex> произвольной вершины в фибоначчиевой куче с <tex>n</tex> вершинами равна <tex>O(log(n))</tex>
|proof=
Пусть <tex>x</tex> {{---}} произвольная вершина в фибоначчиевой куче с <tex>n</tex> вершинами, и пусть <tex>k</tex> {{---}} степень вершины <tex>x</tex>. Тогда по [[#лемма2|доказанному выше]] в дереве, корень которого <tex>x</tex>, содержится не менее <tex>F_k</tex> вершин, что в свою очередь по [[#Лемма3|лемме]] не менее <tex>\varphi^{k}</tex>.
То есть
<tex>n \geqslant \varphi^{k}</tex>
Логарифмируя по основанию <tex>\varphi</tex>, получаем
<tex>log_{\varphi}n \geqslant k</tex>
Таким образом, максимальная степень вершины <tex>D(n)</tex> равна <tex>O(log(n))</tex>.
}}
