СПРАВОЧНИК
Алгоритмы и структуры данных
Структуры, сортировки, поиск, графы — со сложностями
Справочник алгоритмов и структур данных со сложностью Big-O. Каждая запись описывает суть, асимптотику по времени и памяти и содержит короткий пример на Python. Темы сгруппированы: структуры данных, сортировки, поиск, обход графов, парадигмы проектирования и классические задачи.
Классические задачи 9
Быстрое возведение в степень
O(log n)Возведение в степень через двоичное разложение показателя.Задача о рюкзаке
O(n*W)Максимальная ценность предметов в рюкзаке ограниченной вместимости.Наибольшая возрастающая подпоследовательность
O(n log n)Самая длинная строго возрастающая подпоследовательность массива.НОД (алгоритм Евклида)
O(log(min(a, b)))Наибольший общий делитель через остатки от деления.Обратная польская запись (RPN)
O(n)Вычисление постфиксного выражения с помощью стека.Проверка на простоту
O(sqrt(n))Определение, является ли число простым, перебором делителей до корня.Решето Эратосфена
O(n log log n)Поиск всех простых чисел до n вычёркиванием кратных.Факториал
O(n)Произведение всех целых от 1 до n.Числа Фибоначчи
O(n)Каждое число — сумма двух предыдущих.Обход графов 8
Алгоритм A*
зависит от эвристикиПоиск кратчайшего пути с направляющей эвристикой.Алгоритм Беллмана-Форда
O(V * E)Кратчайшие пути с поддержкой отрицательных весов рёбер.Алгоритм Дейкстры
O((V + E) log V)Кратчайшие пути от вершины в графе с неотрицательными весами.Алгоритм Флойда-Уоршелла
O(V^3)Кратчайшие пути между всеми парами вершин.Поиск в глубину (DFS)
O(V + E)Обход графа вглубь до упора с возвратом назад.Поиск в ширину (BFS)
O(V + E)Обход графа по слоям с помощью очереди.Поиск компонент связности
O(V + E)Разбиение графа на группы взаимно достижимых вершин.Топологическая сортировка
O(V + E)Линейный порядок вершин ориентированного ациклического графа.Парадигмы 9
Бинарный поиск по ответу
O(n log R)Бинарный поиск по диапазону ответов с проверочной функцией.Бэктрекинг
часто экспоненциальнаяПолный перебор с отсечением заведомо неподходящих ветвей.Два указателя
O(n)Два индекса двигаются по массиву, заменяя вложенные циклы.Динамическое программирование
часто O(n*m)Решение задачи через переиспользование результатов подзадач.Жадные алгоритмы
часто O(n log n)На каждом шаге выбирается локально лучший вариант.Мемоизация
ускорение до O(числа состояний)Кеширование результатов функции, чтобы не вычислять их повторно.Разделяй и властвуй
часто O(n log n)Задача делится на части, решается рекурсивно и собирается.Рекурсия
зависит от задачиФункция вызывает саму себя, сводя задачу к меньшей.Скользящее окно
O(n)Окно фиксированной или переменной ширины движется по массиву.Поиск 3
Сортировки 9
Быстрая сортировка (quicksort)
среднее O(n log n)Разбивает массив опорным элементом и рекурсивно сортирует части.Поразрядная сортировка (radix)
O(d * (n + k))Сортирует числа по разрядам устойчивой сортировкой подсчётом.Пузырьковая сортировка
O(n^2)Соседние элементы меняются местами, пока массив не упорядочен.Сортировка вставками
O(n^2)Каждый элемент вставляется на своё место в отсортированную часть.Сортировка выбором
O(n^2)На каждом шаге находит минимум и ставит его в начало.Сортировка кучей (heapsort)
O(n log n)Строит кучу и последовательно извлекает минимум или максимум.Сортировка подсчётом (counting sort)
O(n + k)Считает частоты целых чисел в ограниченном диапазоне.Сортировка слиянием (merge sort)
O(n log n)Делит массив пополам, сортирует части и сливает их.Сортировка Шелла
O(n^1.5) типичноСортировка вставками с убывающим шагом сравнения.Структуры данных 16
AVL и красно-чёрное дерево
O(log n) гарантированноСамобалансирующиеся деревья поиска с гарантией O(log n).Граф (представления)
матрица O(V^2)Способы хранить граф: список смежности и матрица смежности.Двоичное дерево поиска (BST)
среднее O(log n)Дерево, где левое поддерево меньше узла, а правое больше.Двусвязный список
удаление O(1)Узлы со ссылками вперёд и назад; удаление узла за O(1).Дек
оба конца O(1)Двусторонняя очередь: вставка и удаление с обоих концов за O(1).Динамический массив
amortized O(1) pushМассив с авторасширением; добавление в конец амортизированно за O(1).Куча (heap)
вставка/извлечение O(log n)Двоичная куча для быстрого доступа к минимуму или максимуму.Массив
доступ O(1)Непрерывный блок памяти с доступом по индексу за константу.Множество
среднее O(1)Коллекция уникальных элементов с быстрой проверкой принадлежности.Очередь
enqueue/dequeue O(1)Структура FIFO: первым пришёл — первым вышел.Префиксное дерево (trie)
O(L) на операциюДерево для строк; операции зависят от длины ключа, а не от их числа.Приоритетная очередь
вставка/извлечение O(log n)Очередь, где элементы извлекаются по приоритету, а не по порядку прихода.Связный список
вставка O(1)Узлы со ссылкой на следующий; вставка по ссылке за O(1).Система непересекающихся множеств (DSU)
почти O(1) на операциюОбъединение множеств и проверка принадлежности почти за константу.Стек
push/pop O(1)Структура LIFO: последним пришёл — первым вышел.Хеш-таблица
среднее O(1)Отображение ключ-значение с доступом в среднем за O(1).