Алгоритмы и структуры данных — различия между версиями
(→Поисковые структуры данных) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 8 промежуточных версий 6 участников) | |||
| Строка 40: | Строка 40: | ||
* [[2-3 дерево]] | * [[2-3 дерево]] | ||
* [[B-дерево]] | * [[B-дерево]] | ||
| + | * [[B+-дерево]] | ||
* [[Красно-черное дерево]] | * [[Красно-черное дерево]] | ||
* [[Декартово дерево]] | * [[Декартово дерево]] | ||
| Строка 53: | Строка 54: | ||
* [[Rope]]<tex>^\star</tex> | * [[Rope]]<tex>^\star</tex> | ||
* [[AA-дерево]]<tex>^\star</tex> | * [[AA-дерево]]<tex>^\star</tex> | ||
| − | + | * [[Техника частичного каскадирования]] <tex>^\star</tex> | |
| + | * [[Centroid decomposition]] <tex>^\star</tex> | ||
== Запросы на отрезках == | == Запросы на отрезках == | ||
| Строка 146: | Строка 148: | ||
* [[Интерполяционный поиск]] | * [[Интерполяционный поиск]] | ||
* [[Метод Фибоначчи]]<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]] | ||
== Связь между структурами данных == | == Связь между структурами данных == | ||
* [[Связь между структурами данных]] | * [[Связь между структурами данных]] | ||
| + | |||
| + | == Алгоритмы во внешней памяти == | ||
| + | * [[Алгоритмы во внешней памяти. Базовые конструкции]] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
Текущая версия на 19:33, 4 сентября 2022
Амортизационный анализ
Персистентные структуры данных
Приоритетные очереди
Система непересекающихся множеств
Поисковые структуры данных
- Упорядоченное множество
- Дерево поиска, наивная реализация
- АВЛ-дерево
- 2-3 дерево
- B-дерево
- B+-дерево
- Красно-черное дерево
- Декартово дерево
- Декартово дерево по неявному ключу
- Splay-дерево
- Взвешенное дерево
- Tango-дерево
- Рандомизированное бинарное дерево поиска
- Дерево ван Эмде Боаса
- Список с пропусками
- Fusion tree
- Сверхбыстрый цифровой бор
- Rope
- AA-дерево
- Техника частичного каскадирования
- Centroid decomposition
Запросы на отрезках
Корневая эвристика
- Статистики на отрезках. Корневая эвристика
- Корневая декомпозиция с операциями: get, insert, erase
- Алгоритм Мо
Дерево отрезков
Дерево Фенвика
Задача о наименьшем общем предке
- Сведение задачи LCA к задаче RMQ
- Сведение задачи RMQ к задаче LCA
- Метод двоичного подъема
- Решение RMQ с помощью разреженной таблицы
- Двумерная разреженная таблица
- Алгоритм Фарака-Колтона и Бендера (решение +/-1 RMQ с помощью метода четырех русских)
- Алгоритм Хьюи
- Heavy-light декомпозиция
- Алгоритм Шибера-Вишкина
- Алгоритм Тарьяна поиска LCA за O(1) в оффлайн
- Link-Cut Tree
- Rake-Compress деревья
Хеширование
Сортировки
Квадратичные сортировки
Сортировки на сравнениях
- Сортировка Шелла
- Сортировка кучей
- Быстрая сортировка
- Сортировка слиянием
- Cортировка слиянием с использованием O(1) дополнительной памяти
- Терпеливая сортировка
- Timsort
- Smoothsort
- Теорема о нижней оценке для сортировки сравнениями
Многопоточные сортировки
Другие сортировки
Сортирующие сети
Алгоритмы поиска
Динамическое программирование
Классические задачи динамического программирования
- Кратчайший путь в ациклическом графе
- Задача о числе путей в ациклическом графе
- Задача о расстановке знаков в выражении
- Задача о порядке перемножения матриц
- Задача о наибольшей общей подпоследовательности
- Задача о наибольшей возрастающей подпоследовательности
- Быстрый поиск наибольшей возрастающей подпоследовательности*
- Задача коммивояжера, ДП по подмножествам
- Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
- Задача о рюкзаке
Способы оптимизации методов динамического программирования
- Метод четырёх русских для умножения матриц
- Применение метода четырёх русских в задачах ДП на примере задачи о НОП
- Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
- Meet-in-the-middle
- Convex hull trick
Другие задачи
- Задача о расстоянии Дамерау-Левенштейна
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о наибольшей подпоследовательности-палиндроме
- Задача о наибольшей общей возрастающей последовательности
- Задача о наибольшей общей палиндромной подпоследовательности
- Динамическое программирование по профилю
- Динамика по поддеревьям
- Level Ancestor problem
