403
правки
Изменения
Нет описания правки
Время работы, как и всех предыдущих функций, оценивается так же, и равно <tex>O(\log k)</tex>. Функция <tex> prev </tex> реализуется аналогично.
= Преимущества и недостатки =
== Преимущества ==
Главным преимуществом данной структуры является ее быстродействие. Асимптотически время работы операций дерева ван Эмде Боаса лучше, чем, например, у [[АВЛ-дерево|АВЛ]], [[Красно-черное дерево|красно-черных]], [[2-3 дерево|2-3]], [[Splay-дерево|splay]] и [[Декартово дерево|декартовых]] деревьев уже при небольшом количестве элементов. Конечно, из-за довольно непростой реализации возникают немалые постоянные множители, которые снижают практическую эффективность данной структуры. Но все же, при большом количестве элементов, эффективность дерева ван Эмде Боаса проявляется и на практике, что позволяет нам использовать данную структуру не только как эффективное дерево поиска, но и в других задачах. Например:
*cортировка последовательности из <tex> n </tex> чисел. Вставим элементы в дерево, найдем минимум и <tex> n - 1</tex> раз вызовем функцию <tex> next </tex>. Так как все операции занимают не более <tex> O(\log k)</tex> времени, то итоговая асимптотика алгоритма <tex> O(n \cdot \log k)</tex>, что даже лучше, чем [[Цифровая сортировка|цифровая сортировка]], асимптотика которой <tex> O(n \cdot k)</tex>.
*[[Алгоритм Дейкстры|алгоритм Дейкстры]]. Данный алгоритм с использованием [[Двоичная куча|двоичной кучи]] для поиска минимума работает за <tex> O(E \cdot \log V)</tex>, где <tex> V </tex> {{---}} количество вершин в графе, а <tex> E </tex> {{---}} количество ребер между ними. Если же вместо кучи использовать дерево ван Эмде Боаса, то релаксация и поиск минимума будут занимать уже не <tex> \log V </tex>, а <tex> \log k </tex>, и итоговая асимптотика этого алгоритма снизится до <tex> O(E \cdot \log k)</tex>.
== Недостатки ==
*
= Источники =
