14
правок
Изменения
м
→Асимптотика
Докажем, что если глубина множества (т.е. его ранг) равна 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> вершин, что и требовалось доказать.
===Функция Аккермана===
|}
Функция, обратная функции Аккермана <tex>\alpha(m, n)</tex> равна минимальному <tex>i</tex> такому, что <tex>A \left (i, \left [\frac{m}{n} \right ] \right ) \geq \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функции функция для всех мыслимых любых значений , которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция get выполняется за константное время.
==Ссылки==
