разделяй и властвуй

SRT Алгоритм Сортировка слиянием Делит пополам, сортирует половины и сливает: n log n на любом входе, устойчиво, годится для внешней памяти. O(n log 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 Алгоритм Быстрый выбор k-й по величине без сортировки: разбиение и одна ветка вместо двух — O(n) в среднем, медиана медиан — всегда. O(n) в среднем 1 задача DS Приём Корневая декомпозиция Блоки по √n: целые отвечают сразу, разрезанные — поклеточно; O(√n) там, где дерево отрезков не складывается. И порядок Мо. O(√n) на запрос; Мо — O(n√q) на все 1 задача DS Структура данных Дерево отрезков Минимум, максимум и сумма на любом отрезке с изменениями на ходу: оба действия за O(log n). O(log n) на запрос и на изменение 2 задачи GRA Алгоритм Центроидная декомпозиция Делим дерево центроидами: log₂ n уровней, и ближайшая отмеченная вершина — за O(log n) после каждой отметки. O(log n) на отметку и на вопрос 1 задача STR Алгоритм Z-функция Сколько букв от каждой позиции совпадает с началом строки — за O(n); поиск, периоды и повторы подряд. O(n) 2 задачи DP Алгоритм Наибольшая общая подпоследовательность Самая длинная цепочка, общая двум последовательностям: таблица m × n, путь назад, Хиршберг. O(m · n) 2 задачи DP Приём Оптимизации Кнута и «разделяй и властвуй» 45 тысяч городов на карте по классам населения: 3,5 млн вычислений вместо пяти миллиардов — потому что лучший разрез монотонен. O(k · n log n) 2 задачи PAR Приём Разделяй и властвуй Разрезать, решить части так же, склеить; сколько это стоит — по уровням дерева рекурсии и основной теореме. T(n) = a·T(n/b) + f(n) 2 задачи PAR Алгоритм Ближайшая пара точек Две ближайшие точки из n за n log n: разрез, полоса шириной 2d и семь соседей; сеткой — за n в среднем. O(n log n) 2 задачи NUM Алгоритм Быстрое возведение в степень aⁿ за O(log n) умножений: квадраты по битам показателя. O(log n) умножений 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 задачи GEO Структура данных k-d дерево Двоичное дерево, которое делит пространство по осям по очереди: ближайшая точка — за десятки шагов вместо перебора. O(n log n) построение; O(log n) на запрос в среднем 1 задача GEO Алгоритм Упрощение линий Рамера — Дугласа — Пекера Упростить ломаную без потери формы: точка, дальше всех от хорды, остаётся, если она дальше допуска. O(n log n) в типичном случае, O(n²) в худшем 2 задачи NUM~ Алгоритм Численное интегрирование Площадь под кривой суммой: трапеции, Симпсон, узлы Гаусса, адаптивный шаг и оценка ошибки по Рунге. O(n) вычислений функции 2 задачи TEC Приём Сложность по замерам Рост времени по замерам: наклон, проверка отношением, экспоненты — и где замер врёт. O(B) на попытку 1 задача