Просмотр исходного текста страницы Алгоритмы и структуры данных

== Амортизационный анализ ==
* [[Амортизационный анализ]]
* [[Динамический массив]]
* [[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>
* [[Техника частичного каскадирования]] <tex>^\star</tex>
* [[Centroid decomposition]] <tex>^\star</tex>

== Запросы на отрезках ==

=== Корневая эвристика ===
* [[Статистики на отрезках. Корневая эвристика]]
* [[Корневая декомпозиция с операциями: get, insert, erase]]
* [[Алгоритм Мо]]

=== Дерево отрезков ===
* [[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
* [[Реализация запроса в дереве отрезков снизу]]
* [[Несогласованные поддеревья. Реализация массового обновления]]
* [[Многомерное дерево отрезков]]
* [[Сжатое многомерное дерево отрезков]]

== Дерево Фенвика ==
* [[Дерево Фенвика]]
* [[Встречное дерево Фенвика]]
* [[Дерево Фенвика для некоммутативных операций]]
* [[Многомерное дерево Фенвика]]

== Задача о наименьшем общем предке ==
* [[Сведение задачи LCA к задаче RMQ]]
* [[Сведение задачи RMQ к задаче LCA]]
* [[Метод двоичного подъема]]
* [[Решение RMQ с помощью разреженной таблицы]]
* [[Двумерная разреженная таблица]]
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
* [[Алгоритм Хьюи]]
* [[Heavy-light декомпозиция]]
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>
* [[Link-Cut Tree]]<tex>^\star</tex>
* [[Rake-Compress деревья]]<tex>^\star</tex>

== Хеширование ==
* [[Хеш-таблица]]
* [[Разрешение коллизий]]
* [[Хеширование кукушки]]
* [[Идеальное хеширование]]
* [[Перехеширование]]
* [[Фильтр Блума]]
* [[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>

== [[Динамическое программирование]] ==
=== Классические задачи динамического программирования ===
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о числе путей в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача о рюкзаке]]

=== Способы оптимизации методов динамического программирования ===
*[[Метод четырёх русских для умножения матриц]]
*[[Применение метода четырёх русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
*[[Meet-in-the-middle]]<tex>^\star</tex>
*[[Convex hull trick]]

=== Другие задачи ===
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о наибольшей подпоследовательности-палиндроме]]
*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
*[[Динамика по поддеревьям]]
*[[Level Ancestor problem]]

==  Криптографические алгоритмы ==
*[[RSA]]

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

== Алгоритмы во внешней памяти ==
* [[Алгоритмы во внешней памяти. Базовые конструкции]]

[[Категория: Алгоритмы и структуры данных]]