14
правок
Изменения
Нет описания правки
* <tex>\alpha(m, n)</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций get и <tex>n</tex> элементов).
Докажем, что если глубина множества (т.е. его ранг) равна k, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с n элементами есть <tex>O(\log n)</tex>, а значит и время работы операции get является логарифмическим.
Будем доказывать данное свойство по индукции. Для k = 0 очевидно в множестве содержится 1 вершина. Пусть для множеств ранга k - 1 свойство выполняется. Как следует из ранговой эвристики, множество ранга k может получиться только при подвешивании множества ранга k - 1 к множеству ранга k - 1. Но тогда из предположения индукции в новом множестве действительно будет <tex>2^k</tex> вершин, что и требовалось доказать.
===Функция Аккермана===
