Разделяй и властвуй ⚔️

Два прошлых урока про сортировку — быструю сортировку и сортировку слиянием — на первый взгляд выглядели как два отдельных алгоритма, каждый со своими сильными и слабыми сторонами: один быстрый в среднем, но ненадёжный, другой чуть медленнее, зато гарантированно предсказуемый. Но если посмотреть на них не как на два конкурирующих рецепта, а немного отстранённо, становится видно нечто более важное: оба они — частные реализации одной и той же идеи. Массив делится на части, каждая часть решается точно так же, как решалась бы исходная задача, только на меньшем объёме данных, а потом результаты как-то соединяются обратно. Различие между quicksort и merge sort — не в идее, а лишь в том, на каком именно шаге сосредоточена вся сложная работа: на разбиении или на слиянии.

Эта идея называется «разделяй и властвуй» (divide and conquer, сокращённо D&C), и она устроена гораздо шире, чем просто «ещё один способ отсортировать массив». Это общий рецепт решения задач: раздели задачу на подзадачи того же типа, но меньшего размера, реши каждую подзадачу рекурсивно, объедини решения подзадач в решение исходной задачи. Три шага — и всё. В этом уроке ты научишься видеть эту структуру за конкретным кодом, выведешь общий инструмент для оценки сложности любого алгоритма такого вида — основную теорему о рекуррентных соотношениях (master theorem), — и увидишь, что она работает не только для сортировок: за бинарным поиском, быстрым возведением в степень и умножением больших чисел стоит ровно та же трёхшаговая схема, просто доведённая до предельно разных форм.

Для практикующего в анализе данных и машинном обучении (Data Science) это не абстрактная теория ради теории. Быстрое возведение в степень за $O(\log n)$ — это не учебная задачка, а рабочая деталь внутри численных библиотек: именно этим приёмом (вместе с быстрым преобразованием Фурье, устроенным по той же схеме) пользуются реализации numpy, scipy и линейной алгебры на GPU, когда им нужно быстро возвести матрицу в большую степень или вычислить дискретное преобразование сигнала. Рекурсивное построение KD-деревьев, с которыми ты уже встречался в уроке 257 про бинарные деревья поиска, — это тоже «разделяй и властвуй»: пространство точек рекурсивно делится пополам по медиане вдоль очередной координаты, и от этого прямо зависит, насколько быстро потом можно будет искать ближайших соседей в задачах рекомендаций и поиска релевантных объектов (retrieval). Понимание общей парадигмы позволяет не запоминать десяток отдельных алгоритмов, а один раз понять их общий скелет — и узнавать его в новом, ещё не виденном коде.

План урока такой: сначала явно проговорим три шага парадигмы и переосмыслим сортировки как её частные случаи, затем выведем и разберём основную теорему о рекуррентных соотношениях с интуицией всех трёх её случаев, применим её к бинарному поиску и быстрому возведению в степень как к вырожденным случаям с ровно одной подзадачей на каждом уровне, кратко познакомимся с умножением Карацубы — и в конце чётко разграничим «разделяй и властвуй» с динамическим программированием по единственному, но решающему признаку: пересекаются подзадачи между собой или нет.

История

Сама фраза «разделяй и властвуй» — не изобретение компьютерных наук. Латинское выражение divide et impera веками использовалось как политическая и военная максима: разбей объединённого противника на несколько разрозненных враждующих групп — и ослабленными по отдельности ими будет намного проще управлять, чем единым сильным целым. Эту стратегию приписывают ещё римским правителям, её подробно обсуждал Никколо Макиавелли в трактатах о государственном управлении, и задолго до появления компьютеров она была общим местом в риторике о власти и управлении сложными системами. Когда в середине XX века специалисты по вычислительной технике стали искать язык для описания рекурсивных алгоритмов, эта метафора оказалась удивительно точной: разбей большую, неподъёмную задачу на несколько меньших, разберись с каждой по отдельности — и общая проблема окажется решена.

Интересно, что конкретные алгоритмы, воплощающие эту идею, появились раньше, чем сама идея была осознана и названа как общий класс. Сортировка слиянием, которую ты разбирал в прошлом уроке, была описана Джоном фон Нейманом ещё в 1945 году, а быстрая сортировка Тони Хоара появилась в 1959–1961 годах — оба алгоритма реально работали и решали практические задачи задолго до того, как кто-то сформулировал общий принцип «раздели, реши рекурсивно, объедини» как самостоятельную категорию для изучения. Систематическое осмысление divide and conquer как единой алгоритмической парадигмы, наравне с жадными алгоритмами и динамическим программированием, оформилось в учебниках по анализу алгоритмов 1970-х годов — в первую очередь в классическом труде Альфреда Ахо, Джона Хопкрофта и Джеффри Ульмана «The Design and Analysis of Computer Algorithms» («Построение и анализ вычислительных алгоритмов», 1974), который одним из первых явно выделил разделяй и властвуй в отдельную главу и показал, что бинарный поиск, сортировки и умножение больших чисел — это проявления одного и того же приёма.

Отдельная страница в этой истории — сама основная теорема о рекуррентных соотношениях (master theorem), с которой ты познакомишься дальше в этом уроке. До её появления каждый новый рекурсивный алгоритм требовал заново разворачивать дерево рекурсии вручную, чтобы понять его сложность — работа хоть и не сложная, но утомительная и легко приводящая к ошибкам. В 1980 году Джон Бентли, Доротея Хакен и Джеймс Сакс опубликовали статью «A general method for solving divide-and-conquer recurrences» («Общий метод решения рекуррентных соотношений разделяй-и-властвуй»), в которой свели типовой анализ к сравнению всего пары показателей степени — а не к пересчёту дерева рекурсии каждый раз с нуля. Десятилетие спустя эта техника получила широкую известность как «master theorem» именно благодаря учебнику «Introduction to Algorithms» Кормена, Лейзерсона, Ривеста и Штайна (1990) — том самом CLRS, который с тех пор остаётся одним из главных учебников по алгоритмам в мире, — и с тех пор master theorem стала стандартным инструментом в арсенале каждого, кто пишет или анализирует рекурсивные алгоритмы.

Три шага парадигмы: разделение, решение, объединение

Интуиция

Представь, что тебе нужно посчитать общую массу очень длинного товарного состава, вагон за вагоном, и у тебя нет весов, способных взвесить весь состав целиком, зато есть весы, справляющиеся с половиной состава. Естественное решение: раздели состав на две половины, взвесь каждую половину отдельно (а если и половина не влезает на весы — раздели её ещё раз, и так до тех пор, пока части не станут достаточно маленькими, чтобы взвесить их напрямую), а затем сложи полученные массы. Ты не изобрёл никакого нового способа взвешивания — ты просто применил одну и ту же операцию рекурсивно к частям всё меньшего размера, а объединил результаты самой простой операцией из возможных — сложением.

Это ровно то, чем занимается парадигма «разделяй и властвуй»: она не предлагает нового способа решать конкретную задачу, а предлагает схему, по которой задачу можно организовать, если у неё есть удобное свойство — большую задачу можно свести к нескольким меньшим задачам того же типа. Ключевое слово здесь — «того же типа»: подзадача сортировки половины массива — это снова задача сортировки, только меньшего размера, а не какая-то принципиально другая задача. Именно эта однородность и позволяет применить рекурсию: один и тот же код, вызванный на меньшем входе, решает подзадачу так же, как решал бы исходную задачу.

Определение

Парадигма «разделяй и властвуй» состоит из трёх шагов, применяемых к задаче размера $n$:

1. Разделение (Divide). Разбить исходную задачу на несколько подзадач меньшего размера того же типа — как правило, эти подзадачи независимы друг от друга и в сумме покрывают всю исходную задачу.
2. Властвование / решение (Conquer). Решить каждую подзадачу рекурсивно тем же самым алгоритмом. Если подзадача достаточно мала (база рекурсии), решить её напрямую, без дальнейшего деления.
3. Объединение (Combine). Скомбинировать решения подзадач в решение исходной задачи размера $n$.

Важно понимать: эта схема ничего не говорит о том, где сосредоточена основная работа алгоритма. Она может целиком уйти на шаг разделения, целиком на шаг объединения, или быть размазана по всем трём шагам примерно поровну — и именно от этого распределения зависит итоговая асимптотика, как ты увидишь в следующем разделе про master theorem.

Разбор примеров

Пример 1 (переосмысление быстрой сортировки). Наложи трёхшаговую схему на quicksort из урока 267. Разделение — здесь самая тяжёлая часть: процедура partition выбирает опорный элемент и физически переставляет элементы массива так, чтобы все меньшие пивота оказались слева, а все большие — справа; это $O(n)$ работы, и именно здесь решается, насколько сбалансированными выйдут подзадачи. Решение — рекурсивный вызов quicksort на левой и на правой частях. Объединение — а вот здесь ничего не происходит: как только обе части отсортированы каждая на своём месте внутри общего массива, весь массив уже отсортирован целиком, дополнительного шага «слияния» не требуется.

def quicksort(arr, low, high):
    if low < high:
        p = partition(arr, low, high)  # Разделение: O(n) работы здесь
        quicksort(arr, low, p - 1)      # Решение: рекурсия слева
        quicksort(arr, p + 1, high)     # Решение: рекурсия справа
        # Объединение: пустой шаг, массив уже отсортирован на месте

Пример 2 (переосмысление сортировки слиянием). Наложи ту же схему на merge sort из урока 268 — и увидишь зеркальную картину. Разделение — тривиально: индекс середины массива вычисляется за $O(1)$, никакого анализа значений элементов не требуется. Решение — рекурсивные вызовы на левой и правой половине. Объединение — вот где сосредоточена вся содержательная работа: функция merge проходит по обеим уже отсортированным половинам и собирает из них один отсортированный массив за $O(n)$.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2                  # Разделение: O(1), просто индекс
    left = merge_sort(arr[:mid])         # Решение: рекурсия слева
    right = merge_sort(arr[mid:])        # Решение: рекурсия справа
    return merge(left, right)            # Объединение: O(n) работы здесь

Заметь: quicksort и merge sort — это буквально зеркальные распределения одной и той же трёхшаговой схемы. Там, где у quicksort тяжёлое разделение и пустое объединение, у merge sort — пустое (точнее, тривиальное) разделение и тяжёлое объединение. Это не совпадение и не два разных алгоритма, притворяющихся похожими, — это одна и та же парадигма, реализованная с противоположным распределением работы между шагами.

Пример 3 (задача о максимальной подпоследовательности). Возьмём задачу, где объединение не тривиально, но и не является полноценным «слиянием»: дан массив чисел (в том числе отрицательных), нужно найти непрерывный подмассив с максимальной суммой элементов. Разделение — разбить массив пополам по индексу, как в merge sort. Решение — рекурсивно найти максимальную подпоследовательность в левой половине и в правой половине. Объединение — а вот здесь появляется третий, самостоятельный случай: максимальный подмассив всего массива — это либо максимальный подмассив целиком внутри левой половины, либо целиком внутри правой половины, либо он пересекает границу между половинами, и такой «пересекающий» вариант нужно посчитать отдельно, пройдясь от границы влево и вправо и накапливая суммы.

def max_crossing_sum(arr, low, mid, high):
    left_sum, total, max_left = float('-inf'), 0, mid
    for i in range(mid, low - 1, -1):
        total += arr[i]
        if total > left_sum:
            left_sum, max_left = total, i

    right_sum, total, max_right = float('-inf'), 0, mid + 1
    for i in range(mid + 1, high + 1):
        total += arr[i]
        if total > right_sum:
            right_sum, max_right = total, i

    return left_sum + right_sum

def max_subarray(arr, low, high):
    if low == high:
        return arr[low]
    mid = (low + high) // 2
    left = max_subarray(arr, low, mid)
    right = max_subarray(arr, mid + 1, high)
    cross = max_crossing_sum(arr, low, mid, high)
    return max(left, right, cross)

Для массива [-2, 1, -3, 4, -1, 2, 1, -5, 4] рекурсия дойдёт до одноэлементных подмассивов, а на обратном пути объединение на каждом уровне будет сравнивать три кандидата — «лучшее слева», «лучшее справа» и «лучшее через границу» — и в итоге корректно найдёт ответ 4 + (-1) + 2 + 1 = 6 (подмассив [4, -1, 2, 1]), несмотря на то, что этот оптимальный подмассив физически пересекает несколько границ деления, ни одна из которых сама по себе «не знала» о существовании остальных частей ответа.

Почему это важно

Умение раскладывать чужой (или собственный) рекурсивный код именно на эти три шага — не формальное упражнение, а рабочий навык. Как только ты видишь, что задача сводится к «раздели → реши рекурсивно → объедини», у тебя автоматически появляется вопрос, определяющий всю дальнейшую сложность алгоритма: где именно сосредоточена основная работа — в разделении, в объединении, или она распределена по всем уровням рекурсии поровну? Ответ на этот вопрос — это фактически черновик ответа на вопрос об асимптотике всего алгоритма, а формальный инструмент, который превращает этот черновик в точную формулу, — это основная теорема о рекуррентных соотношениях, к которой мы переходим.

Основная теорема о рекуррентных соотношениях (master theorem)

Интуиция

У любого алгоритма «разделяй и властвуй» время работы описывается рекуррентным соотношением: время на решение задачи размера $n$ равно времени на решение нескольких подзадач меньшего размера плюс время на разделение и объединение. В прошлом уроке для merge sort ты уже выводил такое соотношение вручную, разворачивая дерево рекурсии по уровням и складывая работу на каждом уровне. Это работает, но каждый раз пересчитывать дерево рекурсии с нуля — долго и легко ошибиться. Master theorem — это готовый ответ для целого класса таких рекуррентных соотношений: вместо того чтобы рисовать дерево, достаточно сравнить между собой две величины — во сколько раз растёт число подзадач и во сколько раз растёт работа на объединение — и по результату сравнения сразу получить асимптотику.

Интуитивно всё сводится к одному вопросу: кто делает больше работы — листья дерева рекурсии (то есть суммарно все базовые случаи) или его корень (то есть объединение на самом верхнем уровне)? Если у алгоритма очень много мелких подзадач и дешёвое объединение — почти вся работа происходит внизу дерева, среди листьев. Если, наоборот, объединение на каждом уровне дорогое, а подзадач немного — работа сосредоточена наверху, у корня. А посередине есть особый, тонко сбалансированный случай, когда работа распределена по всем уровням дерева примерно поровну — именно этот случай и порождает знакомый множитель $\log n$.

Теорема

Основная теорема о рекуррентных соотношениях (master theorem). Пусть рекуррентное соотношение имеет вид

$$T(n) = a \cdot T(n/b) + f(n)$$

где $a \geq 1$ — число подзадач, $b > 1$ — во сколько раз уменьшается размер каждой подзадачи, а $f(n)$ — время на разделение и объединение (без учёта самих рекурсивных вызовов). Сравним $f(n)$ с критической величиной $n^{\log_b a}$ — это время, которое заняли бы одни только листья дерева рекурсии, если бы объединение вообще ничего не стоило.

1. Случай 1 (листья дороже). Если $f(n) = O(n^{\log_b a - \varepsilon})$ для некоторого $\varepsilon > 0$, то $T(n) = \Theta(n^{\log_b a})$ — суммарная работа определяется числом и размером листьев, объединение асимптотически несущественно.
2. Случай 2 (баланс). Если $f(n) = \Theta(n^{\log_b a} \log^k n)$ для некоторого $k \geq 0$, то $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$ — работа распределена по всем $\Theta(\log n)$ уровням дерева примерно поровну, и появляется дополнительный логарифмический множитель.
3. Случай 3 (объединение дороже). Если $f(n) = \Omega(n^{\log_b a + \varepsilon})$ для некоторого $\varepsilon > 0$ и выполняется условие регулярности $a \cdot f(n/b) \leq c \cdot f(n)$ для некоторой константы $c < 1$ и достаточно больших $n$, то $T(n) = \Theta(f(n))$ — работа на самом верхнем уровне доминирует над всем деревом.

Стоит сразу оговориться: теорема покрывает не вообще все рекуррентные соотношения такого вида, а только те, где $f(n)$ достаточно чётко попадает в одну из трёх категорий — заметно медленнее, примерно так же, или заметно быстрее, чем $n^{\log_b a}$. Между случаями остаются узкие «щели», в которые master theorem не попадает вовсе, — ты увидишь такой пример в практических заданиях дальше.

Разбор примеров

Пример 1 (случай 2 — сортировка слиянием). Рекуррентное соотношение merge sort: $T(n) = 2T(n/2) + O(n)$. Здесь $a = 2$, $b = 2$, значит критическая величина $n^{\log_2 2} = n^1 = n$. Сравниваем: $f(n) = O(n) = \Theta(n^1 \log^0 n)$ — это ровно случай 2 с $k = 0$. По теореме $T(n) = \Theta(n^1 \log^{0+1} n) = \Theta(n \log n)$ — тот же результат, что в прошлом уроке был получен вручную через разворачивание дерева рекурсии по уровням, но здесь он получен буквально в одну строчку сравнения показателей.

Пример 2 (случай 2, вырожденный — бинарный поиск). Рекуррентное соотношение бинарного поиска: на каждом шаге задача сводится к поиску в одной половине массива, а не в обеих, значит $a = 1$, $b = 2$, а сравнение с серединой занимает $O(1)$, значит $f(n) = O(1)$. Критическая величина $n^{\log_2 1} = n^0 = 1$. Сравниваем: $f(n) = \Theta(1) = \Theta(n^0 \log^0 n)$ — снова случай 2 с $k=0$, значит $T(n) = \Theta(n^0 \log^{0+1} n) = \Theta(\log n)$. Это тот самый результат, который ты интуитивно знал и раньше, но теперь он получен из того же общего инструмента, что и сложность merge sort — просто с $a=1$ вместо $a=2$.

Пример 3 (случай 1 — наивное рекурсивное умножение матриц). Чтобы перемножить две матрицы $n \times n$, можно разбить каждую на четыре блока размера $n/2 \times n/2$ и выразить произведение через восемь произведений блоков меньшего размера плюс их сложение: $T(n) = 8T(n/2) + O(n^2)$, где $O(n^2)$ — время на сложение блоков-результатов. Здесь $a = 8$, $b = 2$, критическая величина $n^{\log_2 8} = n^3$. Сравниваем: $f(n) = O(n^2) = O(n^{3-1})$ — это случай 1 с $\varepsilon = 1$, значит $T(n) = \Theta(n^3)$ — та же сложность, что и у самого обычного тройного вложенного цикла школьного умножения матриц. Разбиение на блоки само по себе ничего не ускорило, потому что почти вся работа сосредоточена не в объединении, а в восьми одинаково дорогих рекурсивных вызовах — это классический случай 1, «листья дороже».

Пример 4 (случай 3 — среднее время работы алгоритма быстрого выбора). Алгоритм quickselect (поиск $k$-го по порядку элемента без полной сортировки массива, устроенный как quicksort, но рекурсивно обрабатывающий только одну из двух частей) в среднем случае описывается соотношением $T(n) = T(n/2) + O(n)$, где $O(n)$ — стоимость разбиения на этом шаге. Здесь $a = 1$, $b = 2$, критическая величина $n^{\log_2 1} = n^0 = 1$. Сравниваем: $f(n) = \Theta(n) = \Omega(n^{0+1})$ — это случай 3 с $\varepsilon = 1$. Проверим условие регулярности: $a \cdot f(n/2) = 1 \cdot (n/2) = n/2 \leq c \cdot n$ при $c = 1/2 < 1$ — условие выполняется. Значит $T(n) = \Theta(f(n)) = \Theta(n)$ — линейное время в среднем случае, несмотря на то что задача решается рекурсивно, а не одним проходом. Вся сложность в этом соотношении сосредоточена на верхних уровнях (разбиение на каждом шаге), а не в листьях — прямая противоположность примеру 3.

Почему это важно

Master theorem превращает анализ нового рекурсивного алгоритма из «разверни дерево рекурсии и просуммируй работу по уровням» в «подставь $a$, $b$ и $f(n)$ в формулу и сравни два показателя степени». Это экономит время в первую очередь потому, что позволяет мгновенно сравнивать варианты дизайна алгоритма ещё до того, как ты написал и протестировал код: если ты видишь, что твоя идея даёт соотношение $T(n) = 4T(n/2) + O(n)$, ты сразу знаешь, что это случай 1 и итоговая сложность $\Theta(n^2)$ — и можешь сразу спросить себя, нельзя ли уменьшить число подзадач $a$ хитрым алгебраическим трюком (спойлер: именно так рождается умножение Карацубы, о котором пойдёт речь дальше в этом уроке, и умножение Штрассена матриц — тот же трюк, но для матриц, сокращающий восемь произведений блоков до семи и снижающий показатель степени с 3 до $\log_2 7 \approx 2.807$).

Бинарный поиск и быстрое возведение в степень

Интуиция

Оба алгоритма этого раздела — вырожденные, «однорукие» случаи парадигмы: вместо того чтобы порождать несколько подзадач на каждом уровне, они порождают ровно одну. Формально это означает $a = 1$ в терминах master theorem, а интуитивно — что дерево рекурсии здесь вырождается в прямую линию, а не ветвится. Именно поэтому оба алгоритма работают за логарифмическое время: глубина рекурсии равна $\log_b n$, и на каждом уровне выполняется $O(1)$ (или близкая к константе) работы, а суммировать по единственной ветке — не то же самое, что суммировать по экспоненциально растущему числу листьев.

Определение

Бинарный поиск как «разделяй и властвуй»:

1. Разделение. Сравнить искомое значение с элементом посередине отсортированного массива. По результату сравнения задача сводится к поиску в одной из двух половин (левой или правой) — вторая половина отбрасывается целиком, без какой-либо дальнейшей работы с ней.
2. Решение. Рекурсивно искать в выбранной половине.
3. Объединение. Не требуется вовсе: ответ на подзадачу — это уже готовый ответ на исходную задачу, комбинировать нечего.

Быстрое возведение в степень как «разделяй и властвуй»:

1. Разделение. Свести вычисление $x^n$ к вычислению $x^{n/2}$ — то есть к ровно одной подзадаче половинного размера (при чётном $n$; при нечётном $n$ добавляется один лишний множитель $x$).
2. Решение. Рекурсивно вычислить $x^{n/2}$.
3. Объединение. Возвести результат в квадрат: $x^n = (x^{n/2})^2$ (и домножить на $x$, если $n$ было нечётным) — одна операция умножения, $O(1)$.

Разбор примеров

Пример 1 (трассировка бинарного поиска). Ищем 23 в отсортированном массиве [2, 5, 8, 12, 16, 23, 38, 45, 50, 63] (индексы 0–9). Середина — индекс 4, значение 16. 23 > 16 → отбрасываем всю левую половину целиком, продолжаем поиск в [23, 38, 45, 50, 63] (индексы 5–9). Новая середина — индекс 7, значение 45. 23 < 45 → отбрасываем правую половину, продолжаем в [23, 38] (индексы 5–6). Середина — индекс 5, значение 23. Совпадение — найдено за 3 сравнения, при том что линейный перебор потребовал бы до 10 сравнений.

Пример 2 (быстрое возведение в степень, рекурсивно). Вычислим $3^{13}$. Поскольку $13$ нечётно: $3^{13} = 3 \cdot (3^6)^{2/2}$... аккуратнее распишем рекурсию: $3^{13} = 3 \cdot 3^{12} = 3 \cdot (3^6)^2$; $3^6 = (3^3)^2$; $3^3 = 3 \cdot 3^2 = 3 \cdot (3^1)^2$; $3^1 = 3$ (база рекурсии). Разворачивая обратно: $3^1 = 3$; $3^3 = 3 \cdot 3^2 = 3 \cdot 9 = 27$; $3^6 = 27^2 = 729$; $3^{12} = 729^2 = 531\,441$; $3^{13} = 3 \cdot 531\,441 = 1\,594\,323$. Всего потребовалось 6 умножений (по одному на каждый уровень рекурсии плюс поправки на нечётность), вместо 12 умножений при наивном последовательном перемножении 3 * 3 * 3 * ... * 3 тринадцать раз.

def fast_power(x, n):
    if n == 0:
        return 1
    half = fast_power(x, n // 2)
    if n % 2 == 0:
        return half * half
    else:
        return half * half * x

print(fast_power(3, 13))  # 1594323

Пример 3 (модулярное возведение в степень — почему это не просто учебная задача). В реальных численных и криптографических библиотеках почти никогда не нужна сама по себе гигантская степень числа — нужен остаток от деления на большое число $m$ (модулярная арифметика), например в алгоритме RSA при шифровании и расшифровке. Наивно вычислить $x^n$, а потом взять остаток, невозможно уже для не очень больших $n$ — число попросту не поместится в память. Но если брать остаток по модулю $m$ на каждом шаге рекурсии, а не в конце, все промежуточные числа остаются ограниченного размера, и вся идея быстрого возведения в степень сохраняется без изменений:

def fast_power_mod(x, n, m):
    if n == 0:
        return 1 % m
    half = fast_power_mod(x, n // 2, m)
    result = (half * half) % m
    if n % 2 == 1:
        result = (result * x) % m
    return result

fast_power_mod(7, 128, 1_000_000_007)  # быстро, за 7 уровней рекурсии

Такое модулярное возведение в степень — это ровно та функция, которая используется в Python как третий необязательный аргумент встроенного pow(x, n, m), а быстрое (не обязательно модулярное) возведение чисел, матриц и полиномов в степень заложено внутрь numpy.linalg.matrix_power и аналогичных функций в других численных библиотеках — везде, где нужно вычислить большую степень объекта, для которого умножение определено, но само по себе дорого.

Почему это важно

Оба алгоритма демонстрируют важный частный случай master theorem, который легко упустить: если у тебя ровно одна подзадача на каждом уровне ($a=1$), то независимо от того, насколько тяжёл шаг объединения, ты почти всегда получаешь логарифмическую или близкую к ней сложность — потому что дерево рекурсии не ветвится, а вытягивается в линию глубиной $\log_b n$. Это резко контрастирует с интуицией, будто рекурсия по своей природе означает ветвление и экспоненциальный рост: как ты увидишь в следующем разделе на примере наивного вычисления чисел Фибоначчи, дело не в самой рекурсии, а в том, сколько подзадач она порождает на каждом уровне и пересекаются ли они между собой.

Умножение Карацубы и сравнение с динамическим программированием

Интуиция

Школьный способ умножения двух $n$-значных чисел «в столбик» требует порядка $n^2$ операций умножения однозначных цифр — примерно так, как если бы к рекуррентному соотношению вида $T(n) = 4T(n/2) + O(n)$ применить master theorem: $n^{\log_2 4} = n^2$, случай 1, и правда $\Theta(n^2)$. В 1960 году советский математик Анатолий Карацуба, тогда студент, на семинаре Андрея Колмогорова (у которого, к слову, несколькими годами позже в Москве учился и Тони Хоар, придумавший быструю сортировку — оба алгоритма из этого блока курса связаны с одной и той же московской математической школой) нашёл способ обойтись не четырьмя, а всего тремя умножениями половинного размера — и этого небольшого на первый взгляд сокращения хватает, чтобы асимптотически обогнать школьный способ.

Теорема

Алгоритм умножения Карацубы. Пусть нужно перемножить два $n$-значных числа $x$ и $y$. Представим каждое как $x = x_1 \cdot 10^{m} + x_0$ и $y = y_1 \cdot 10^{m} + y_0$, где $m = n/2$, а $x_1, y_1$ — старшие половины цифр, $x_0, y_0$ — младшие. Школьный способ требует четырёх произведений половинного размера: $x_1y_1$, $x_1y_0$, $x_0y_1$, $x_0y_0$. Карацуба заметил, что средние слагаемые можно получить всего одним дополнительным умножением вместо двух:

$$z_2 = x_1 y_1, \qquad z_0 = x_0 y_0, \qquad z_1 = (x_1 + x_0)(y_1 + y_0) - z_2 - z_0 = x_1 y_0 + x_0 y_1$$

Итоговое произведение собирается сложением с учётом сдвигов: $xy = z_2 \cdot 10^{2m} + z_1 \cdot 10^{m} + z_0$. Рекуррентное соотношение — $T(n) = 3T(n/2) + O(n)$, где $a=3$, критическая величина $n^{\log_2 3} \approx n^{1.585}$, а $f(n) = O(n)$ растёт медленнее — случай 1 master theorem, значит $T(n) = \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$, что асимптотически быстрее школьного $\Theta(n^2)$.

Разбор примеров

Пример 1 (трассировка на маленьких числах). Перемножим 1234 и 5678 по Карацубе, разбив каждое число пополам: $x_1=12$, $x_0=34$, $y_1=56$, $y_0=78$, $m=2$. Считаем: $z_2 = 12 \cdot 56 = 672$, $z_0 = 34 \cdot 78 = 2652$, $z_1 = (12+34)(56+78) - z_2 - z_0 = 46 \cdot 134 - 672 - 2652 = 6164 - 3324 = 2840$. Собираем: $xy = 672 \cdot 10^4 + 2840 \cdot 10^2 + 2652 = 6\,720\,000 + 284\,000 + 2652 = 7\,006\,652$. Проверка прямым умножением: $1234 \times 5678 = 7\,006\,652$ — совпадает, и потребовалось всего три умножения двузначных чисел ($12\times56$, $34\times78$, $46\times134$) вместо четырёх, которые понадобились бы школьному способу.

Пример 2 (во сколько раз быстрее на больших числах). Для чисел с $n = 1024$ цифрами (типичный порядок для криптографических ключей) школьное умножение потребует порядка $n^2 = 1\,048\,576$ элементарных операций. Карацуба потребует порядка $n^{\log_2 3} = 1024^{1.585} \approx 65\,536 \cdot \sqrt[3]{...}$ — если считать точнее через $1024 = 2^{10}$, то $n^{\log_2 3} = (2^{10})^{\log_2 3} = 2^{10 \log_2 3} = 3^{10} = 59\,049$. Разница почти в 18 раз — и она растёт вместе с $n$, потому что показатель $1.585$ асимптотически меньше $2$.

Пример 3 (реализация).

def karatsuba(x, y):
    if x < 10 or y < 10:  # база рекурсии: однозначные числа
        return x * y

    n = max(len(str(x)), len(str(y)))
    m = n // 2

    x1, x0 = divmod(x, 10 ** m)
    y1, y0 = divmod(y, 10 ** m)

    z2 = karatsuba(x1, y1)
    z0 = karatsuba(x0, y0)
    z1 = karatsuba(x1 + x0, y1 + y0) - z2 - z0

    return z2 * 10 ** (2 * m) + z1 * 10 ** m + z0

print(karatsuba(1234, 5678))  # 7006652

Разделяй и властвуй против динамического программирования

Три рекурсивных вызова в Карацубе — karatsuba(x1, y1), karatsuba(x0, y0), karatsuba(x1+x0, y1+y0) — работают с тремя разными парами чисел. Ни один из этих вызовов никогда не пересчитывает то, что уже посчитал другой: подзадачи не пересекаются, кэшировать нечего, и в этом алгоритм Карацубы устроен точно так же, как quicksort или merge sort — раздели на непересекающиеся куски, реши каждый независимо, объедини.

Сравни это с наивной рекурсией для чисел Фибоначчи из урока 270, которая на первый взгляд тоже выглядит как «разделяй и властвуй»: $F(n) = F(n-1) + F(n-2)$ — разделение на две подзадачи, рекурсивное решение, объединение сложением. Формально это тот же трёхшаговый рецепт. Но есть решающее отличие: подзадача $F(n-2)$ не независима от подзадачи $F(n-1)$ — она является частью её собственного дерева вызовов. $F(n-1)$ в процессе своего вычисления сам вызовет $F(n-2)$, и в итоге $F(n-2)$ будет вычислена дважды: один раз напрямую, второй раз — как подзадача внутри вычисления $F(n-1)$. На больших $n$ такие повторы множатся экспоненциально: $F(n-3)$ вычисляется трижды, $F(n-4)$ — пять раз, и так далее.

Ключевое различие. В «разделяй и властвуй» подзадачи, порождаемые разделением, не пересекаются: каждая подзадача решается ровно один раз, кэшировать результаты незачем. В динамическом программировании подзадачи пересекаются: одна и та же меньшая подзадача многократно возникает внутри разных более крупных подзадач, и именно поэтому DP запоминает (мемоизирует или табулирует) уже посчитанные результаты — иначе экспоненциальный взрыв повторных вычислений, как в наивной рекурсии Фибоначчи, неизбежен.

Наивная рекурсия Фибоначчи и merge sort формально имеют одинаковую структуру рекуррентного вызова — «две подзадачи плюс объединение», — но качественно устроены абсолютно по-разному. Дерево вызовов merge sort на массиве из $n=8$ элементов содержит ровно $n-1=7$ узлов слияния, каждый над своим уникальным непересекающимся диапазоном индексов — ни один диапазон не повторяется дважды. Дерево вызовов наивного Фибоначчи для $F(6)$, напротив, вызывает $F(4)$ дважды, $F(3)$ трижды, $F(2)$ пять раз — те же самые входные значения снова и снова пересчитываются с нуля в разных ветвях. Именно из-за этого наивная рекурсия Фибоначчи работает за экспоненциальное время $O(2^n)$, а не за $O(n \log n)$, как можно было бы наивно ожидать по аналогии с merge sort, — и именно это отличие является тем самым признаком, по которому стоит выбирать между «просто написать рекурсию как есть» (если подзадачи не пересекаются — это divide and conquer) и «добавить мемоизацию или табулирование» (если подзадачи пересекаются — это сигнал для динамического программирования).

Почему это важно

Вопрос «пересекаются ли подзадачи между собой?» — это, пожалуй, самый практически полезный диагностический вопрос из всего этого урока. Он занимает буквально одну секунду размышления перед тем, как садиться писать рекурсивный алгоритм, но экономит часы отладки: если ответ «нет, не пересекаются» — пиши обычную рекурсию по трёхшаговой схеме без всякого кэширования, как в Карацубе или merge sort. Если ответ «да, пересекаются» — сразу добавляй мемоизацию (или переходи к табулированию), потому что без неё та же самая логика неизбежно скатится в экспоненциальную сложность, как в наивном Фибоначчи, независимо от того, насколько элегантно выглядит рекурсивный код.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Назови три шага парадигмы «разделяй и властвуй» и для каждого шага сортировки слиянием (merge sort) укажи, тривиален он или содержит основную вычислительную работу алгоритма.

Задание 2: Объясни, почему у быстрой сортировки (quicksort) шаг объединения полностью отсутствует, в отличие от merge sort.

Задание 3: Сколько уровней рекурсии потребует бинарный поиск для массива из $1\,000\,000$ элементов?

Задание 4: Дано рекуррентное соотношение $T(n) = 4T(n/2) + O(n)$. Определи $a$, $b$, $f(n)$, вычисли критическую величину $n^{\log_b a}$, определи случай master theorem и итоговую сложность.

Задание 5: Дано рекуррентное соотношение $T(n) = 2T(n/2) + O(n)$ (сортировка слиянием). Определи случай master theorem и итоговую сложность.

Задание 6: Проследи бинарный поиск числа 23 в массиве [2, 5, 8, 12, 16, 23, 38, 45, 50, 63], указав середину и направление сужения на каждом шаге.

Задание 7: Реализуй рекурсивную функцию быстрого возведения в степень fast_power(x, n) и вычисли с её помощью $3^{13}$.

def fast_power(x, n):
    if n == 0:
        return 1
    half = fast_power(x, n // 2)
    return half * half * x if n % 2 else half * half

print(fast_power(3, 13))

Задание 8: Для чисел с $n=1024$ цифрами сравни показатели степени в оценках сложности школьного умножения и умножения Карацубы. Какое асимптотически быстрее и почему?

Задание 9: Укажи, пересекаются ли подзадачи в (а) сортировке слиянием и (б) наивной рекурсии вычисления чисел Фибоначчи $F(n)=F(n-1)+F(n-2)$. Какой подход (обычная рекурсия или рекурсия с мемоизацией) уместен в каждом случае?

Задание 10: Дано рекуррентное соотношение бинарного поиска $T(n) = T(n/2) + O(1)$. Определи $a$, $b$, $f(n)$ и результат по master theorem.

Средние задания (11–20)

Задание 11: Дано рекуррентное соотношение $T(n) = T(n/2) + O(n^2)$. Определи случай master theorem (проверь условие регулярности) и итоговую сложность.

Задание 12: Дано рекуррентное соотношение наивного рекурсивного умножения матриц $n\times n$ через разбиение на блоки: $T(n) = 8T(n/2) + O(n^2)$. Определи случай master theorem и итоговую сложность, сравни с обычным тройным циклом умножения матриц.

Задание 13: Проследи быстрое возведение в степень для $x^{20}$: сколько умножений потребуется и сколько потребовалось бы наивному последовательному перемножению?

Задание 14: Опиши, почему шаг «объединение» в алгоритме поиска максимальной подпоследовательности (задача о максимальном подмассиве) не тривиален, в отличие от бинарного поиска, и что именно приходится проверять дополнительно.

Задание 15: Объясни в терминах master theorem, почему бинарный поиск называют «вырожденным» случаем «разделяй и властвуй» по сравнению с merge sort.

Задание 16: Проследи умножение Карацубы для чисел 21 и 34 (разбиение пополам по одной цифре: $x_1=2,x_0=1,y_1=3,y_0=4$), вычисли $z_2$, $z_0$, $z_1$ и итоговый результат.

Задание 17: Дано рекуррентное соотношение $T(n) = 3T(n/3) + O(n\log n)$. Определи случай master theorem и итоговую сложность.

Задание 18: Алгоритм quickselect в среднем случае описывается соотношением $T(n)=T(n/2)+O(n)$ (рекурсия только в одну из двух частей после разбиения). Определи случай master theorem, проверь условие регулярности и найди итоговую сложность.

Задание 19: Объясни своими словами, почему для вычисления чисел Фибоначчи нужно динамическое программирование (урок 270), а для сортировки слиянием — нет, хотя оба алгоритма формально рекурсивны и оба «делят задачу на две части плюс объединение».

Задание 20: Для наивной рекурсии $F(5)=F(4)+F(3)$ построй (опиши текстом) дерево вызовов и посчитай, сколько раз в нём вычисляется $F(2)$.

Продвинутые задания (21–30)

Задание 21: Для рекуррентного соотношения умножения матриц $T(n)=8T(n/2)+O(n^2)$ объясни через рассуждение об уровнях дерева рекурсии (без прямой ссылки на формулу master theorem), почему именно листья дерева определяют итоговую асимптотику.

Задание 22: Реализуй полную функцию умножения Карацубы для произвольных больших целых чисел (без ограничения на число цифр), включая обработку случаев, когда числа имеют разную длину.

def karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y

    n = max(len(str(abs(x))), len(str(abs(y))))
    m = n // 2

    x1, x0 = divmod(x, 10 ** m)
    y1, y0 = divmod(y, 10 ** m)

    z2 = karatsuba(x1, y1)
    z0 = karatsuba(x0, y0)
    z1 = karatsuba(x1 + x0, y1 + y0) - z2 - z0

    return z2 * 10 ** (2 * m) + z1 * 10 ** m + z0

Задание 23: Объясни, почему на практике библиотеки длинной арифметики не применяют Карацубу для маленьких чисел (скажем, короче 20–30 цифр), а переключаются на неё только начиная с определённого порога — аналогично идее гибридных сортировок из прошлого урока.

Задание 24: Дано рекуррентное соотношение $T(n) = 2T(n/2) + n/\log n$. Проверь, применим ли master theorem в стандартной формулировке этого урока, и объясни, почему.

Задание 25: Опиши идею вычисления $n$-го числа Фибоначчи за $O(\log n)$ через быстрое возведение в степень матрицы $\begin{pmatrix}1&1\\1&0\end{pmatrix}$ в степень $n$, и почему это быстрее, чем DP-решение за $O(n)$ из урока 270.

Задание 26: Классический алгоритм поиска ближайшей пары точек на плоскости методом «разделяй и властвуй» имеет соотношение $T(n)=2T(n/2)+O(n)$ (после предварительной сортировки точек по координате). Определи итоговую сложность и опиши в общих словах, что должен делать нетривиальный шаг объединения.

Задание 27: Сравни число листьев дерева рекурсии для сортировки слиянием и для умножения Карацубы при одинаковом размере входа $n=16$.

Задание 28: Спроектируй алгоритм «разделяй и властвуй» для одновременного поиска минимума и максимума массива, использующий меньше сравнений, чем наивный проход с $2n-2$ сравнениями, и оцени итоговое число сравнений.

Задание 29: Построение сбалансированного KD-дерева (урок 257) из $n$ точек описывается рекуррентным соотношением $T(n)=2T(n/2)+O(n)$ (поиск медианы по выбранной оси и разбиение точек занимает линейное время на уровень). Определи итоговую сложность построения и укажи, с каким уже разобранным в курсе алгоритмом совпадает это рекуррентное соотношение.

Задание 30: Предложи (на уровне описания шагов) алгоритм поиска элемента большинства (значения, встречающегося больше чем в половине элементов массива) методом «разделяй и властвуй», оцени его сложность через master theorem и объясни, почему для этой конкретной задачи мемоизация не даёт никакого выигрыша.

Частые ошибки

Ошибка 1. Считают, что в любом алгоритме «разделяй и властвуй» основная работа обязательно происходит на шаге объединения — по аналогии с merge sort, который обычно разбирают первым.

Как выглядит: при анализе нового рекурсивного алгоритма автоматически ищут «функцию слияния» и удивляются, если её не оказывается вовсе, как в quicksort или Карацубе.

Почему возникает: merge sort часто становится первым подробно разобранным примером D&C, и его структура — тяжёлое объединение, лёгкое разделение — воспринимается как норма, а не как один из двух возможных полюсов.

Как правильно: явно проверять оба шага по отдельности для каждого нового алгоритма — иногда тяжело разделение (quicksort), иногда объединение (merge sort), а иногда работа распределена между всеми тремя шагами примерно поровну.

Ошибка 2. Пытаются применить master theorem к рекуррентным соотношениям, не имеющим вида $T(n) = aT(n/b) + f(n)$ — например, к $T(n) = T(n-1) + n$ (линейное, а не пропорциональное уменьшение размера).

Как выглядит: подставляют в формулу master theorem соотношение, где размер подзадачи уменьшается на константу (n-1), а не делится на константу (n/b), и получают бессмысленный или неопределённый результат.

Почему возникает: оба типа соотношений выглядят одинаково «рекурсивно» на глаз, но описывают качественно разные семейства алгоритмов — линейную рекурсию (как в наивном факториале) и настоящее деление задачи пополам.

Как правильно: прежде чем применять master theorem, явно убедиться, что размер подзадачи именно делится на константу $b>1$, а не уменьшается на константу — для линейных рекурсий вида $T(n)=T(n-1)+f(n)$ асимптотика находится прямым суммированием, а не через master theorem.

Ошибка 3. Присваивают ответ $\Theta(f(n))$ для случая 3, не проверив условие регулярности $a\cdot f(n/b) \leq c\cdot f(n)$.

Как выглядит: видят, что $f(n)$ растёт быстрее критической величины $n^{\log_b a}$, и сразу делают вывод о случае 3, пропуская проверку дополнительного условия.

Почему возникает: условие регулярности выглядит формальной технической деталью, которую на практике для большинства «нормальных» функций (многочленов, произведений многочлена на логарифм) можно пропустить без вреда — что создаёт ложное ощущение, будто оно не нужно вообще.

Как правильно: для «хороших» функций (степенны́х, степенных умноженных на логарифм) условие регулярности почти всегда выполняется автоматически и его можно проверять быстро, но для более экзотических $f(n)$ стоит явно её прописать — иначе легко получить случай master theorem, который формально к соотношению неприменим.

Ошибка 4. Путают динамическое программирование и «разделяй и властвуй» просто по признаку «здесь есть рекурсия», не проверяя, пересекаются ли подзадачи.

Как выглядит: пишут наивную рекурсию для задачи с пересекающимися подзадачами (вроде чисел Фибоначчи или задачи о рюкзаке), ожидая производительности merge sort, и удивляются экспоненциальному времени работы.

Почему возникает: оба подхода формально выглядят как «раздели задачу на подзадачи и реши их рекурсивно» — разница проявляется только при внимательном анализе того, встречаются ли одинаковые подзадачи повторно в разных ветвях дерева вызовов.

Как правильно: перед тем как писать рекурсию, явно задать себе вопрос «может ли одна и та же подзадача (с теми же аргументами) встретиться больше одного раза?» — если да, нужна мемоизация или табулирование (динамическое программирование из урока 270), если нет — можно писать чистую рекурсию без кэша.

Ошибка 5. Реализуют рекурсивные алгоритмы вроде Карацубы или сортировки слиянием без порога переключения на простой алгоритм для маленьких подзадач.

Как выглядит: рекурсия доходит до подзадач размера 2–3 элемента и продолжает по той же тяжёлой рекурсивной схеме, вместо того чтобы решить их напрямую.

Почему возникает: асимптотическая оценка сложности не учитывает константные накладные расходы на каждый рекурсивный вызов (создание стекового кадра, выделение памяти под промежуточные объекты), которые становятся заметны именно на маленьких подзадачах.

Как правильно: добавлять порог (обычно определяемый эмпирически, часто 10–30 элементов или цифр), ниже которого алгоритм переключается на простую нерекурсивную реализацию — тот же приём, что используется в гибридных сортировках вроде Timsort из прошлого урока.

Ошибка 6. Забывают, что при бинарном поиске и быстром возведении в степень объединять по сути нечего, и пытаются искусственно добавить шаг объединения там, где ответ подзадачи уже является готовым ответом.

Как выглядит: при реализации бинарного поиска после рекурсивного вызова добавляют лишние проверки или преобразования результата, хотя правильный подход — просто вернуть то, что вернула рекурсия в выбранную половину.

Почему возникает: привычка к трёхшаговой схеме с обязательным нетривиальным объединением (закреплённая примерами вроде merge sort) создаёт ощущение, будто объединение должно быть содержательным шагом всегда.

Как правильно: помнить, что вырожденные случаи с $a=1$ (одна подзадача на уровень) часто вовсе не требуют объединения — ответ подзадачи и есть ответ исходной задачи, и пытаться придумать искусственный шаг объединения там, где его нет, — лишняя и потенциально ошибочная работа.

Главное запомнить

• «Разделяй и властвуй» — общая парадигма из трёх шагов: разделение задачи на подзадачи того же типа меньшего размера, рекурсивное решение каждой подзадачи, объединение решений подзадач в решение исходной задачи.

• Quicksort и merge sort — не два разных алгоритма, а два разных распределения работы по этим трём шагам: у quicksort тяжёлое разделение и пустое объединение, у merge sort — наоборот.

• Основная теорема о рекуррентных соотношениях (master theorem) для $T(n)=aT(n/b)+f(n)$ сравнивает $f(n)$ с критической величиной $n^{\log_b a}$ и даёт один из трёх ответов в зависимости от того, что растёт быстрее — листья дерева рекурсии или объединение на верхнем уровне.

• Случай 1 (листья дороже) даёт $T(n)=\Theta(n^{\log_b a})$; случай 2 (баланс) даёт $T(n)=\Theta(n^{\log_b a}\log^{k+1} n)$; случай 3 (объединение дороже, при выполнении условия регулярности) даёт $T(n)=\Theta(f(n))$.

• Между тремя случаями существуют «щели», в которые master theorem в этой формулировке не попадает — в таких случаях нужны более общие методы анализа (например, метод Акра–Базци).

• Бинарный поиск и быстрое возведение в степень — вырожденные случаи парадигмы с $a=1$: дерево рекурсии не ветвится, а вытягивается в цепочку глубиной $\log_b n$, объединение обычно тривиально или отсутствует вовсе.

• Умножение Карацубы сокращает четыре умножения половинного размера до трёх алгебраическим трюком, снижая сложность умножения больших чисел с $\Theta(n^2)$ до $\Theta(n^{\log_2 3})\approx\Theta(n^{1.585})$.

• Ключевое отличие от динамического программирования: в «разделяй и властвуй» подзадачи не пересекаются, и каждая решается ровно один раз без надобности в кэшировании; в динамическом программировании подзадачи пересекаются, и без мемоизации или табулирования возникает экспоненциальный взрыв повторных вычислений.

• Формальное сходство рекуррентной структуры («раздели на части плюс объедини») не гарантирует одинакового поведения алгоритма — решающим является именно вопрос о пересечении подзадач, а не форма рекурсии сама по себе.

• Быстрое возведение в степень и родственная ему схема лежат в основе модулярной арифметики в криптографии, функций численных библиотек вроде numpy.linalg.matrix_power, а рекурсивное деление пространства пополам той же парадигмой строит KD-деревья для поиска ближайших соседей.

Связь с темами курса

Что нужно было знать до этого урока

Этот урок прямо опирается на быструю сортировку (урок 267) и сортировку слиянием (урок 268) — оба алгоритма были представлены как конкретные примеры «разделяй и властвуй», а здесь эта парадигма наконец осмыслена как самостоятельный общий класс со своим собственным инструментом анализа. Также используются рекуррентные соотношения и логарифмическая нотация из урока 251 про сложность алгоритмов, и напрямую противопоставляется динамическому программированию из урока 270 — без понимания разницы между «оптимальная подструктура плюс перекрывающиеся подзадачи» (DP) и «независимые подзадачи» (D&C) трудно осмысленно выбирать между двумя подходами при проектировании нового рекурсивного алгоритма.

Что изучить дальше

Следующий урок 273 разбирает backtracking (поиск с возвратом) — ещё одну рекурсивную парадигму, но устроенную принципиально иначе: вместо того чтобы делить задачу на независимые подзадачи заранее (как в D&C) или запоминать решения перекрывающихся подзадач (как в DP), backtracking исследует пространство решений шаг за шагом, откатываясь назад («возвращаясь»), как только становится ясно, что текущий частичный вариант решения не может привести к успеху. Вместе три парадигмы — динамическое программирование, «разделяй и властвуй» и backtracking — покрывают подавляющее большинство рекурсивных алгоритмических приёмов, с которыми ты столкнёшься в дальнейшем курсе, и умение быстро распознать, какая из них подходит к конкретной новой задаче, — один из самых ценных практических навыков алгоритмического мышления.

Где это нужно в жизни

🌳 Структуры данных для ML. Построение сбалансированного KD-дерева из урока 257 подчиняется ровно тому же рекуррентному соотношению $T(n)=2T(n/2)+O(n)$, что и merge sort, и по той же master theorem даёт $\Theta(n\log n)$ на построение — а ускоренный поиск $k$ ближайших соседей поверх такого дерева напрямую используется в рекомендательных системах и компонентах поиска релевантных объектов (retrieval) семантического поиска.

🔢 Численные библиотеки. Быстрое возведение в степень за $O(\log n)$ лежит в основе функций вроде numpy.linalg.matrix_power и встроенной модулярной версии pow(x, n, m) в Python — везде, где нужно быстро вычислить большую степень числа, матрицы или полинома.

📡 Обработка сигналов и длинные последовательности. Быстрое преобразование Фурье (FFT), используемое в цифровой обработке сигналов и в некоторых архитектурах для работы с длинными последовательностями, построено по той же схеме «разделяй и властвуй»: разбиение полинома (или сигнала) на части с чётными и нечётными индексами, рекурсивное решение для каждой части, объединение через формулу «бабочки» (butterfly) — та же трёхшаговая идея, доведённая до алгоритма со сложностью $\Theta(n\log n)$ вместо наивных $\Theta(n^2)$.

🔐 Криптография и безопасность. Модулярное быстрое возведение в степень — обязательный строительный блок алгоритма RSA и других криптосистем на основе теории чисел, где приходится оперировать числами в сотни и тысячи битов, для которых наивное возведение в степень попросту невыполнимо за разумное время.

Интересные факты

• Фраза «разделяй и властвуй» (divide et impera) — не изобретение программистов, а древняя политическая максима, которую приписывают ещё римским правителям и подробно обсуждал Никколо Макиавелли; когда computer science понадобилось название для алгоритмической стратегии дробления задач, эта военно-политическая метафора оказалась настолько точной, что прижилась без изменений.

• Умножение Карацубы открыл в 1960 году 23-летний студент Анатолий Карацуба на семинаре Андрея Колмогорова в МГУ — том самом Колмогорове, у которого несколькими годами позже учился Тони Хоар, придумавший быструю сортировку: два алгоритма из соседних уроков этого курса восходят к одной и той же московской математической школе теории вероятностей и алгоритмов.

• Алгоритм Штрассена для умножения матриц (1969) — это буквально «Карацуба для матриц»: он сокращает восемь рекурсивных произведений блоков до семи хитрой алгебраической комбинацией, снижая показатель степени с $3$ до $\log_2 7 \approx 2.807$ — небольшое на первый взгляд число дало толчок к десятилетиям исследований ещё более быстрых алгоритмов умножения матриц, вплоть до теоретических методов с показателем ниже $2.4$.

• Master theorem в её нынешнем «удобном для подстановки» виде была формализована лишь в 1980 году в статье Джона Бентли, Доротеи Хакен и Джеймса Сакса — то есть спустя десятилетия после того, как сами алгоритмы «разделяй и властвуй» (сортировка слиянием 1945 года, быстрая сортировка 1959–1961 годов) уже активно использовались на практике безо всякого единого инструмента для их анализа.

Лайфхаки

• Перед тем как писать рекурсивный алгоритм, сразу задай себе вопрос «могут ли одинаковые подзадачи встретиться повторно в разных ветвях рекурсии?» — ответ «нет» указывает на «разделяй и властвуй» (кэш не нужен), ответ «да» — на динамическое программирование (нужна мемоизация).

• Используй master theorem как быструю проверку интуиции при проектировании нового рекурсивного алгоритма: прежде чем писать и тестировать код, подставь предполагаемые $a$, $b$ и $f(n)$ и прикинь итоговую асимптотику — это дешевле, чем сначала реализовать алгоритм, а потом обнаружить, что он асимптотически не лучше наивного решения.

• Если в рекуррентном соотношении $a=1$ (одна подзадача на уровень), почти наверняка получится логарифмическая или близкая к ней сложность, независимо от того, насколько тяжело выглядит объединение, — не пугайся рекурсии в бинарном поиске или быстром возведении в степень, там нет экспоненциального взрыва, потому что дерево вызовов не ветвится.

• Ищи возможность сократить число подзадач $a$ алгебраическим трюком, как это сделали Карацуба для умножения чисел и Штрассен для умножения матриц, — снижение $a$ даже на единицу (с 4 до 3, с 8 до 7) напрямую снижает показатель степени $\log_b a$ в итоговой асимптотике.

• Для рекурсивных алгоритмов, которые пишешь сам, всегда предусматривай порог переключения на простую нерекурсивную реализацию на маленьких подзадачах — асимптотика ничего не говорит о константных накладных расходах, а они особенно заметны именно на малых размерах входа.

• Если не можешь однозначно отнести $f(n)$ ни к одному из трёх случаев master theorem (например, из-за дробных степеней логарифма) — не пытайся «подогнать» результат под ближайший похожий случай; признай, что стандартная формулировка теоремы здесь не работает, и либо разворачивай дерево рекурсии вручную, либо ищи более общий метод анализа.

• Держи в голове конкретную пару контрастных примеров — merge sort (непересекающиеся подзадачи, $O(n\log n)$) и наивный Фибоначчи (пересекающиеся подзадачи, $O(2^n)$) — как быстрый ментальный тест: если новая задача больше похожа по структуре подзадач на первую, пиши прямую рекурсию, если на вторую — сразу добавляй кэш.

Парадигма «разделяй и властвуй» — это, пожалуй, самый экономный интеллектуальный инструмент из всех, что встретились тебе в этом блоке курса: вместо десятка отдельных алгоритмов, которые пришлось бы запоминать по отдельности, ты теперь держишь в голове одну трёхшаговую схему и один универсальный способ быстро оценить её сложность — master theorem. Быстрая сортировка и сортировка слиянием оказались не двумя разрозненными рецептами, а двумя полюсами одного и того же спектра; бинарный поиск и быстрое возведение в степень — тем же приёмом, доведённым до вырожденного, но невероятно полезного предела; а умножение Карацубы показало, что иногда достаточно одного алгебраического наблюдения, чтобы асимптотически обогнать способ, которым люди умножали числа столетиями. Дальше в курсе, когда ты столкнёшься с новым рекурсивным алгоритмом — будь то FFT в обработке сигналов, построение очередного вида дерева поиска или что-то ещё не пройденное, — у тебя уже есть чёткий чек-лист: найти три шага, проверить, пересекаются ли подзадачи, и при необходимости подставить $a$, $b$ и $f(n)$ в master theorem, чтобы получить асимптотику за секунды, а не за долгое ручное разворачивание дерева рекурсии.