ALGO·III Алгоритмы Глава 21 из 65
Разделяй и властвуй
Два московских сюжета: аспирант, опровергший Колмогорова за неделю, и английский стажёр, который сортировал русские слова для машинного перевода. Оба резали задачу пополам, и на этом приёме держатся алгоритмы, которые работают внутри каждого компьютера.
Алгоритмы
- 20 Поиск и сортировка
- 21 Разделяй и властвуй вы здесь
- 22 Динамика
- 23 Жадные
- 24 Кратчайшие пути
- 25 Потоки и пары
- 26 Случайность
- 27 Поиск в тексте
Опирается на: 20 · Турнир сортировок 09 · Задача внутри задачи
Что вы унесёте из главы
- узнавать задачи, которые решаются разрезанием пополам, и писать для них рекурсию
- считать время работы через дерево рекурсии и основную теорему
- почему быстрая сортировка быстрая — и когда она становится медленной
Прошлая глава кончилась тупиком. Сортировки вставками и выбором делают порядка $n^2$ сравнений, и ни быстрый процессор, ни аккуратный код этого не исправят: на миллиарде чисел квадрат даёт порядка $10^{18}$ сравнений, годы работы. Нужна другая идея. Её принесли два человека, которые почти одновременно оказались в Московском университете и, не сговариваясь, нашли один и тот же приём.
Москва, 1960. Гипотеза Колмогорова
Школьный способ и правда квадратичный: каждая цифра верхнего числа умножается на каждую цифру нижнего, получается таблица $n \times n$. Двузначные числа — четыре умножения цифр, десятизначные — сто, тысячезначные — миллион.
Три умножения вместо четырёх
Карацуба начал с того, что разрезал каждое число пополам. Возьмём четырёхзначные $x = 1234$ и $y = 5678$. Их можно записать как $x = 12 \cdot 100 + 34$ и $y = 56 \cdot 100 + 78$. В общем виде, если у чисел $n$ цифр и $B = 10^{n/2}$:
$$x = a \cdot B + b, \qquad y = c \cdot B + d.$$Перемножим, раскрыв скобки:
$$x \cdot y = ac \cdot B^2 + (ad + bc) \cdot B + bd.$$Умножение на $B$ — приписывание нулей, его можно не считать. Остаются четыре умножения половинок: $ac$, $ad$, $bc$, $bd$. Если делать их тем же способом рекурсивно, ничего не выиграем: четыре задачи вдвое меньше — это опять $n^2$ (почему — посчитаем ниже). А Карацуба заметил, что средний коэффициент можно получить, не вычисляя $ad$ и $bc$ по отдельности:
$$ad + bc = (a + b)(c + d) - ac - bd.$$
Раскроем скобки в правой части: $(a + b)(c + d) = ac + ad + bc + bd$. Вычтем $ac$ и $bd$ — останется $ad + bc$.
Проверка уместилась в строчку, а следствие у неё большое. $ac$ и $bd$ нам всё равно нужны, поэтому средний коэффициент обходится одним новым умножением, $(a+b)(c+d)$, и половинки перемножаются три раза вместо четырёх. Для нашего примера: $ac = 12 \cdot 56 = 672$, $bd = 34 \cdot 78 = 2652$, $(a+b)(c+d) = 46 \cdot 134 = 6164$, средний коэффициент $6164 - 672 - 2652 = 2840$. Итого $672 \cdot 10^4 + 2840 \cdot 10^2 + 2652 = 7\,006\,652$ — проверьте на калькуляторе.
Одно умножение из четырёх — всего четверть. Но экономия повторяется на каждом уровне рекурсии: каждое из трёх умножений половинок само делается тремя умножениями четвертинок, и так до отдельных цифр. Запустите и посчитайте, сколько умножений цифр понадобится.
На 64-значных числах столбик тратит 4096 умножений цифр, Карацуба — около тысячи. Чем длиннее числа, тем больше разрыв. Ровно $3^6 = 729$ не выходит из-за переносов: сумма $a + b$ бывает на цифру длиннее половинки. Скорости роста эта добавка не меняет.
Колмогорова, по воспоминаниям Карацубы, это сильно взволновало: результат противоречил его гипотезе, которая казалась вполне правдоподобной. На следующем заседании Колмогоров сам рассказал участникам о новом методе — и на этом семинар прекратил работу. В 1962 году Колмогоров написал о методе короткую статью (возможно, вместе с Юрием Офманом) и опубликовал её в «Докладах Академии наук» под фамилиями Карацубы и Офмана. Карацуба узнал о публикации, только когда ему вручили оттиски.
Раздели, реши, склей
Оставим на время умножение. У Карацубы было три шага:
- Раздели задачу на несколько таких же, но меньше: числа — на половинки.
- Реши каждую часть тем же способом — рекурсией, пока части не станут совсем маленькими, как одна цифра.
- Склей ответы частей в ответ всей задачи: сложи с нужными сдвигами.
Этот приём называют «разделяй и властвуй» — по латинской поговорке divide et impera, которую приписывают то Цезарю, то Макиавелли. В программировании он один из главных. Вы уже встречали его в двоичном поиске: делим отрезок пополам, решаем задачу в одной половине, склеивать нечего. Осталось применить его к сортировке, из-за которой мы сюда и пришли.
Сортировка слиянием
Допустим, списки вдвое короче вы сортировать уже умеете. Тогда длинный список сортируется так: отсортировать обе половины, а потом слить их. Сливать две отсортированные колоды легко: смотрим на верхние карты обеих, берём меньшую, повторяем. Попробуйте сами — нажимайте на меньшую из двух верхних карт.
Каждое сравнение отправляет одну карту в результат, поэтому слить две колоды общей длиной $n$ удаётся не больше чем за $n - 1$ сравнений. Слияние — наш шаг «склей», остальное делает рекурсия: половинки сортируются тем же способом, их половинки — тоже, пока не останутся списки из одного элемента, которые уже отсортированы.
Сортировку слиянием описал Джон фон Нейман в 1945 году. Это был один из первых алгоритмов для EDVAC — машины, которую ещё только проектировали. Вот она на Python. Нажмите «Шаги», чтобы увидеть, как рекурсия уходит вглубь и возвращается: справа будут кадры вызовов, каждый со своим кусочком списка.
Сколько это стоит
Сколько сравнений делает сортировка слиянием? Нарисуем все вызовы как дерево. Наверху — один вызов на весь список длины $n$: он сливает две половины, это до $n$ сравнений. Под ним — два вызова на половины: каждый сливает до $n/2$, вместе снова $n$. На следующем уровне — четыре вызова по $n/4$: опять $n$ в сумме. Каждый уровень стоит $n$, а уровней столько, сколько раз $n$ можно поделить пополам до единицы, то есть $\log_2 n$.
Сортировка слиянием упорядочивает $n$ элементов не больше чем за $n \log_2 n$ сравнений.
Для простоты пусть $n$ — степень двойки, $n = 2^k$. Вызов на списке длины $m$ сам делает не больше $m$ сравнений (при слиянии) и ещё два вызова на списках длины $m/2$. На уровне $i$ дерева вызовов (корень — уровень $0$) стоят $2^i$ вызовов, каждый на списке длины $n / 2^i$, и вместе они делают не больше $2^i \cdot n/2^i = n$ сравнений. Уровни с длиной хотя бы 2 — это $i = 0, 1, \ldots, k-1$, их $k = \log_2 n$; на нижнем уровне списки из одного элемента, там сравнений нет. Сумма по уровням — не больше $n \cdot \log_2 n$. Если $n$ не степень двойки, дерево не глубже $\lceil \log_2 n \rceil$, и оценка становится $n \lceil \log_2 n \rceil$.
Миллион чисел — это $\log_2 10^6 \approx 20$ уровней по миллиону сравнений: двадцать миллионов вместо полутриллиона у квадратичных сортировок. Разница в двадцать пять тысяч раз. В прошлой главе мы доказали, что любая сортировка сравнениями делает в худшем случае не меньше $\log_2 n! \approx n \log_2 n$ сравнений. Значит, сортировка слиянием оптимальна: по порядку роста лучше нельзя.
Дерево рекурсии и основная теорема
Тот же приём с деревом считает время любого алгоритма «разделяй и властвуй». Пусть задача размера $n$ делится на $a$ подзадач размера $n/b$, а разделение и склейка стоят порядка $n^d$ действий. Время работы $T(n)$ подчиняется рекуррентному соотношению:
$$T(n) = a \cdot T\!\left(\frac{n}{b}\right) + n^d.$$Сортировка слиянием: $a = 2$, $b = 2$, $d = 1$. Карацуба: $a = 3$, $b = 2$, $d = 1$ (сложения и сдвиги линейны). Умножение половинками без хитрости: $a = 4$, $b = 2$, $d = 1$. Двоичный поиск: $a = 1$, $b = 2$, $d = 0$. Поиграйте с параметрами: на каком уровне дерева сосредоточена работа?
На уровне $i$ стоят $a^i$ подзадач размера $n/b^i$, каждая стоит $(n/b^i)^d$, вместе — $n^d \cdot \left(\frac{a}{b^d}\right)^i$. Длины полосок образуют геометрическую прогрессию, и всё решает её знаменатель $q = a / b^d$.
Если $T(n) = a\,T(n/b) + n^d$, где $a \ge 1$, $b > 1$, $d \ge 0$, то
- при $a < b^d$ работа убывает вниз по дереву, и $T(n) = \Theta(n^d)$ — основное время уходит на корень;
- при $a = b^d$ все уровни стоят одинаково, и $T(n) = \Theta(n^d \log n)$;
- при $a > b^d$ работа растёт вниз по дереву, и $T(n) = \Theta\!\left(n^{\log_b a}\right)$ — основное время уходит на листья.
Глубина дерева — $\log_b n$, работа уровня $i$ равна $n^d q^i$, где $q = a/b^d$. Всего $T(n) = n^d \sum_{i=0}^{\log_b n} q^i$. Если $q < 1$, сумма бесконечно убывающей прогрессии не больше $\frac{1}{1-q}$ — константа, и $T(n) = \Theta(n^d)$. Если $q = 1$, все $\log_b n + 1$ слагаемых равны единице, и $T(n) = \Theta(n^d \log n)$. Если $q > 1$, сумма определяется последним слагаемым: $\sum_{i=0}^{L} q^i < \frac{q}{q-1} q^{L}$ при $L = \log_b n$. А $n^d q^{\log_b n} = n^d \cdot \frac{a^{\log_b n}}{n^d} = a^{\log_b n} = n^{\log_b a}$ — это число листьев дерева. Значит, $T(n) = \Theta(n^{\log_b a})$.
Теперь видно, почему Карацуба выигрывает. При четырёх умножениях половинок $a = 4 > 2^1$: работа сосредоточена в листьях, их $n^{\log_2 4} = n^2$ — тот же квадрат, что у столбика. При трёх умножениях листьев $n^{\log_2 3} \approx n^{1{,}585}$. Одно сэкономленное умножение на каждом уровне превращается в другой показатель степени.
Алгоритм делит задачу на 8 подзадач вдвое меньшего размера и тратит на склейку порядка $n^2$ действий. Как растёт время его работы?
$a = 8$, $b = 2$, $d = 2$, $b^d = 4 < 8$ — работа растёт к листьям, и время $\Theta(n^{\log_2 8}) = \Theta(n^3)$. Так работает наивное рекурсивное умножение матриц. В 1969 году Фолькер Штрассен проделал с матрицами тот же трюк, что Карацуба с числами: семь умножений блоков вместо восьми, $n^{\log_2 7} \approx n^{2{,}81}$.
Москва, 1959. Стажёр Хоар и словарь на магнитной ленте
Сортировка слиянием режет список механически, пополам, а всю думающую работу делает при склейке. У Хоара наоборот: вся мысль уходит в разрезание, а склеивать ничего не нужно. Выберем любой элемент списка — его называют опорным — и разложим остальные на две кучки: меньшие опорного налево, большие направо. Опорный встанет между ними на своё окончательное место. Теперь отсортируем кучки той же процедурой — и весь список отсортирован, ведь всё левое уже меньше всего правого.
Разложить на кучки — разбиение — можно за один проход: указатели идут с двух концов навстречу друг другу, и когда каждый находит элемент не на своей стороне, они меняют их местами. В Python проще собрать кучки как новые списки — так алгоритм читается почти как определение:
Когда быстрая сортировка медленная
Если опорный элемент каждый раз делит список примерно пополам, дерево рекурсии такое же, как у слияния, и работа — $n \log n$. Но что, если опорный окажется самым маленьким? Тогда одна кучка пустая, а в другой $n - 1$ элементов. Если так случается раз за разом, дерево вытягивается в палку глубины $n$, и сравнений получается $n + (n-1) + \ldots + 1 \approx n^2/2$ — как у пузырька.
Это и случится, если всегда брать в опорные первый элемент, а на вход подать уже отсортированный список. Вторая половина программы кончится ошибкой — так и задумано.
На отсортированном списке рекурсии нужно пять тысяч уровней в глубину, а Python останавливает её примерно на тысяче: у него есть предел глубины вызовов. Даже без этого предела сортировка шла бы квадратичное время. Защититься легко: выбирать опорный элемент случайно, как в первой версии. Тогда никакой вход не будет плохим всегда: плохими бывают только неудачные броски монетки, а они редки. В среднем случайная быстрая сортировка делает около $1{,}39\, n \log_2 n$ сравнений — почему, разберём в главе 26.
Быструю сортировку Хоар опубликовал в 1961 году, и с тех пор она — одна из самых используемых программ в мире: её варианты работают в стандартных библиотеках C++ и Java. Сам Хоар в 1980 году получил премию Тьюринга за вклад в определение и устройство языков программирования; он умер в марте 2026 года в возрасте 92 лет. А в главе 53 мы встретим его ещё раз — с признанием в «ошибке на миллиард долларов».
Что делает сам Python
Сортировка слиянием и метод Карацубы работают у вас на компьютере прямо сейчас. Функция sorted в Python использует Timsort — гибрид сортировки слиянием и вставками, который Тим Петерс написал в 2002 году для самого Python. А умножение целых чисел в CPython, когда числа становятся длинными, переходит на метод Карацубы. Это видно по часам: при удвоении длины чисел время умножения должно расти примерно в $2^{1{,}58} \approx 3$ раза, а не в 4.
Каждое удвоение — примерно втрое дольше. Опровержение гипотезы Колмогорова встроено в CPython, и наш сервер только что им воспользовался.
Задачи
Четыре задачи — от разминки до классики собеседований. Все проверяются на больших входах с ограничением времени, так что квадратичное решение не пройдёт.
Напишите функцию merge_sort(a), которая возвращает новый список с элементами a по возрастанию. Встроенными sorted и .sort() пользоваться нельзя — тесты это проверят. На списке из 200 000 чисел функция должна укладываться в пару секунд.
Начните с функции merge(left, right), которая сливает два отсортированных списка двумя указателями. Не забудьте в конце добавить хвост, который остался в одном из списков.
Рекурсия: merge(merge_sort(a[:mid]), merge_sort(a[mid:])), где mid = len(a) // 2.
Знак <= при сравнении делает сортировку устойчивой: равные элементы сохраняют взаимный порядок. Это нужно, когда записи сортируют по полям поочерёдно, например сначала по имени, потом по городу: внутри каждого города имена останутся по алфавиту.
Напишите функцию kth_smallest(a, k), которая возвращает $k$-й по величине элемент списка (для $k = 1$ — минимум, для $k = $ len(a) — максимум). Сортировать весь список не нужно: подумайте, как помогает разбиение Хоара. На миллионе чисел функция должна работать заметно быстрее сортировки.
Разбейте список относительно случайного опорного на меньшие, равные и большие. Сравните $k$ с размерами кучек: в какой из них лежит ответ?
Рекурсия нужна только в одну кучку, а не в обе. Если опорный каждый раз попадает близко к середине, работа — $n + n/2 + n/4 + \ldots \approx 2n$; со случайным опорным время в среднем тоже линейное.
Этот алгоритм тоже придумал Хоар — он называется quickselect. Так, например, ищут медиану.
Инверсия в списке — это пара позиций $i < j$, где a[i] > a[j]. В отсортированном списке инверсий нет, в развёрнутом их $n(n-1)/2$. Число инверсий показывает, насколько список «перемешан» — так, например, сравнивают два рейтинга одних и тех же фильмов. Напишите count_inversions(a). Перебор всех пар на 100 000 элементах не уложится во время.
Сортируйте слиянием и считайте инверсии по дороге. Инверсии бывают трёх видов: обе позиции в левой половине, обе в правой и «через границу».
Когда при слиянии вы берёте элемент из правой половины, он меньше всех оставшихся элементов левой — и с каждым из них образует инверсию. Сколько их осталось? len(left) - i.
Время — $n \log n$, как у сортировки слиянием: подсчёт добавляет к каждому шагу слияния одно сложение.
Напишите функцию karatsuba(x, y), которая умножает неотрицательные целые числа рекурсивно, по методу Карацубы. Встроенное * разрешено только в базовом случае, когда одно из чисел меньше 10. Это уговор на честность: тесты проверяют только правильность ответа, а смысл задачи в рекурсии.
Разрежьте оба числа по одной и той же позиции $m$ — половине длины более длинного: a, b = divmod(x, 10 ** m).
Решение — в ячейке из начала главы, без подсчёта умножений. В ней B * B и middle * B — умножения на степени десяти, то есть приписывание нулей; в рабочих реализациях вместо них делают сдвиг.
Куда дальше
У «разделяй и властвуй» есть слабое место. Вспомните рекурсивные числа Фибоначчи из главы 9: fib(n) вызывает fib(n-1) и fib(n-2), те — свои, и дерево вызовов разрастается экспоненциально, хотя различных подзадач всего $n + 1$. У сортировки половинки не пересекаются; у Фибоначчи одни и те же подзадачи решаются миллионы раз. Что, если запоминать уже решённые? Тогда экспонента превращается в линию, а на этой мысли стоит целый метод — динамическое программирование. Название ему, по рассказу автора, придумали, чтобы министр обороны не догадался, что это математика.