Найпопулярніші алгоритми

Добірка алгоритмів, які покривають левову частку задач на контестах. Якщо не знаєш, з чого почати розв'язок — переглянь колонку «Коли застосовувати»: часто сама умова задачі підказує інструмент.

Основи

Алгоритм	Складність	Коли застосовувати
Бінарний пошук	$O(\log n)$	Відсортований масив або монотонний предикат («якщо відповідь $x$ підходить, то і все більше за $x$ підходить») — половина задач типу «знайди мінімальне/максимальне $x$»
Бінарне піднесення до степеня	$O(\log n)$	Великі степені за модулем ($a^n \bmod m$), швидке множення матриць, $n$-те число Фібоначчі
Алгоритм Евкліда	$O(\log n)$	НСД/НСК двох чисел; розширена версія — діофантові рівняння й обернений елемент за модулем
Решето Ератосфена	$O(n \log \log n)$	Усі прості числа до $n$, найменші прості дільники, передобчислення для факторизації
Тернарний пошук	$O(\log n)$	Максимум/мінімум унімодальної функції (спершу зростає, потім спадає)

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

Алгоритм	Складність	Коли застосовувати
Дерево відрізків	$O(\log n)$ на запит	Суми/мінімуми/максимуми на відрізку з оновленнями елементів; найуніверсальніша структура — якщо сумніваєшся, бери її
Дерево Фенвіка	$O(\log n)$ на запит	Префіксні суми з оновленнями — простіше й швидше за дерево відрізків, коли операція оборотна (сума, XOR)
СНМ	~$O(1)$ на запит	Динамічна зв'язність: «чи в одній компоненті $a$ та $b$?» після серії об'єднань; основа алгоритму Крускала
Розріджена таблиця	$O(1)$ на запит	Мінімум/максимум/НСД на відрізку без оновлень — передобчислив раз, відповідаєш миттєво

Графи

Алгоритм	Складність	Коли застосовувати
BFS	$O(V+E)$	Найкоротші шляхи в незваженому графі; «мінімальна кількість кроків» у сітках і головоломках
DFS	$O(V+E)$	Компоненти зв'язності, пошук циклів, топологічне сортування, часи входу/виходу
Дейкстра	$O(E \log V)$	Найкоротші шляхи з однієї вершини, ваги невід'ємні (версія з купою для розріджених графів)
Беллман-Форд	$O(VE)$	Найкоротші шляхи з від'ємними вагами; детекція від'ємних циклів
Флойд-Воршелл	$O(V^3)$	Найкоротші шляхи між усіма парами, коли $V \lesssim 500$ — три вкладені цикли і готово
Топологічне сортування	$O(V+E)$	Порядок виконання із залежностями (DAG): збірка проєкту, переліки курсів, ДП на графі
Крускал / Прим	$O(E \log V)$	Мінімальне кістякове дерево: з'єднати все мінімальною сумарною вартістю
LCA через binary lifting	$O(\log n)$ на запит	Найнижчий спільний предок у дереві; відстані між вершинами дерева, підйом на $k$ предків
Потік Дініца	$O(V^2 E)$	Максимальний потік / мінімальний розріз; задачі про пропускні здатності й розбиття на дві множини
Алгоритм Куна	$O(VE)$	Максимальне парування у дводольному графі: «розподіли працівників по задачах»

Динамічне програмування

Алгоритм	Складність	Коли застосовувати
Рюкзак	$O(nW)$	Вибір підмножини предметів з обмеженням на сумарну вагу/вартість — і десятки замаскованих варіацій
НЗП	$O(n \log n)$	Найдовша зростаюча підпослідовність; задачі про «вкладені» об'єкти, мінімум ланцюгів покриття
ДП за профілем	$O(n \cdot 2^m)$	Замощення/розфарбування вузької сітки ($m \lesssim 20$): стан — бітова маска стовпця

Рядки

Алгоритм	Складність	Коли застосовувати
Префікс-функція (КМП)	$O(n)$	Пошук підрядка в рядку, періоди й бордери рядка, підрахунок входжень
Z-функція	$O(n)$	Ті самі задачі, що й КМП, але часто простіша в міркуваннях: $z[i]$ — довжина збігу з префіксом
Хешування рядків	$O(1)$ порівняння	Порівняння будь-яких підрядків за $O(1)$ після передобчислення; кількість різних підрядків; коли суфіксні структури — overkill
Ахо-Корасік	$O(\text{сумарної довжини})$	Пошук багатьох патернів у тексті одночасно (словник у боро + суфіксні посилання)
Суфіксний масив	$O(n \log n)$	Лексикографічні задачі на суфіксах: $k$-тий підрядок, найдовший спільний підрядок, кількість різних підрядків

Геометрія та інше

Алгоритм	Складність	Коли застосовувати
Опукла оболонка	$O(n \log n)$	Мінімальний опуклий многокутник навколо точок; перший крок багатьох геометричних задач
Замітаюча пряма	$O(n \log n)$	«Чи перетинається хоч одна пара відрізків» та інші задачі, де події обробляються зліва направо
Бінарне сортування пар / СНМ-офлайн	$O(n \cdot \alpha)$	Офлайн-відповіді на запити LCA, коли всі запити відомі заздалегідь
Числа Каталана	$O(n)$	Підрахунок: правильні дужкові послідовності, бінарні дерева, тріангуляції — якщо відповідь 1, 2, 5, 14, 42 — це вони
Біноміальні коефіцієнти за модулем	$O(1)$ після $O(n)$	Будь-який комбінаторний підрахунок за модулем — передобчисли факторіали й обернені

---

Не знайшов потрібного? Повний каталог зі ~160 статей — у бічній панелі, а маршрут для новачків — на головній.