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

SRT Алгоритм Двоичный поиск Находит границу «нет → да» в упорядоченных данных за log₂ n проверок. O(log n) 2 задачи SRT Приём Двоичный поиск по ответу Если проверить ответ легче, чем найти, и проверка монотонна, — ищем ответ делением пополам. O(log D · стоимость проверки) 2 задачи SRT Алгоритм Экспоненциальный поиск Шаги 1, 2, 4, 8, … пока не перескочишь, потом двоичный поиск: когда граница неизвестна или ответ близко. 2⌊log₂ i⌋ + 1 вопрос до позиции i 1 задача SRT Алгоритм Интерполяционный поиск Прикинуть место по значениям на краях: log log n проб на равномерных ключах и до n — на неудобных. ≈ log₂ log₂ n в среднем, n в худшем 1 задача SRT Алгоритм Троичный поиск Вершина унимодальной функции: сравнить две точки и отбросить часть отрезка. И почему золотое сечение лучше. O(log(L/ε)) вычислений функции 2 задачи SRT Алгоритм Простые сортировки Вставки, выбор и пузырёк: квадратичные, но вставки работают внутри библиотечных сортировок. O(n²) 2 задачи SRT Алгоритм Сортировка слиянием Делит пополам, сортирует половины и сливает: n log n на любом входе, устойчиво, годится для внешней памяти. O(n log n) 2 задачи SRT Алгоритм Timsort Находит готовые упорядоченные куски и сливает их: стек серий, галоп, powersort. O(n log n), на готовых данных O(n) 2 задачи SRT Алгоритм Внешняя сортировка Файл больше памяти: отсортированные прогоны, потом многопутевое слияние; замещающий выбор даёт прогоны длиной 2M. O(n log n) сравнений; 2n·(1 + ⌈log_k R⌉) чтений и записей строк 1 задача SRT Алгоритм Быстрая сортировка Разбиение вокруг опорного: в среднем n log n на месте, в худшем n² — и как от худшего защищаются. O(n log n) 2 задачи SRT Алгоритм Пирамидальная сортировка Куча прямо в массиве: n log n в худшем случае без лишней памяти — страховка introsort и сортировка ядра Linux. O(n log n) 2 задачи SRT Алгоритм Сортировка подсчётом и поразрядная Без сравнений: посчитать ключи или разложить их по цифрам — O(n + k) и O(d·n) вместо n log n. O(n + k) и O(d·(n + b)) 2 задачи SRT Приём Нижние границы сравнений Почему нельзя быстрее: подсчёт исходов и игра против судьи; сортировка, второй в турнире, минимум с максимумом, слияние. сортировка — ⌈log₂ n!⌉ сравнений 1 задача SRT Алгоритм Быстрый выбор k-й по величине без сортировки: разбиение и одна ветка вместо двух — O(n) в среднем, медиана медиан — всегда. O(n) в среднем 1 задача SRT Алгоритм Top-k: k лучших Куча из k с худшим наверху: поток читается один раз, почти каждый элемент отсеивается одним сравнением. O(n log k) 2 задачи SRT Алгоритм Перемешивание Фишера — Йетса Честная случайная перестановка за O(n): каждая из n! — с вероятностью 1/n!, и почему «обмен с любым» нечестен. O(n) 2 задачи

DS Структура данных Динамический массив Массив, который растёт сам: доступ по индексу за O(1), добавление в конец — за O(1) амортизированно. O(1) амортизированно на append 2 задачи DS Структура данных Связный список Узлы со ссылками на соседей: вставка и удаление у известного узла за O(1), путь к k-му — k шагов. O(1) у известного узла 2 задачи DS Структура данных Стек и очередь Стек: последним пришёл — первым ушёл. Очередь: первым пришёл — первым ушёл. Каждая операция — O(1). O(1) на push и pop, enqueue и dequeue 2 задачи DS Приём Монотонный стек Стек с упорядоченными значениями: ближайший больший элемент и наибольший прямоугольник за O(n). O(n) 2 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи DS Структура данных Хеширование кукушки Два гнезда на ключ, поиск — не больше двух проб; вставка выселяет жильцов. Работает до заполнения 1/2, с корзинами — до 98 %. поиск — не больше d проб в худшем; вставка — O(1) в среднем ниже порога 1 задача DS Структура данных Фильтр Блума Отвечает «точно нет» или «возможно, да» о членстве в множестве, тратя около 10 бит на элемент. O(k) 2 задачи DS Приём Корневая декомпозиция Блоки по √n: целые отвечают сразу, разрезанные — поклеточно; O(√n) там, где дерево отрезков не складывается. И порядок Мо. O(√n) на запрос; Мо — O(n√q) на все 1 задача DS Структура данных Персистентные структуры Каждое изменение — новая версия, старые живы; копируется только путь от корня. Медиана любого периода — разность двух версий. O(log n) на изменение и запрос 1 задача DS Структура данных Верёвка Текст кусками в листьях дерева: вставка и удаление в середине — путь к листу и один кусок; номер строки — по счётчикам в узлах. O(log n + C) на вставку, удаление, доступ 1 задача DS Структура данных Двоичная куча Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий. O(log n) 2 задачи DS Структура данных Двоичное дерево поиска Меньшие налево, большие направо: поиск, порядок и k-й элемент за высоту дерева — от log n до n. O(h): от O(log n) до O(n) 2 задачи DS Структура данных АВЛ-дерево Дерево поиска, где высоты веток у узла различаются не больше чем на 1: высота до ~1,44·log₂ n. O(log n) на поиск, вставку и удаление 2 задачи DS Структура данных Красно-чёрное дерево Дерево поиска с узлами двух цветов: высота до 2·log₂(n + 1), не больше трёх поворотов на операцию. O(log n) на поиск, вставку и удаление 2 задачи DS Структура данных Декартово дерево Ключ и случайный приоритет: глубина O(log n) в среднем, split и merge, массив с разворотом куска за O(log n). O(log n) в среднем на поиск, вставку, удаление, split и merge 1 задача DS Структура данных Список с пропусками Связный список с экспресс-линиями по броскам монетки: поиск и вставка за O(log n) в среднем, без поворотов. O(log n) в среднем на поиск, вставку, удаление и ранг 1 задача DS Структура данных B-дерево Дерево с сотнями ключей в узле-странице: поиск среди миллиарда ключей читает пять страниц. O(log n) сравнений, O(log_B n) чтений страниц 2 задачи DS Структура данных Косое дерево После каждого запроса ключ поднимается в корень парами поворотов: частые ключи сами собираются наверху, амортизированно O(log n). O(log n) амортизированно на операцию; одна операция — до O(n) 1 задача DS Структура данных Бор (префиксное дерево) Слова с общим началом идут общим путём: поиск слова и всех продолжений — за длину запроса. O(L) на вставку и поиск слова длины L 2 задачи DS Структура данных Система непересекающихся множеств Слить два множества и узнать, в одном ли элементы, — почти за O(1): лес ссылок на родителя и два приёма. O(α(n)) 2 задачи DS Структура данных Дерево отрезков Минимум, максимум и сумма на любом отрезке с изменениями на ходу: оба действия за O(log n). O(log n) на запрос и на изменение 2 задачи DS Структура данных Дерево Фенвика Суммы на префиксе с изменениями за O(log n) в одном массиве: блоки длиной в младшую единицу номера. O(log n) на сумму префикса и на изменение 2 задачи DS Структура данных Разреженная таблица Минимум любого отрезка за O(1) после O(n log n) подготовки: два перекрывающихся блока длиной 2^k. O(1) на запрос, O(n log n) на построение 2 задачи DS Структура данных LRU-кэш Словарь плюс двусвязный список: get и put за O(1), выселяется тот, к кому дольше всех не обращались. O(1) на get и put 2 задачи

GRA Приём Как хранить граф Матрица, списки, массив рёбер и CSR: память, скорость и какие вопросы каждая запись задаёт дёшево. соседи вершины: O(n) у матрицы, O(deg) у списков и CSR; есть ли ребро: O(1) у матрицы, O(deg) у списков 2 задачи GRA Алгоритм Поиск в ширину Обходит граф слоями и находит пути с наименьшим числом рёбер за O(V + E). O(V + E) 2 задачи GRA Алгоритм Поиск в глубину Идёт вглубь, отмечает вход и выход каждой вершины и по ним находит циклы за O(V + E). O(V + E) 2 задачи GRA Алгоритм Топологическая сортировка Выстраивает вершины графа без циклов так, чтобы все рёбра смотрели вперёд, за O(V + E). O(V + E) 2 задачи GRA Алгоритм Компоненты сильной связности Группы вершин, где из любой можно дойти до любой: Тарьян за один обход, Косараю за два, O(V + E). O(V + E) 2 задачи GRA Алгоритм 2-SAT Условия «a или b»: граф следствий, компоненты сильной связности и ответ за O(n + m); на настоящих нотах. O(n + m) 1 задача GRA Алгоритм Мосты и точки сочленения Улицы и перекрёстки, без которых граф распадается: один поиск в глубину с числами tin и low, O(V + E). O(V + E) 2 задачи GRA Алгоритм Алгоритм Дейкстры Кратчайшие пути от одной вершины во взвешенном графе без отрицательных рёбер. O((V + E) log V) 3 задачи GRA Алгоритм A* Дейкстра с подсказкой «сколько ещё до финиша»: волна тянется к цели, а путь остаётся кратчайшим. O((V + E) log V) 2 задачи GRA Алгоритм Двунаправленный поиск Две волны Дейкстры навстречу друг другу: где остановиться, сколько экономится и как подружить с A*. O((V + E) log V) 2 задачи GRA Алгоритм Алгоритм Беллмана — Форда Кратчайшие пути с отрицательными рёбрами и поиск отрицательного цикла: V раундов по всем рёбрам. O(V · E) 2 задачи GRA Алгоритм Алгоритм Флойда — Уоршелла Кратчайшие пути между всеми парами вершин за O(n³): динамика по разрешённым пересадкам. O(n³) 2 задачи GRA Алгоритм Алгоритм Джонсона Кратчайшие пути при отрицательных весах: потенциалы Беллмана — Форда, перевзвешивание и Дейкстра от каждой вершины. O(V·E + V·(V + E) log V) 2 задачи GRA Алгоритм Иерархии сжатия Предподсчёт навигаторов: сжимаем неважные перекрёстки в ярлыки и ищем путь двумя волнами вверх. O((V + E′) log V) 1 задача GRA Алгоритм Минимальное остовное дерево Самая дешёвая сеть, связывающая все вершины: Борувка, Краскал и Прим — три способа применить одну лемму. O(E log V) 2 задачи GRA Алгоритм Максимальный поток Наибольший поток из истока в сток и узкое место сети: Форд — Фалкерсон, Эдмондс — Карп, теорема о разрезе. O(V E²) 2 задачи GRA Алгоритм Алгоритм Диница Наибольший поток фазами: слоистая сеть, блокирующий поток, указатели; O(V²E), а в единичных сетях O(E√V). O(V² E) 2 задачи GRA Алгоритм Минимальный разрез Самая дешёвая граница в графе: вырезает предмет на фотографии и находит слабое место сети. O(m n² |C|) 2 задачи GRA Алгоритм Раскраска графа Соседям — разные цвета: жадный способ, порядок «наименьший последним», DSatur и точный перебор на картах и расписаниях. O(V + E) — жадно в данном порядке и «наименьший последним»; O((V + E) log V) — DSatur с кучей 2 задачи GRA Алгоритм Паросочетания в двудольном графе Наибольшее число пар в двудольном графе: Кун, Хопкрофт — Карп, теоремы Кёнига и Холла. O(E √V) 2 задачи GRA Алгоритм Венгерский алгоритм Кому какую работу при наименьшей общей цене: потенциалы, честные пары и увеличивающие пути за O(n³). O(n³) 2 задачи GRA Алгоритм Поток наименьшей стоимости Поток с наименьшей суммарной ценой: круги отрицательной стоимости, кратчайшие пути с потенциалами, транспортная задача 1930 года. O(F · E log V) 2 задачи GRA Алгоритм Эйлеров путь Пройти каждое ребро ровно раз: правило нечётных вершин и алгоритм Хирхольцера за O(E). O(V + E) 3 задачи GRA Алгоритм Наименьший общий предок Общий предок двух вершин дерева: двоичный подъём за O(log n), обход Эйлера за O(1), Тарьян офлайн. O(log n) на запрос 2 задачи GRA Алгоритм Тяжёлые пути Запросы на путях дерева: тяжёлые пути режут любой путь на O(log n) отрезков массива под деревом отрезков. O(log² n) на запрос 1 задача GRA Алгоритм Центроидная декомпозиция Делим дерево центроидами: log₂ n уровней, и ближайшая отмеченная вершина — за O(log n) после каждой отметки. O(log n) на отметку и на вопрос 1 задача GRA Алгоритм Задача коммивояжёра Кратчайший объезд всех точек: ближайший сосед, 2-opt со списками соседей, Or-opt, оценка Хелда — Карпа. NP-трудна; точно O(2ⁿ · n²) 2 задачи GRA Алгоритм PageRank Важность страниц по ссылкам: случайный читатель, степенной метод и коэффициент затухания. O((V + E) · log(1/ε) / log(1/d)) 1 задача

STR Алгоритм Наивный поиск подстроки Образец прикладывают к каждой позиции текста: n · m сравнений в худшем случае, около n — на обычном тексте. O(n · m) 2 задачи STR Алгоритм Префикс-функция и КМП Все вхождения образца за O(n + m) без шагов назад по тексту; префикс-функция находит и период строки. O(n + m) 2 задачи STR Алгоритм Z-функция Сколько букв от каждой позиции совпадает с началом строки — за O(n); поиск, периоды и повторы подряд. O(n) 2 задачи STR Приём Полиномиальный хеш Хеш любого куска строки за O(1) из хешей начал: сравнение подстрок, окна, общие начала — с оценкой вероятности ошибки. O(n) подготовка, O(1) хеш куска 2 задачи STR Алгоритм Алгоритм Рабина — Карпа Хеш окна катится по тексту, буквы сравниваются только при совпадении хеша; тысячи образцов — за один проход. O(n + m) в среднем 1 задача STR Алгоритм Алгоритм Ахо — Корасик Все вхождения тысяч слов за один проход: бор из слов плюс ссылки отказа, как у префикс-функции. O(n + Σ|wᵢ| + z) 1 задача STR Алгоритм Бойер — Мур Сравнивает справа налево и перепрыгивает буквы: на длинных образцах читает лишь малую часть текста. O(n + m) 2 задачи STR Структура данных Суффиксный массив Отсортированные хвосты текста: поиск двоичным поиском, повторы и число разных кусков по соседям. O(n log n) 2 задачи STR Структура данных Суффиксный автомат Все подстроки текста в графе из меньше чем 2n состояний: склейка фразы из кусков «Онегина» за один проход. O(n) 2 задачи STR Алгоритм Преобразование Барроуза — Уилера Перестановка, которая сжимает текст и служит по нему указателем: обратный поиск, LF и выравнивание ридов. O(m) на подсчёт образца, O(m + k·s) на k мест 2 задачи STR Алгоритм Алгоритм Манакера Все палиндромы строки за O(n): зеркало внутри самого правого палиндрома; фаги и палиндромы в их ДНК. O(n) 2 задачи STR Алгоритм Редакционное расстояние Наименьшее число вставок, удалений и замен между двумя строками — таблица m × n и выравнивание по ней. O(m · n) 2 задачи STR Структура данных BK-дерево Все пароли в одной-двух правках от данного: неравенство треугольника отрезает целые ветви — и где оно перестаёт помогать. O(N · глубина) на построение 1 задача STR Алгоритм Diff Майерса Кратчайший сценарий удалений и вставок строк за O((N + M) · D): волны по числу правок. Так работает git diff. O((N + M) · D) 1 задача STR Алгоритм Код Хаффмана Оптимальный префиксный код по частотам знаков: два самых редких дерева склеиваются, пока не останется одно. O(n log n) 2 задачи STR Алгоритм LZ77 и LZW Повторы — ссылками назад (LZ77) или номерами фраз растущего словаря (LZW); хеш-цепочки, уровни, окно. O(n · chain) 2 задачи

DP Приём Динамическое программирование Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице. состояния × переходы 2 задачи DP Алгоритм Задача о рюкзаке Лучший набор вещей под ограничение по весу: таблица n × W и путь по ней назад. O(n·W) 3 задачи DP Алгоритм Наибольшая возрастающая подпоследовательность Самая длинная растущая цепочка элементов в исходном порядке: пасьянс и двоичный поиск за n log n. O(n log n) 2 задачи DP Алгоритм Наибольшая общая подпоследовательность Самая длинная цепочка, общая двум последовательностям: таблица m × n, путь назад, Хиршберг. O(m · n) 2 задачи DP Приём Динамика на отрезках Состояние — отрезок [i, j], переход — где его разрезать: дерево поиска, порядок умножения матриц, распил. O(n³) 2 задачи DP Приём Динамика на деревьях Ответ поддерева — из ответов детей: проход от листьев к корню, а для всех корней сразу — перерасчёт с корня. O(n) 2 задачи DP Приём Динамика по маскам Состояние — подмножество, записанное битами числа: точный коммивояжёр, назначения, раскладки по профилю. O(2ⁿ · n²) для коммивояжёра 2 задачи DP Приём Динамика по цифрам Счастливые билеты в любом диапазоне за проход по цифрам: 55 252 из миллиона и любой из 10¹⁸ — за миллисекунду. O(D · 10 · S) 2 задачи DP Приём Convex hull trick Минимум прямых вместо перебора: 1776 тестов каталога по запускам песочницы — и квадратичная динамика становится линейной. O(n) 2 задачи DP Приём Оптимизации Кнута и «разделяй и властвуй» 45 тысяч городов на карте по классам населения: 3,5 млн вычислений вместо пяти миллиардов — потому что лучший разрез монотонен. O(k · n log n) 2 задачи DP Алгоритм Seam carving Сужает фото, вырезая пиксельные швы наименьшей энергии; каждый шов — динамика по таблице. O(W·H) на шов, O(k·W·H) на k швов 2 задачи DP Алгоритм Алгоритм Витерби Самая правдоподобная цепочка скрытых состояний по шумным наблюдениям: улицы по GPS, участки генома, сообщение по битам. O(T · S²) 2 задачи DP Алгоритм Выравнивание последовательностей Лучшее сопоставление двух последовательностей с очками за замены и пропуски: целиком, по кускам и с проверкой на случайность. O(m · n) 2 задачи DP Алгоритм Красивый перенос строк Жадный перенос против всего абзаца сразу: кратчайший путь по местам разрыва, как в TeX. O(n·L) 2 задачи

PAR Приём Жадные алгоритмы Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать. обычно O(n log n): сортировка или куча 2 задачи PAR Приём Перебор с возвратом Строить решение по шагу, сразу проверять и отступать из тупика: судоку, ферзи, раскраски. O(bᵈ) в худшем случае 2 задачи PAR Приём Ветви и границы 38 аэропортов, где из каждого прямой рейс в каждый: оценка раскраской сжимает перебор с миллиона узлов до 242. экспоненциальное в худшем случае 1 задача PAR Приём Разделяй и властвуй Разрезать, решить части так же, склеить; сколько это стоит — по уровням дерева рекурсии и основной теореме. T(n) = a·T(n/b) + f(n) 2 задачи PAR Алгоритм Ближайшая пара точек Две ближайшие точки из n за n log n: разрез, полоса шириной 2d и семь соседей; сеткой — за n в среднем. O(n log n) 2 задачи PAR Приём Встреча посередине Перебрать две половины по отдельности и встретиться в отсортированной таблице: 2·2^(n/2) шагов вместо 2ⁿ. O(2^(n/2) · n) 2 задачи

NUM Алгоритм Алгоритм Евклида Наибольший общий делитель двух чисел за O(log n) делений с остатком. O(log min(a, b)) 2 задачи NUM Алгоритм Быстрое возведение в степень aⁿ за O(log n) умножений: квадраты по битам показателя. O(log n) умножений 2 задачи NUM Алгоритм Решето Эратосфена Все простые до n за O(n log log n): вычёркиваем кратные каждого простого, начиная с его квадрата. O(n log log n) 2 задачи NUM Алгоритм Тест Миллера — Рабина Простота числа за k возведений в степень: основания-свидетели ловят составное, лжецов не больше четверти. O(k log³ n) 2 задачи NUM Алгоритм ρ-алгоритм Полларда Делитель p числа n за ~√p шагов: цикл по модулю неизвестного p, черепаха и заяц, НОД. O(√p) умножений по модулю n 1 задача NUM Алгоритм Китайская теорема об остатках Число по остаткам от нескольких модулей: алгоритм Гарнера и точные вычисления по многим простым. O(k²) операций с машинными числами 2 задачи NUM Алгоритм Длинная арифметика Числа длиннее машинного слова: цифры по основанию 10⁹ или 2³⁰, переносы, столбик и дорогая печать. сложение O(n), умножение и деление столбиком O(n²), печать в десятичной записи O(n²) или O(M(n) log n) 2 задачи NUM Алгоритм Умножение Карацубы Три умножения половин вместо четырёх: n^1,585 вместо n² — в CPython, Go и GMP. O(n^1,585) 2 задачи NUM Алгоритм Быстрое преобразование Фурье Дискретное преобразование Фурье за O(N log N): спектры, свёртки, умножение многочленов и больших чисел. O(N log N) 2 задачи NUM Алгоритм Теоретико-числовое преобразование БПФ без округлений: корень из единицы — 17 по модулю 3329, и так ваш браузер умножает многочлены постквантового ключа. O(n log n) 1 задача NUM Алгоритм Матрицы и рекуррентности Степень матрицы: пути длины k в графе, линейные рекуррентности, матрица переноса и цепи Маркова. O(m³ log k) для A^k размера m × m 2 задачи NUM Алгоритм Метод Гаусса Линейная система исключением: ведущий элемент, LU, обусловленность, разреженные матрицы и заполнение. O(n³): около n³/3 умножений на прямой ход 2 задачи NUM Алгоритм Генераторы псевдослучайных чисел Откуда берутся «случайные» числа, почему плохой генератор видно по плоскостям и как его проверить. O(1) на число 2 задачи

GEO Приём Векторы и ориентация Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия. O(1) на один поворот 2 задачи GEO Алгоритм Пересечение отрезков Где встречаются два отрезка — точно, в дробях; и как найти все встречи среди тысяч отрезков без перебора пар. O(1) на пару; O(n²) перебором для n отрезков 2 задачи GEO Алгоритм Выпуклая оболочка Наименьший выпуклый многоугольник, содержащий все точки, за O(n log n). O(n log n) 2 задачи GEO Алгоритм Точка в многоугольнике Луч из точки пересекает границу нечётное число раз — точка внутри; число оборотов — то же со знаками. O(n) на точку 2 задачи GEO Алгоритм Площадь многоугольника Площадь по координатам вершин: сумма xᵢyᵢ₊₁ − xᵢ₊₁yᵢ, а её знак — направление обхода. O(n) 2 задачи GEO Приём Заметающая прямая Упростите берега мира до 0,2° — и в 72 местах они пересекутся. Прямая с запада на восток найдёт их все, сравнив только соседей. O((n + k) log n) 3 задачи GEO Алгоритм Триангуляция Делоне и диаграмма Вороного Зоны ближайшей точки и треугольники с пустыми окружностями: две стороны одной структуры. O(n log n) в среднем 2 задачи GEO Структура данных k-d дерево Двоичное дерево, которое делит пространство по осям по очереди: ближайшая точка — за десятки шагов вместо перебора. O(n log n) построение; O(log n) на запрос в среднем 1 задача GEO Структура данных R-дерево Окно карты 10° × 5°: из 58 987 отрезков берега R-дерево проверяет 847 прямоугольников. И находит город, дальше всех от моря. окно — число открытых узлов × M; ближайший — обычно O(log n) узлов 1 задача GEO Приём Вращающиеся калиперы У 971 из 2679 кварталов центра Алматы наименьший прямоугольник повёрнут на 4–8°: сетка улиц смотрит не строго на север. O(n) после оболочки, O(n log n) с ней 2 задачи GEO Алгоритм Упрощение линий Рамера — Дугласа — Пекера Упростить ломаную без потери формы: точка, дальше всех от хорды, остаётся, если она дальше допуска. O(n log n) в типичном случае, O(n²) в худшем 2 задачи GEO Приём Кривые Гильберта и geohash Пронумеровать плоскость так, чтобы соседи на карте стояли рядом в одномерном индексе: Z-порядок, geohash, Гильберт. O(k) на номер 1 задача

NUM~ Алгоритм Бисекция и метод Ньютона Корень уравнения: деление отрезка пополам надёжно, касательные Ньютона — быстро. бисекция — log₂((b − a)/ε) шагов; Ньютон — около log₂ от числа знаков 2 задачи NUM~ Алгоритм Градиентный спуск Ищет минимум функции шагами против градиента — в сторону самого крутого спуска. O(κ · log(1/ε)) шагов 2 задачи NUM~ Алгоритм Численное интегрирование Площадь под кривой суммой: трапеции, Симпсон, узлы Гаусса, адаптивный шаг и оценка ошибки по Рунге. O(n) вычислений функции 2 задачи NUM~ Алгоритм Метод Монте-Карло Оценка числа случайным опытом: ошибка 1/√n в любой размерности, честный доверительный интервал. O(n) испытаний, ошибка ~ σ/√n 2 задачи NUM~ Алгоритм Методы Эйлера и Рунге — Кутты Шаг за шагом по закону движения: Эйлер, РК4, адаптивный шаг, Верле для орбит и неявные схемы. O(T/h) шагов, у РК4 четыре вычисления правой части на шаг 2 задачи NUM~ Приём Суммирование Кэхэна Сложить миллионы дробных чисел и не растерять младшие разряды: поправка Кэхэна, попарное и точное суммирование. O(n) 1 задача NUM~ Алгоритм Симплекс-метод 24 числа вместо 88 клавиш — и симплекс-метод восстанавливает каждый аккорд прелюдии Шопена точно. Наименьшие квадраты — ни одного. шаг — O(m·n); число шагов на практике порядка m, в худшем случае экспоненциальное 1 задача

SYS Алгоритм Консистентное хеширование Распределяет ключи по серверам так, что при добавлении сервера переезжает лишь его доля. O(log(N·v)) на поиск сервера 1 задача SYS Алгоритм Рандеву-хеширование Каждый ключ уходит к серверу с наибольшим хешем пары «ключ, сервер»: равномерно, без таблиц, отказ сдвигает только ключи упавшего. O(N) на ключ 2 задачи SYS Структура данных Count-Min Sketch Частоты элементов потока в фиксированной памяти: минимум из d счётчиков, ошибка только вверх. O(d) на элемент и на запрос 2 задачи SYS Структура данных HyperLogLog Число разных элементов потока в килобайте памяти: длинные серии нулей в хешах и среднее по регистрам. O(1) на элемент, O(m) на оценку 2 задачи SYS Алгоритм Резервуарная выборка k случайных элементов из потока неизвестной длины за один проход и O(k) памяти. O(n) 2 задачи SYS Структура данных Дерево Меркла Хеши хешей: отпечаток всего набора, поиск расхождений за несколько сравнений и доказательство из log n хешей. O(n) на построение, O(log n) на доказательство и его проверку 2 задачи SYS Алгоритм Ограничение частоты запросов Не больше N запросов в единицу времени: окно, журнал, два счётчика и ведро с токенами. O(1) на запрос (журнал — O(N)) 2 задачи SYS Структура данных Инвертированный индекс и BM25 Словарь «слово → документы, где оно есть»: запрос читает несколько коротких списков вместо всех текстов. O(сумма длин списков слов запроса); «И» галопом — O(m·log(n/m)) 2 задачи SYS Алгоритм MinHash и LSH Подпись из K минимумов хешей: доля совпавших — оценка сходства Жаккара; полосы LSH сводят похожие пары в одни корзины. O(K·S) на подписи, O(n·b) на корзины, плюс проверка кандидатов 2 задачи SYS Структура данных LSM-дерево Записи копятся в памяти и ложатся на диск отсортированными прогонами; фоновые слияния держат число прогонов малым. запись O(1) амортизированно в памяти плюс O(L·T/B) на перезапись при слиянии; чтение — по прогону на уровень 2 задачи SYS Приём Повтор с джиттером Пауза перед повтором растёт вдвое и выбирается случайно: клиенты расходятся во времени и не бьют по серверу волнами. O(1) на решение о паузе 2 задачи SYS Алгоритм Raft Реплицированный журнал на ненадёжных серверах: лидер, сроки, большинство; выдерживает падение меньшей половины. один круг сообщений до большинства на запись 2 задачи SYS Алгоритм Часы Лэмпорта и векторные часы Логические часы: одно число Лэмпорта согласовано с «случилось раньше», вектор по процессам отличает «раньше» от «параллельно». O(1) на событие у Лэмпорта, O(n) у векторных 2 задачи SYS Структура данных CRDT Данные, копии которых правят независимо и сливают в любом порядке: счётчики, множества, текст. O(1) на операцию у счётчика и множества; вставка в текст — O(1) в среднем 2 задачи SYS Алгоритм Два случайных выбора Спросить двух случайных и выбрать менее занятого: самая полная корзина — ln ln n вместо ln n / ln ln n. O(d) на решение: узнать нагрузку d серверов 2 задачи SYS Алгоритм Планирование задач Порядок работы: короткие сначала, сроки, прерывания, много ядер и аномалии Грэма. O(n log n): сортировка или куча 2 задачи SYS Алгоритм Алгоритм rsync Передаёт только изменённые куски файла: суммы блоков туда, новые байты обратно; блоки находятся на любом смещении. O(n + m): сумма окна сдвигается за O(1), сильная сумма — только при совпадении слабой 2 задачи SYS Алгоритм LFU и ARC Кэши, которые помнят частоту: LFU за O(1) на корзинах счётчиков и ARC, который сам делит места между свежими и частыми. O(1) на запрос у обоих 2 задачи

ML Алгоритм k-средних Делит точки на k групп так, чтобы точки были поближе к центру своей группы. O(n · k · d) за шаг 2 задачи ML Алгоритм DBSCAN Собирает в кластеры плотные области точек любой формы, а одинокие точки помечает как шум. O(n·Q + Σ|N(p)|) 2 задачи ML Алгоритм k ближайших соседей Отвечает так, как ответило большинство из k самых похожих известных примеров. O(n · d) на вопрос 2 задачи ML Алгоритм Решающее дерево Отвечает цепочкой вопросов «признак ≤ порог?»; каждый вопрос выбран так, чтобы неопределённость упала сильнее всего. O(h · F · n log n) построение; O(h) ответ 2 задачи ML Алгоритм Наивный Байес Считает, как часто каждый признак встречается в каждом классе, и складывает логарифмы этих частот. O(N) обучение, O(L·m) ответ 2 задачи ML Алгоритм Линейная регрессия Подбирает коэффициенты модели так, чтобы сумма квадратов промахов по данным была наименьшей. O(n·d² + d³) 2 задачи ML Алгоритм Логистическая регрессия Оценивает вероятность ответа «да»: взвешенная сумма признаков, пропущенная через сигмоиду. O(n·d² + d³) на шаг Ньютона 3 задачи ML Алгоритм Метод главных компонент Находит направления наибольшего разброса данных и описывает каждую точку немногими числами вдоль них. O(n·d² + d³) 2 задачи ML Алгоритм Рекомендации через разложение матрицы Тысяча книг, четыре тысячи читателей и десять чисел на каждого. Отметьте, что вам нравится, — и посмотрите, что предложит разложение матрицы. раунд ALS — O(N·k² + (u + i)·k³) 1 задача ML Алгоритм Перцептрон и обратное распространение Нарисуйте цифру: её узнают перцептрон 1958 года и сеть со скрытым слоем, обученные прямо на странице за секунду. перцептрон — O(d) на пример; градиент сети — O(число весов) на пример 1 задача

RND Приём Лас-Вегас и Монте-Карло Всегда верный, но иногда долгий против всегда быстрого, но иногда неверного — и как превратить одно в другое. O(k · стоимость одной попытки) 2 задачи RND Приём Случайные блуждания Шаг наугад на каждом перекрёстке: √t, время до цели, «кто первый» и 2-SAT случайным блужданием. O(1) на шаг 2 задачи RND Алгоритм Имитация отжига Локальный поиск, который принимает ухудшения с вероятностью e^(−Δ/T) и постепенно остывает. O(S · c) 2 задачи RND Алгоритм Генетический алгоритм Популяция решений, отбор, скрещивание и мутация: эволюция траектории на настоящем автодроме. O(G · N · c) 2 задачи