Изменения

ПростейшийПростейшей, наиболее общийобщей, но менее эффективный эффективной поисковой структурой является простая неупорядоченный неупорядоченная последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемые в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур, по крайней мере пропорционально пропорциональна <tex>n</tex>, они окупятсяих построение окупится, даже если поступает лишь несколько запросов.

=== Тип === '''Статическиепоисковые структуры данных''' (англ. ''Offline search structures'' поисковые структуры данных ) предназначены для ответа на запросы на фиксированной базе данных; . '''Динамическиепоисковые структуры''' (англ. ''Online search structures' поисковые структуры ') также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных. Любую динамическую структуру данных можно сделать статической, если запретить вставку и удаление. Также если множество ключей известно, то можно его заранее упорядочить так, чтобы избежать худших случаев в поисках в структурах данных.

Сравним эффективность поисковых структур данных для реализации интерфейса [[Упорядоченное множество|упорядоченного множества]]. Время работы методов <tex>Predecessor</tex> и <tex>Successor</tex> совпадает с временем работы <tex>Search</tex>. <tex>n</tex> {{---}} количество хранимых чисел, каждое из которых представляется с помощью <tex>w</tex> битов.

! Среднее! Худшее! Среднее! Худшее! Среднее! Худшее! Среднее! Худшееcolspan="9" align="center" | Динамические структуры данных

| colspanalign="2center" style="background: #ddffdd;" | <tex>O(1)</tex>| align="center" style="background: #ddffddffdddd;" | <tex>O(1n)</tex>| colspanalign="2center" style="background: #ddffdd;" | <tex>O(1)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>

| colspan="2" align="center" style="background: #ffddddddffdd;" | <tex>O(n1)</tex>

| colspan="2" align="center" style="background: #ffddddddffdd;" | <tex>O(n1)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffddffdddd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffddffdddd;" | <tex>O(n)</tex>|-|[[Tango-дерево]]| colspan="2" align="center" style="background: #ddffddffffdd;" | <tex>O(\log \log n)</tex>| colspan="2" align="center" style="background: #ddffddffdddd;" | <tex>O(\log \log n)</tex>| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \log n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log kw)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log kw)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log kw)</tex>| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(2^kw)</tex>| align="center" | Cтруктура данных, представляющая собой [[Дерево поиска, наивная реализация|дерево поиска]], позволяющее хранить целые неотрицательные числа в интервале <tex>[0;2^w)</tex> и осуществлять над ними все соответствующие дереву поиска операции. Проще говоря, данная структура позволяет хранить <tex>w</tex>-битные числа.Особенностью этой структуры является то, что все операции выполняются за <tex>O(\log w)</tex>, что асимптотически лучше, чем <tex>O(\log n)</tex> в большинстве других деревьев поиска, где <tex>n</tex> {{---}} количество элементов в дереве.

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex> | align="center" style="background: #ffdddd;" | Вероятностная структура данных, основанная на нескольких отсортированных односвязных списках.Отсортированный связный список является простейшей структурой с временем поиска <tex>O\Theta(n )</tex>. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, помогает улучшить асимптотику до <tex>\Theta(\log (n))</tex>

|[[Сверхбыстрый цифровой бор]]| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>

==См. Такжетакже==

*[[:Сортировка|Сортировка]]*[[:Приоритетные_кучи|Поиск подстроки в строке]]*[[Приоритетные кучиочереди]]