Разделяй и ВластвуйDivide & Conquer

Разделяй-и-властвуй — это рекуррентное соотношение T(n) = a·T(n/b) + f(n): разбить вход размера n на a подзадач размера n/b, решить каждую рекурсивно, потратить f(n) на объединение результатов. Master theorem (2.1.2) даёт итоговую асимптотику по трём числам — a, b и f(n). Ключевое наблюдение, вокруг которого построена вся эта тема: САМО разбиение почти никогда не даёт выигрыша — выигрыш даёт то, сколько именно рекурсивных подзадач a требуется и что происходит на шаге объединения. Наивное разбиение задачи умножения чисел или матриц пополам по-прежнему требует a=4 (числа) или a=8 (матрицы) подзадач — и по Master theorem это даёт ровно ту же асимптотику, что и наивный алгоритм без всякой рекурсии. Карацуба (1960) и Штрассен (1969) вошли в историю не потому, что придумали "разбить пополам" — это очевидно, — а потому, что нашли способ объединения, требующий на одну (Карацуба: 3 вместо 4) или на одну (Штрассен: 7 вместо 8) подзадачу меньше ценой более сложной алгебры на шаге combine. БПФ (1965, Кули—Тьюки, хотя идея восходит к Гауссу) идёт другим путём: та же схема "разбить пополам", но объединение работает не через дополнительные умножения, а через явную структуру корней из единицы, что даёт a=2, b=2 и f(n)=O(n) — отсюда O(n log n) вместо O(n²) для свёртки. Последние две статьи переносят ту же идею в геометрию: ближайшая пара точек и выпуклая оболочка — обе имеют вид T(n) = 2T(n/2) + O(n), но весь нетривиальный контент — в том, как за линейное время объединить два решения половин без полного перебора пар между ними.Divide-and-conquer is the recurrence T(n) = a·T(n/b) + f(n): split an input of size n into a subproblems of size n/b, solve each recursively, spend f(n) combining the results. The Master theorem (2.1.2) gives the final asymptotics from three numbers — a, b, and f(n). The key observation this whole topic is built around: the split itself almost never buys you anything — the payoff comes from exactly how many recursive subproblems a are needed and what happens at the combine step. A naive split of number or matrix multiplication in half still needs a=4 (numbers) or a=8 (matrices) subproblems — and by the Master theorem that gives exactly the same asymptotics as the naive algorithm with no recursion at all. Karatsuba (1960) and Strassen (1969) made history not because they thought of "split in half" — that part is obvious — but because they found a way to combine that needs one fewer subproblem (Karatsuba: 3 instead of 4) or one fewer (Strassen: 7 instead of 8), at the cost of trickier algebra in the combine step. The FFT (1965, Cooley–Tukey, though the idea traces back to Gauss) takes a different route: the same "split in half" scheme, but the combine step works not through extra multiplications but through the explicit structure of roots of unity, giving a=2, b=2, and f(n)=O(n) — hence O(n log n) instead of O(n²) for convolution. The last two articles carry the same idea into geometry: closest pair of points and convex hull both have the shape T(n) = 2T(n/2) + O(n), but all the non-trivial content is in how the two half-solutions get combined in linear time without brute-forcing every cross-pair.

Порядок карточек — по смысловой дуге: сначала быстрая арифметика над числами (Карацуба), затем тот же приём над матрицами (Штрассен), затем над многочленами/сигналами (БПФ), и наконец два примера из вычислительной геометрии. Полный разбор — на отдельной странице по ссылке в названии.The card order follows a narrative arc: fast arithmetic on numbers first (Karatsuba), then the same trick on matrices (Strassen), then on polynomials/signals (FFT), and finally two computational-geometry examples. The full writeup is on its own page via the name link.

Первые две карточки — арифметика над числами и матрицами, где вся статья строится вокруг одного факта: сокращение числа рекурсивных подзадач (3 вместо 4, 7 вместо 8) ценой более сложной алгебры combine-шага меняет показатель степени в асимптотике. Третья переносит тот же принцип на многочлены, но объединение там устроено принципиально иначе — не через уменьшение числа умножений, а через переход в другое представление (точечные значения вместо коэффициентов), где умножение вообще становится тривиальным. Четвёртая и пятая карточки — вычислительная геометрия: обе имеют "правильную" асимптотику T(n) = 2T(n/2) + O(n) без всяких трюков с числом подзадач, а вся сложность — в том, как за линейное время объединить два решения половин, не перебирая все пары между ними.The first two cards are arithmetic on numbers and matrices, where the whole article is built around one fact: cutting the number of recursive subproblems (3 instead of 4, 7 instead of 8) at the cost of trickier combine-step algebra changes the exponent in the asymptotics. The third carries the same principle to polynomials, but the combine step works on a fundamentally different mechanism — not by cutting the number of multiplications, but by switching to a different representation (point-values instead of coefficients) where multiplication becomes trivial altogether. The fourth and fifth cards are computational geometry: both have the "well-behaved" T(n) = 2T(n/2) + O(n) asymptotics with no tricks on the subproblem count — all the difficulty is in combining two half-solutions in linear time without checking every cross-pair.