Обзор поисковых структур данных — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Поисковая структура данных''' - любая структура данных реализующая эффективный поиск к...»)
 
Строка 1: Строка 1:
'''Поисковая структура данных''' - любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.
+
'''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.
  
Простейший, наиболее общий, но менее эффективный поисковой структурой является простая неупорядоченный последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемные в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур, по крайней мере пропорционально n, они окупятся, даже если поступает лишь несколько запросов.
+
Простейший, наиболее общий, но менее эффективный поисковой структурой является простая неупорядоченный последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемые в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур, по крайней мере пропорционально n, они окупятся, даже если поступает лишь несколько запросов.
  
'''Статические''' поисковые структуры данных предназначены для ответа на запросы на фиксированной базе данных; '''Динамические''' поиковые структуры также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных.
+
'''Статические''' поисковые структуры данных предназначены для ответа на запросы на фиксированной базе данных; '''Динамические''' поисковые структуры также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных.
  
 
=== Время работы ===
 
=== Время работы ===
  
Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее для каждой операции. Лучшее время минимальное время работы алгоритма на каком-либо наборе. Худшее время наибольшее время.
+
Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее для каждой операции. Лучшее время {{---}} минимальное время работы алгоритма на каком-либо наборе. Худшее время {{---}} наибольшее время.
  
 
=== Используемая память ===
 
=== Используемая память ===
  
Параметр структуры данных, показывающий, сколько памяти ей требуется. Обычно затраты состовляют <tex>O(n)</tex>.
+
Параметр структуры данных, показывающий, сколько памяти ей требуется. Обычно затраты составляют <tex>O(n)</tex>.
  
 
=== Сравнение структур данных ===
 
=== Сравнение структур данных ===
  
Сравненим эффиктивность посиковых структур данных для реализации интерфейса [[Упорядоченное множество|упорядочего множества]].
+
Сравним эффективность поисковых структур данных для реализации интерфейса [[Упорядоченное множество|упорядоченного множества]]. Время работы методов <tex>Predecessor</tex> и <tex>Successor</tex> совпадает с временем работы <tex>Search</tex>.
 +
 
 +
<tex>n</tex> {{---}} количество хранимых чисел, каждое из которых представляется с помощью <tex>w</tex> битов.
  
 
{| class="wikitable"
 
{| class="wikitable"
Строка 23: Строка 25:
 
! colspan="2" | Delete
 
! colspan="2" | Delete
 
! colspan="2" | Search
 
! colspan="2" | Search
! colspan="2" | Minimum
 
! colspan="2" | Maximum
 
! colspan="2" | Predecessor
 
! colspan="2" | Successor
 
 
! colspan="2" | Память
 
! colspan="2" | Память
 
|-
 
|-
! Сре-<br>днее
+
! Среднее
! Худ-<br>шее
+
! style="background: #ffdddd;" | Худшее
! Сре-<br>днее
+
! Среднее
! Худ-<br>шее
+
! style="background: #ffdddd;" | Худшее
! Сре-<br>днее
+
! Среднее
! Худ-<br>шее
+
! style="background: #ffdddd;" | Худшее
! Сре-<br>днее
+
! Среднее
! Худ-<br>шее
+
! style="background: #ffdddd;" | Худшее
! Сре-<br>днее
 
! Худ-<br>шее
 
! Сре-<br>днее
 
! Худ-<br>шее
 
! Сре-<br>днее
 
! Худ-<br>шее
 
! Сре-<br>днее
 
! Худ-<br>шее
 
 
|-
 
|-
| Неотсортированный<br>массив
+
| Неотсортированный массив
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
+
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
|-
 
|-
| Отсортированный<br>массив
+
| Отсортированный массив
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
|-
 
|-
| Неотсортированный<br>[[Список|список]]
+
| Неотсортированный [[Список|список]]
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
|-
 
|-
| Отсортированный<br>[[Список|список]]
+
| Отсортированный [[Список|список]]
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
|-
 
|-
| [[Дерево поиска, наивная реализация|Дерево поиска,<br>наивная<br> реализация]]
+
| [[Дерево поиска, наивная реализация]]
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
Строка 104: Строка 70:
 
|-
 
|-
 
|[[АВЛ-дерево]]
 
|[[АВЛ-дерево]]
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
Строка 114: Строка 76:
 
|-
 
|-
 
|[[2-3 дерево]]
 
|[[2-3 дерево]]
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
Строка 124: Строка 82:
 
|-
 
|-
 
|[[B-дерево]]
 
|[[B-дерево]]
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
Строка 133: Строка 87:
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
|-
 
|-
|[[Красно-черное дерево|Красно-черное<br>дерево]]
+
|[[Красно-черное дерево]]
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
Строка 144: Строка 94:
 
|-
 
|-
 
| [[Декартово дерево]]
 
| [[Декартово дерево]]
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
Строка 161: Строка 103:
 
|-
 
|-
 
|[[Splay-дерево]]
 
|[[Splay-дерево]]
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
Строка 171: Строка 109:
 
|-
 
|-
 
|[[Tango-дерево]]
 
|[[Tango-дерево]]
| colspan="2" align="center" style="background: #ddffdd;" | <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: #ddffdd;" | <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: #ddffdd;" | <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: #ddffdd;" | <tex>O(\log \log n)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \log n)</tex>
Строка 180: Строка 114:
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
|-
 
|-
|[[Дерево ван Эмде Боаса|Дерево<br>ван Эмде Боаса]]
+
|[[Дерево ван Эмде Боаса]]
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log k)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log k)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log k)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
+
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(2^w)</tex>
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log k)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log k)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(2^k)</tex>
 
 
|-
 
|-
| [[Список с пропусками|Список с<br>пропусками]]
+
| [[Список с пропусками]]
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
Строка 207: Строка 131:
 
|-
 
|-
 
|[[Fusion tree]]
 
|[[Fusion tree]]
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
Строка 216: Строка 136:
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
|-
 
|-
|[[Сверхбыстрый цифровой бор|Сверхбыстрый<br> цифровой бор]]
+
|[[Сверхбыстрый цифровой бор]]
| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 
 
| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
 
| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
Строка 233: Строка 145:
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
|}
 
|}
 +
 +
==См. Также==
 +
 +
*[[:Сортировка|Сортировка]]
 +
*[[:Приоритетные_кучи|Приоритетные кучи]]
 +
 +
== Источники информации ==
 +
 +
* [[wikipedia:en:Search_data_structure|Wikidedia {{---}} Search data structure]]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Деревья поиска]]

Версия 12:18, 11 мая 2015

Поисковая структура данных — любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.

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

Статические поисковые структуры данных предназначены для ответа на запросы на фиксированной базе данных; Динамические поисковые структуры также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных.

Время работы

Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее для каждой операции. Лучшее время — минимальное время работы алгоритма на каком-либо наборе. Худшее время — наибольшее время.

Используемая память

Параметр структуры данных, показывающий, сколько памяти ей требуется. Обычно затраты составляют [math]O(n)[/math].

Сравнение структур данных

Сравним эффективность поисковых структур данных для реализации интерфейса упорядоченного множества. Время работы методов [math]Predecessor[/math] и [math]Successor[/math] совпадает с временем работы [math]Search[/math].

[math]n[/math] — количество хранимых чисел, каждое из которых представляется с помощью [math]w[/math] битов.

Insert Delete Search Память
Среднее Худшее Среднее Худшее Среднее Худшее Среднее Худшее
Неотсортированный массив [math]O(1)[/math] [math]O(n)[/math] [math]O(n)[/math] [math]O(n)[/math]
Отсортированный массив [math]O(n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math]
Неотсортированный список [math]O(1)[/math] [math]O(n)[/math] [math]O(n)[/math] [math]O(n)[/math]
Отсортированный список [math]O(n)[/math] [math]O(n)[/math] [math]O(n)[/math] [math]O(n)[/math]
Дерево поиска, наивная реализация [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(n)[/math]
АВЛ-дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math]
2-3 дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math]
B-дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math]
Красно-черное дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math]
Декартово дерево [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(n)[/math]
Splay-дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math]
Tango-дерево [math]O(\log \log n)[/math] [math]O(\log \log n)[/math] [math]O(\log \log n)[/math] [math]O(n)[/math]
Дерево ван Эмде Боаса [math]O(\log w)[/math] [math]O(\log w)[/math] [math]O(\log w)[/math] [math]O(2^w)[/math]
Список с пропусками [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(n)[/math] [math]O(n \log n)[/math]
Fusion tree [math]O(\log_{w} n)[/math] [math]O(\log_{w} n)[/math] [math]O(\log_{w} n)[/math] [math]O(n)[/math]
Сверхбыстрый цифровой бор [math]O(\log w)[/math] [math]O(w)[/math] [math]O(\log w)[/math] [math]O(w)[/math] [math]O(\log w)[/math] [math]O(w)[/math] [math]O(n)[/math]

См. Также

Источники информации