Ниже большой набор примеров алгоритмов, разбитых по категориям. Для каждой записи — название, краткое описание и асимптотика (в KaTeX).
Сортировка
- Пузырьковая сортировка — простая обменная, стабильная, худшая $O(n^2)$.
- Сортировка вставками — эффективна для почти отсортированных, худшая $O(n^2)$.
- Сортировка выбором — выбирает минимум/максимум, худшая $O(n^2)$.
- Сортировка слиянием — divide-and-conquer, стабильная, $O(n\log n)$.
- Быстрая сортировка (Quicksort) — средняя $O(n\log n)$, худшая $O(n^2)$.
- Пирамидальная сортировка (Heapsort) — $O(n\log n)$, невозм. дополнительная память $O(1)$.
- Counting sort — для целых в диапазоне, $O(n+k)$.
- Radix sort — по цифрам, $O(d(n+k))$.
- Bucket sort — распределительная, средняя $O(n+k)$.
Поиск
- Линейный поиск — $O(n)$.
- Бинарный поиск — отсортированный массив, $O(\log n)$.
- Интерполяционный поиск — лучше для равномерного распределения, среднее ~$O(\log \log n)$.
- Поиск в хеш-таблице — амортизированное $O(1)$.
Строковые алгоритмы
- KMP (Кнута-Морриса-Пратта) — поиск подстроки за $O(n+m)$.
- Rabin–Karp — хеширование, среднее $O(n+m)$.
- Бойер–Мур — сдвиги по плохому символу/хорошему суффиксу, эффективен на практике.
- Z-функция — строит Z-массив за $O(n)$.
- Суффиксный массив + LCP — построение $O(n\log n)$ или $O(n)$.
- Суффиксное дерево (Ukkonen) — $O(n)$.
Графовые алгоритмы
- BFS (поиск в ширину) — кратчайшие пути в невзвешенном графе, $O(V+E)$.
- DFS (поиск в глубину) — обход, топологическая сортировка, $O(V+E)$.
- Dijkstra — кратчайшие пути (неотриц. веса), $O((V+E)\log V)$ с кучей.
- Bellman–Ford — кратчайшие пути с отриц. ребрами, $O(VE)$.
- Floyd–Warshall — все-пары кратчайших путей, $O(V^3)$.
- Johnson — все-пары для разреженных графов, использует Dijkstra.
- Prim — MST с кучей, $O(E\log V)$.
- Kruskal — MST через сортировку ребер и DSU, $O(E\log E)$.
- Borůvka — параллельный подход к MST.
- Tarjan — компоненты сильно связности, $O(V+E)$.
- Kosaraju — SCC через два прохода DFS, $O(V+E)$.
- Топологическая сортировка — для DAG, $O(V+E)$.
- Edmonds–Karp — max flow (BFS), $O(V{E}^2)$.
- Dinic — max flow с уровнями, $O(E\sqrt{V})$ на практике.
- Push–relabel — max flow, эффективен на плотных графах.
- A* — эвристический поиск кратчайшего пути, зависит от эвристики.
Декомпозиция и структуры данных
- Union-Find (DSU) — объединение множеств, почти амортизированное $\alpha (n)$.
- Fenwick tree (BIT) — суммы/обновления, $O(\log n)$.
- Segment tree — диапазонные запросы и обновления, $O(\log n)$.
- Treap, AVL, Red–Black tree — сбалансированные BST, операции $O(\log n)$.
- B-tree/B+tree — структуры для диска, поиски $O(\log n)$.
- LRU cache (реализация c хеш + двусвязный список) — амортизированное $O(1)$.
- Bloom filter — приближенная проверка принадлежности, память/ошибка в $O(k)$.
Динамическое программирование и комбинаторика
- Задача 0/1 knapsack — DP $O(nW)$.
- Unbounded knapsack — вариация DP.
- Longest Common Subsequence (LCS) — классический DP $O(nm)$.
- Longest Increasing Subsequence (LIS) — DP $O(n^2)$ или patience + бинарный поиск $O(n\log n)$.
- Coin change — минимум монет DP $O(nm)$.
- Вектор состояния для DP по битам (bitmask DP) — $O(2^{n}n)$.
- Held–Karp — TSP DP по подмножествам, $O(n^2{2}^n)$.
Численные и алгебраические
- Евклид (GCD) — $O(\log \min (a,b))$.
- Расширенный Евклид — находит коэффициенты, $O(\log \min (a,b))$.
- Быстрое возведение в степень (fast pow) — $O(\log n)$.
- Сифр Эратосфена — простые до $N$, $O(N\log \log N)$.
- Миллер–Рабин — вероятный тест простоты (рандомизированный).
- Pollard's rho — факторизация случайного типа.
- FFT (БПФ) — умножение полиномов/чисел, $O(n\log n)$.
- Newton–Raphson — корни уравнений (итеративно).
- Kalman filter — оценка состояния линейной динамики.
Геометрические алгоритмы
- Graham scan — выпуклая оболочка, $O(n\log n)$.
- Jarvis march (gift wrapping) — выпуклая оболочка, $O(nh)$.
- Алгоритм «разделяй и властвуй» для ближайшей пары точек — $O(n\log n)$.
- Sweep line (шаблон) — пересечения отрезков, периметры, $O((n+k)\log n)$.
- Triangulation (Delaunay) — триангуляция.
Вероятностные и рандомизированные
- Randomized quicksort — ожидаемое $O(n\log n)$.
- Монте‑Карло — численное интегрирование/симуляции, ошибка ~$O(1/\sqrt{N})$.
- Las Vegas алгоритмы — всегда правильны, время случайно.
- Reservoir sampling — выбор $k$ элементов из потока длины неизвестной, $O(n)$ время, $O(k)$ память.
- Count–min sketch — приближённые частоты в стриме, память/погрешность в функциях параметров схемы.
Компрессия и кодирование
- Huffman coding — префиксный код минимальной средней длины.
- Arithmetic coding — более плотное кодирование.
- LZW — словарная компрессия.
- Run-length encoding — для подряд идущих повторов.
Криптография
- RSA — шифрование на основе факторизации, экспоненцирование по модулю.
- Diffie–Hellman — протокол обмена ключами.
- AES — симметричное блочное шифрование.
- SHA (хеш) — криптографические хеши.
- ElGamal, ECC-алгоритмы.
Поисковые и ранжирующие
- PageRank — ранжирование ссылок (итеративный метод).
- TF–IDF + cosine similarity — поиск релевантности текстов.
- Viterbi — наивероятнейший путь в HMM, $O(n{S}^2)$ (зависит от модели).
Оптимизация и эвристики
- Градиентный спуск — минимизация дифференцируемых функций.
- Стохастический градиентный спуск (SGD) — для больших данных.
- Newton / quasi-Newton (BFGS) — быстрое схождение при доступных градиентах/Гессианах.
- Симуляция отжига (Simulated annealing) — стохастическая глобальная оптимизация.
- Генетические алгоритмы — эволюционные приближения.
- Branch and bound — точный перебор с отсечениями.
Машинное обучение (кл. алгоритмы)
- k-NN — ленивый классификатор, время запроса $O(n)$.
- Decision trees — CART/ID3/C4.5.
- Random forest — ансамбль деревьев.
- SVM — опорные векторы (линейные/ядровые).
- k-means — кластеризация (итеративно).
- EM (Expectation–Maximization) — для скрытых переменных.
- PCA — метод главных компонент (SVD).
Потоки, большие данные и распределённые
- MapReduce — модель обработки больших данных (мап + редьюс).
- Spark RDD transformations — ленивые трансформации данных.
- Consistent hashing — распределение ключей между узлами.
- Paxos, Raft — консенсус в распределённых системах.
- Two-phase commit — распределённые транзакции.
Алгоритмы в играх и ИИ
- Minimax — для двух игроков, полный перебор.
- Alpha–beta pruning — отсечение в minimax.
- Monte Carlo Tree Search (MCTS) — для игр с большим деревом ходов.
Поиск оптимальных наближений и аппроксимации
- Жадный алгоритм для Set Cover — приближение $O(\log n)$.
- PTAS/FPTAS — приближающие схемы для NP‑трудных задач.
Другое важное
- Viterbi, Baum–Welch — HMM алгоритмы.
- Bellman equations — для динамического программирования и MDP.
- PageRank (итерации собственного вектора) — метод степенной итерации.
- Aho–Corasick — поиск множества шаблонов, $O(n+\text{total\_pattern\_len}+\text{occurrences})$.
- ZKW / Hungarian — алгоритмы для задач назначения (Hungarian $O(n^3)$).
- Simplex — линейное программирование (неполиномиальное в худшем случае, на практике быстро).
- Edmonds' blossom — максимальное паросочетание в общем графе, $O(n^3)$.
Если нужно, могу расширить любую из категорий и привести код/псевдокод, доказательства корректности или сравнение по применимости и памяти.