Где выигрыш исчезает: три режима одной формулы

Если ты по виду рекуррентности определяешь режим, знаешь, зачем в реальном коде нужен порог перехода на простой алгоритм, и помнишь про цену рекурсии, листай до «Теперь сам».

Как думаешь, что дороже

Две функции сортируют миллион чисел. Первая - сортировка слиянием до самого дна, то есть до кусков по одному элементу. Вторая - та же сортировка, но на кусках короче 32 элементов она переключается на сортировку вставками, у которой честный квадрат.

Квадрат против n·log n - казалось бы, вопрос закрыт. Но в реальных библиотеках стоит именно вторая, и она быстрее первой примерно в полтора раза. Как квадратичный алгоритм может ускорять n·log n?

На что это похоже

Доставка посылок. Разделить город на районы и развезти по районам - выигрыш. Разделить район на дома и посылать отдельную машину к каждому дому - проигрыш: время уходит не на дорогу, а на подачу машины. Где-то посередине лежит размер куска, ниже которого дробить уже невыгодно, - и этот размер не вычисляется из асимптотики, он измеряется.

Механизм: три режима и три способа всё испортить

n^(log_b a)  - сколько работы В ЛИСТЬЯХ (число листьев дерева рекурсии)
f(n)         - сколько работы НА ВЕРХНЕМ уровне

листья тяжелее      f(n) = O(n^(log_b a − ε))     T(n) = Θ(n^(log_b a))
поровну             f(n) = Θ(n^(log_b a))         T(n) = Θ(n^(log_b a)·log n)
корень тяжелее      f(n) = Ω(n^(log_b a + ε))     T(n) = Θ(f(n))

ЧТО УБИВАЕТ ВЫИГРЫШ

дорогое объединение     2·T(n/2) + n²   → Θ(n²),  как у перебора
много подзадач          4·T(n/2) + n    → Θ(n²),  деление не спасает
мелкое дробление        рекурсия на кусках из 2-3 элементов:
                        вызов функции стоит дороже, чем сама работа

Третий пункт в асимптотике не виден вовсе: Θ(n·log n) останется Θ(n·log n), что бы ты ни делал на дне. Он виден только в замере - и лечится порогом: ниже него берётся простой алгоритм без рекурсии.

def sort(a, lo, hi):
    if hi - lo <= 32:            # порог: дальше дробить невыгодно
        insertion_sort(a, lo, hi)
        return
    mid = lo + (hi - lo) // 2    # не (lo + hi) // 2 - переполнение в C и Java
    sort(a, lo, mid)
    sort(a, mid, hi)
    merge(a, lo, mid, hi)

Правило

Три режима формулы: листья тяжелее (T = Θ(n^(log_b a))), поровну (множитель log n), корень тяжелее (T = Θ(f(n))). Выигрыш деления убивают дорогое объединение, слишком большое число подзадач и слишком мелкое дробление. Первые два видны в асимптотике, третий - только в замере, и лечится порогом перехода на простой алгоритм (в библиотеках это 16-64 элемента). Глубина рекурсии - log_b n кадров на стеке, и это отдельный ресурс: на миллионе элементов деление пополам даёт два десятка кадров, а деление на «один и остальные» - миллион и переполнение стека.

Разбор: почему вставки ускоряют слияние

Посчитаем честно. Пусть порог k = 32, всего n = 10⁶ элементов.

без порога:  дерево до листьев по 1 элементу, уровней log₂ 10⁶ ≈ 20
             вызовов функции ≈ 2·10⁶, и на дне каждый вызов делает почти ничего

с порогом:   дерево останавливается на кусках по 32, уровней log₂(10⁶/32) = 15
             вызовов ≈ 2·(10⁶/32) ≈ 62 500 - в тридцать раз меньше
             плюс 31 250 сортировок вставками по 32 элемента:
             32²/4 ≈ 256 операций каждая, итого ≈ 8·10⁶ операций

Восемь миллионов операций вставками против экономии почти двух миллионов вызовов функции (2·10⁶ − 62 500 ≈ 1.94·10⁶) и пяти уровней слияния (каждый уровень - это 10⁶ перемещений). Считаем уровни: 20 − 15 = 5 уровней по 10⁶ = 5·10⁶ перемещений сэкономлено. Плюс вызовы. Против 8·10⁶ дешёвых операций вставками на почти отсортированных коротких кусках, где вставки работают быстрее своего худшего случая.

Итог примерно в ноль по числу операций - а выигрыш в полтора раза берётся из того, чего в подсчёте операций нет вовсе: короткий кусок целиком помещается в кеш процессора, у вставок нет вызовов функций, и у них последовательный доступ к памяти. Именно поэтому порог ПОДБИРАЮТ замером под конкретную машину, а не выводят из формулы.

Разбор: одно и то же дерево, три разных ответа

Возьмём три рекуррентности с одинаковым делением пополам и посмотрим, как перетекает работа по уровням. Пусть n = 8.

T(n) = 2·T(n/2) + n            T(n) = 2·T(n/2) + n²        T(n) = 2·T(n/2) + 1
уровень 0:  8                  уровень 0:  64              уровень 0:  1
уровень 1:  4 + 4 = 8          уровень 1:  16 + 16 = 32    уровень 1:  1 + 1 = 2
уровень 2:  2·4 = 8            уровень 2:  4·4 = 16        уровень 2:  4
уровень 3:  1·8 = 8            уровень 3:  1·8 = 8         уровень 3:  8
сумма: 4 уровня по 8 = 32      сумма: 64+32+16+8 = 120     сумма: 1+2+4+8 = 15
режим: поровну                 режим: корень тяжелее       режим: листья тяжелее
Θ(n·log n)                     Θ(n²)                       Θ(n)

Смотри, куда смещается масса. В первом столбце она размазана ровно - отсюда log n множителем. Во втором больше половины стоит на верхнем уровне, и сумма всего лишь вдвое больше верхнего: 120 < 2 · 64. В третьем наоборот: половина всей работы - в листьях, и сумма меньше удвоенного нижнего уровня.

Это и есть способ понять ответ без теоремы: посчитай верхний уровень, посчитай нижний и посмотри, какой из них растёт быстрее по мере спуска. Теорема лишь формализует этот взгляд.

Что ломается без этого

Первое: гнать рекурсию до одного элемента и удивляться, что «теоретически быстрый» код медленнее библиотечного. Второе: ставить порог наугад и не мерить: оптимальное значение зависит от размера кеша и стоимости вызова, а на разных машинах оно разное. Третье: забывать про стек: log n кадров при делении пополам это мелочь, но при делении «один элемент и остальные» (худший случай быстрой сортировки) их будет n, и программа упадёт до того, как станет медленной. Четвёртое: считать, что f(n) - это только объединение: деление тоже стоит времени, и если оно требует сортировки, то f(n) = n·log n, а не n. Пятое: применять главную теорему к рекуррентности, которая под неё не подходит (подзадачи РАЗНОГО размера, как T(n) = T(n/3) + T(2n/3) + n) - там нужен разбор деревом.

Зачем это в работе

Три режима - это готовый ответ на вопрос «стоит ли переписывать». Если твой алгоритм в режиме «корень тяжелее», ускорять рекурсию бессмысленно: время уходит на верхний уровень, и оптимизировать надо именно его. Если «листья тяжелее» - наоборот, смотри на базовый случай и на число подзадач. Порог перехода на простой алгоритм стоит в любой серьёзной реализации сортировки (в CPython это Timsort с minrunРазбирается в разделе 25, глава «Timsort, introsort и почему в библиотеке гибрид»: Timsort изнутри: серии, minrun и вставки двоичным поиском, в C++ - introsort с переходом на вставки), и знание, зачем он там, - это разница между «скопировал библиотечный код» и «понимаю, что будет, если убрать эту строчку». А глубина рекурсии - обычная причина падений на проде: обработка дерева каталогов или JSON рекурсией без ограничения глубины ломается ровно там, где данные оказались глубже, чем думал автор.

Теперь сам

Алгоритм делит массив на три части по n/3, решает каждую рекурсивно и объединяет за n. Назови режим и ответ. Что изменится, если объединение станет стоить n²?