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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
−
#перенаправление [[Дискретная математика, алгоритмы и структуры данных]]
+
== Амортизационный анализ ==
 +
* [[Амортизационный анализ]]
 +
* [[Динамический массив]]
 +
* [[Hashed Array Tree]]<tex>^\star</tex>
 +
* [[Список]]
 +
* [[Стек]]
 +
* [[Очередь]]
 +
* [[Дек]]
 +
* [[Мажорирующий элемент]]
 +
* [[Счетчик Кнута]]
 +
* [[Мастер-теорема]]<tex>^\star</tex>
 +
* [[List order maintenance]]<tex>^\star</tex>
 +
 
 +
== Персистентные структуры данных ==
 +
* [[Персистентные структуры данных]]
 +
* [[Персистентный стек]]
 +
* [[Персистентная очередь]]
 +
* [[Персистентный дек]]
 +
* [[Персистентная приоритетная очередь]]
 +
 
 +
== [[Приоритетные очереди]] ==
 +
* [[Двоичная куча]]
 +
* [[Биномиальная куча]]
 +
* [[Фибоначчиева куча]]
 +
* [[Левосторонняя куча]]
 +
* [[Тонкая куча]]
 +
* [[Толстая куча на избыточном счетчике]]
 +
* [[Куча Бродала-Окасаки]]<tex>^\star</tex>
 +
 
 +
== Система непересекающихся множеств ==
 +
* [[СНМ (наивные реализации) | Наивные реализации]]
 +
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
 +
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
 +
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex>
 +
 
 +
== [[Поисковые структуры данных]] ==
 +
* [[Упорядоченное множество]]
 +
* [[Дерево поиска, наивная реализация]]
 +
* [[АВЛ-дерево]]
 +
* [[2-3 дерево]]
 +
* [[B-дерево]]
 +
* [[Красно-черное дерево]]
 +
* [[Декартово дерево]]
 +
* [[Декартово дерево по неявному ключу]]
 +
* [[Splay-дерево]]
 +
* [[Взвешенное дерево]]
 +
* [[Tango-дерево]]<tex>^\star</tex>
 +
* [[Рандомизированное бинарное дерево поиска]]
 +
* [[Дерево ван Эмде Боаса]]
 +
* [[Список с пропусками]]
 +
* [[Fusion tree]]<tex>^\star</tex>
 +
* [[Сверхбыстрый цифровой бор]]
 +
* [[Rope]]<tex>^\star</tex>
 +
* [[AA-дерево]]<tex>^\star</tex>
 +
 
 +
== Дерево отрезков ==
 +
* [[Статистики на отрезках. Корневая эвристика]]
 +
* [[Корневая декомпозиция с операциями: get, insert, erase]]
 +
* [[Дерево отрезков. Построение]]
 +
* [[Реализация запроса в дереве отрезков сверху]]
 +
* [[Реализация запроса в дереве отрезков снизу]]
 +
* [[Несогласованные поддеревья. Реализация массового обновления]]
 +
* [[Многомерное дерево отрезков]]
 +
* [[Сжатое многомерное дерево отрезков]]
 +
 
 +
== Дерево Фенвика ==
 +
* [[Дерево Фенвика]]
 +
* [[Встречное дерево Фенвика]]
 +
* [[Дерево Фенвика для некоммутативных операций]]
 +
* [[Многомерное дерево Фенвика]]
 +
 
 +
== Хеширование ==
 +
* [[Хеш-таблица]]
 +
* [[Разрешение коллизий]]
 +
* [[Хеширование кукушки]]
 +
* [[Идеальное хеширование]]
 +
* [[Перехеширование]]
 +
* [[Фильтр Блума]]
 +
* [[Quotient filter]]<tex>^\star</tex>
 +
* [[Универсальное семейство хеш-функций]]
 +
* [[Расширяемое хеширование]]<tex>^\star</tex>
 +
 
 +
== [[Сортировки]] ==
 +
=== Квадратичные сортировки ===
 +
* [[Сортировка выбором]]
 +
* [[Сортировка пузырьком]]
 +
* [[Сортировка вставками]]
 +
=== Сортировки на сравнениях ===
 +
* [[Сортировка Шелла]]<tex>^\star</tex>
 +
* [[Сортировка кучей]]
 +
* [[Быстрая сортировка]]
 +
* [[Сортировка слиянием]]
 +
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
 +
* [[Терпеливая сортировка]]<tex>^\star</tex>
 +
* [[Timsort]]<tex>^\star</tex>
 +
* [[Smoothsort]]<tex>^\star</tex>
 +
* [[Теорема о нижней оценке для сортировки сравнениями]]
 +
 
 +
=== Многопоточные сортировки ===
 +
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex>
 +
* [[PSRS-сортировка]]<tex>^\star</tex>
 +
=== Другие сортировки ===
 +
* [[Поиск k-ой порядковой статистики]]
 +
* [[Поиск k-ой порядковой статистики за линейное время]]
 +
* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex>
 +
* [[Сортировка подсчетом]]
 +
* [[Цифровая сортировка]]
 +
* [[Карманная сортировка]]
 +
* [[Сортировка Хана]]<tex>^\star</tex>
 +
* [[Задача флага Нидерландов]]<tex>^\star</tex>
 +
* [[Блинная сортировка]]<tex>^\star</tex>
 +
 
 +
== Сортирующие сети ==
 +
* [[Сортирующие сети]]
 +
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 +
* [[Сортирующие сети для квадратичных сортировок]]
 +
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
 +
* [[Сеть Бетчера]]
 +
 
 +
== Алгоритмы поиска ==
 +
* [[Целочисленный двоичный поиск]]
 +
* [[Поиск в матрице]]<tex>^\star</tex>
 +
* [[Вещественный двоичный поиск]]
 +
* [[Троичный поиск]]
 +
* [[Поиск с помощью золотого сечения]]
 +
* [[Интерполяционный поиск]]
 +
* [[Метод Фибоначчи]]<tex>^\star</tex>
 +
 
 +
== Связь между структурами данных ==
 +
* [[Связь между структурами данных]]
 +
 
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]

Версия 13:45, 24 февраля 2017

Амортизационный анализ

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

Приоритетные очереди

Система непересекающихся множеств

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

Дерево отрезков

Дерево Фенвика

Хеширование

Сортировки

Квадратичные сортировки

Сортировки на сравнениях

Многопоточные сортировки

Другие сортировки

Сортирующие сети

Алгоритмы поиска

Связь между структурами данных

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_и_структуры_данных&oldid=60468»