Каталог алгоритмов

Все алгоритмы курса и разделы, где они разобраны. Ссылка открывает нужный раздел страницы. Файл создан скриптом common/build_navigation.py, не редактируйте его вручную.

Сортировки

• Сортировка пузырьком O(n²)
  Где разобран: Квадратичные сортировки, сортировка "Пузырьком"
• Сортировка выбором O(n²)
  Где разобран: Сортировка выбором
• Сортировка подсчётом O(n + k)
  Где разобран: Сортировка подсчётом
• Быстрая сортировка (QuickSort) O(n log n)
  Где разобран: "Быстрая сортировка" QuickSort
• Сортировка слиянием (MergeSort) O(n log n)
  Где разобран: Сортировка слиянием - MergeSort
• Пирамидальная сортировка (HeapSort) O(n log n)
  Где разобран: HeapSort - сортировка при помощи кучи

Поиск

• Двоичный поиск O(log n)
  Где разобран: Двоичный (бинарный) поиск, BinSearch, БинПоиск

Структуры данных

• Стек и очередь на массиве O(1) на операцию
  Где разобран: Реализация Стека и Очереди на базе массива
• Обходы бинарного дерева O(n)
  Где разобран: Обходы бинарного дерева
• Наименьший общий предок O(h)
  Где разобран: Наименьший общий предок
• Декартово дерево (treap) O(log n)
  Где разобран: Двоичные деревья поиска. Декартово дерево
• Дерево отрезков O(log n)
  Где разобран: Дерево отрезков; Дерево отрезков с отложенной операцией
• Корневая оптимизация (sqrt-декомпозиция) O(√n)
  Где разобран: 2. Корневая оптимизация
• Дерево Фенвика O(log n)
  Где разобран: Дерево Фенвика
• Рандомизированная куча O(log n)
  Где разобран: Рандомизированная куча минимума
• Дерево двоичного поиска O(h)
  Где разобран: Дерево двоичного поиска

Графы

• Поиск в глубину (DFS) O(V + E)
  Где разобран: Поиск в глубину - ПВГ (Depth First Search - DFS); Поиск в глубину - ПВГ (Depth First Search - DFS)
• Поиск в ширину (BFS) O(V + E)
  Где разобран: Поиск в ширину - ПВШ (Breadth First Search - BFS); Поиск в ширину - ПВШ (Breadth First Search - BFS)
• Топологическая сортировка O(V + E)
  Где разобран: Топологическая сортировка; Топологическая сортировка
• Эйлеров цикл O(E)
  Где разобран: Поиск эйлерова цикла в графе; Поиск эйлерова цикла в графе
• Гамильтонов цикл (перебор с возвратом) O(n!) в худшем случае
  Где разобран: Поиск гамильтонова цикла в графе
• Алгоритм Дейкстры O((V + E) log V)
  Где разобран: Алгоритм Дейкстры; Алгоритм Дейкстры
• Алгоритм Флойда–Уоршелла O(V³)
  Где разобран: Алгоритм Флойда
• Алгоритм Прима (минимальное остовное дерево) O(E log V)
  Где разобран: Алгоритм Прима
• Максимальное паросочетание (алгоритм Куна) O(V·E)
  Где разобран: Максимальное паросочетание
• Система непересекающихся множеств (DSU) почти O(1)
  Где разобран: Система непересекающихся множеств

Строки

• Поиск подстроки: алгоритм КМП O(n + m)
  Где разобран: Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм); Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм)
• Полиномиальный хеш строки O(n)
  Где разобран: Полиномиальные хеши на строках

Динамическое программирование

• Простейшие задачи динамического программирования O(n)
  Где разобран: Задача: Числа Фибоначчи

Числа

• Алгоритм Евклида (НОД) O(log n)
  Где разобран: Алгоритм Евклида для нахождения НОД; Наибольший общий делитель: алгоритм Евклида
• Решето Эратосфена O(n log log n)
  Где разобран: Решето Эратосфена для нахождения простых чисел
• Быстрое умножение длинных чисел (FFT) O(n log n)
  Где разобран: Быстрое умножение длинных чисел: FFT

Комбинаторика

• Комбинаторика: перестановки, размещения, сочетания —
  Где разобран: Число сочетаний

Рекурсия и перебор

• Рекурсия —
  Где разобран: Простейшая рекурсия (замена цикла)
• Ханойские башни O(2ⁿ)
  Где разобран: Ханойские башни: рекурсивное перемещение
• Перебор с возвратом (backtracking) зависит от задачи
  Где разобран: 2.3.2. Перебор с возвратом (backtracking)
• Перебор перестановок O(n!)
  Где разобран: 2.3.1. Перебор с отсечениями

Геометрия

• Выпуклая оболочка: алгоритм Грэхема O(n log n)
  Где разобран: Алгоритм Грэхема
• Выпуклая оболочка: алгоритм Джарвиса O(n·h)
  Где разобран: Алгоритм Джарвиса («заворачивание подарка»)
• Принадлежность точки многоугольнику O(n)
  Где разобран: Принадлежность точки многоугольнику (правило луча)

Рандомизированные алгоритмы

• Метод Монте-Карло —
  Где разобран: Статистическое моделирование (метод Монте-Карло)