Обзор поисковых структур данных - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:31:48Z

rollbackEdits.php mass rollback

185.100.85.24 в 04:30, 1 сентября 2022

2022-09-01T04:30:52Z

Oxygen3 в 14:40, 24 мая 2015

2015-05-24T14:40:55Z

Oxygen3 в 11:03, 24 мая 2015

2015-05-24T11:03:49Z

Внесённые изменения

Oxygen3 в 08:55, 24 мая 2015

2015-05-24T08:55:05Z

Oxygen3 в 09:18, 11 мая 2015

2015-05-11T09:18:03Z

Внесённые изменения

Oxygen3: Новая страница: «'''Поисковая структура данных''' - любая структура данных реализующая эффективный поиск к...»

2015-05-10T11:41:07Z

Новая страница: «'''Поисковая структура данных''' - любая структура данных реализующая эффективный поиск к...»

Новая страница

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

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

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

=== Время работы ===

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

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

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

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

Сравненим эффиктивность посиковых структур данных для реализации интерфейса [[Упорядоченное множество|упорядочего множества]].

{| class="wikitable"
|-
! rowspan="2" |
! colspan="2" | Insert
! colspan="2" | Delete
! colspan="2" | Search
! colspan="2" | Minimum
! colspan="2" | Maximum
! colspan="2" | Predecessor
! colspan="2" | Successor
! colspan="2" | Память
|-
! Сре- днее
! Худ- шее
! Сре- днее
! Худ- шее
! Сре- днее
! Худ- шее
! Сре- днее
! Худ- шее
! Сре- днее
! Худ- шее
! Сре- днее
! Худ- шее
! Сре- днее
! Худ- шее
! Сре- днее
! Худ- шее
|-
| Неотсортированный массив
| 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: #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(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: #ffffdd;" | <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: #ffffdd;" | <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: #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>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(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>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
|-
|[[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(n)</tex>
|-
|[[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(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>
| colspan="2" align="center" style="background: #ffffdd;" | <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: #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>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
|-
|[[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(n)</tex>
|-
|[[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: #ffffdd;" | <tex>O(n)</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: #ffffdd;" | <tex>O(\log k)</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 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>
|-
| [[Список с пропусками|Список с пропусками]]
| 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>
| 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: #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(n)</tex>
| align="center" style="background: #ffdddd;" | <tex>O(n \log n)</tex>
|-
|[[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(n)</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: #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>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
|}

← Предыдущая		Версия 16:31, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.		'''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.

← Предыдущая		Версия 04:30, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.		'''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.

← Предыдущая		Версия 08:55, 24 мая 2015
Строка 149:		Строка 149:

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

@@ Строка 38: / Строка 38: @@
 |-
 | Неотсортированный массив
-| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
+| align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
-| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
+| 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>
@@ Строка 56: / Строка 58: @@
 | colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 | colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
-| align="center" rowspan="2" | Аналогично массиву, но храним данные в [[Список|списке]].
+| align="center" rowspan="2" | Аналогично массиву, но храним данные в [[Список|списке]]. Можно хранить дополнительную информацию о вершинах, что позволит ускорить время работы операции delete.
 |-
 | Отсортированный [[Список|список]]