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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:11:08Z

rollbackEdits.php mass rollback

185.220.100.252 в 06:09, 1 сентября 2022

2022-09-01T06:09:01Z

46.229.177.35: /* Тип */

2019-01-16T19:03:21Z

‎Тип

87.76.14.10: правка окончаний

2018-04-20T11:30:37Z

правка окончаний

Shersh: /* См. также */

2015-12-30T10:52:30Z

‎См. также

Shersh: /* Сравнение структур данных */

2015-06-10T08:31:37Z

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

Eadm: Отмена правки 47847 участника, ошибка

2015-06-06T18:42:48Z

Отмена правки 47847 участника, ошибка

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

Eadm: Отмена правки 47848 участника, ошибка

2015-06-06T18:42:17Z

Отмена правки 47848 участника, ошибка

Eadm в 18:37, 6 июня 2015

2015-06-06T18:37:15Z

Eadm: Новая статья

2015-06-06T18:36:26Z

Новая статья

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

← Предыдущая		Версия 16:11, 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 Майкл Наки].
−	\|}
−
	'''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.		'''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.

← Предыдущая		Версия 06:09, 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 Майкл Наки].
		+	\|}
		+
	'''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.		'''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.

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

@@ Строка 1: / Строка 1: @@
 '''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.
-Простейший, наиболее общий, но менее эффективный поисковой структурой является простая неупорядоченный последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемые в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур пропорциональна <tex>n</tex>, их построение окупится, даже если поступает лишь несколько запросов.
+Простейшей, наиболее общей, но менее эффективной поисковой структурой является простая неупорядоченная последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемые в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур пропорциональна <tex>n</tex>, их построение окупится, даже если поступает лишь несколько запросов.
 === Тип ===

@@ Строка 203: / Строка 203: @@
 ==См. также==
-*[[:Сортировка|Сортировка]]
+*[[Сортировка]]
-*[[:Поиск_подстроки_в_строке|Поиск подстроки в строке]]
+*[[Поиск подстроки в строке]]
-*[[:Приоритетные_кучи|Приоритетные кучи]]
+*[[Приоритетные очереди]]
 == Источники информации ==

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

@@ Строка 1: / Строка 1: @@
 '''Приоритетная очередь''' (англ. ''priority queue'') {{---}} это абстрактная структура данных на подобии стека или очереди, где у каждого элемента есть приоритет. Элемент с более высоким приоритетом находится перед элементом с более низким приоритетом. Если у элементов одинаковые приоритеты, они распологаются в зависимости от своей позиции в очереди. Обычно приоритетные очереди реализуются с помощью куч (англ. ''heap'').
 ==Операции==
 * find-min (find-max) - поиск элемента с наибольшим приоритетом
 * insert (push) - вставка нового элемента
@@ Строка 6: / Строка 8: @@
 * delete-min (delete-max) - удалить элемент с наибольшим приоритетом
 * merge - объединение двух приоритетных очередей
 ==Реализации==
 ===Наивная===
 В качестве наивной реализации мы можем взять обычный список и при добавлении нового элемента класть его в конец, а при запросе элемента с максимальным приоритетом проходить по всему списку. Тогда операция insert будет выполняться за <tex>O(1)</tex>, а extract-max (extract-min) за <tex>O(n)</tex>.
 ===Обычная===
 Для лучшей производительности приоритетные очереди реализуют с помощью куч, что позволяет выполнять операции вставки и удаления за <tex>O(\log n)</tex>. Использование специальных куч, таких как Фибоначчиева куча и спаренная куча, позволяет еще больше улучшить асимптотику некоторый операций.
 ==Виды приорететных очередей==
 {| class="wikitable"
 |-
@@ Строка 96: / Строка 102: @@
 |-
 |}
 ==Применение==
 * Алгоритм Дейкстры
@@ Строка 103: / Строка 110: @@
 * Поиск по первому наилучшему совпадению
 * Управление полосой пропускания
 ==Реализации в языках программирования==
 * Стандартная библиотека шаблонов (англ. ''STL'') в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.
@@ Строка 111: / Строка 119: @@
 * В Perl имеются реализации бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.
 * Go имеет пакет heap, в котором реализованы алгоритмы для работы с кучами.
 == Источники информации ==
 * [http://en.wikipedia.org/wiki/Heap_(data_structure)| Wikidedia {{---}} Heap (data structure)]