Паттерн divide and conquer

Divide and conquer — это техника решения задачи через три шага:

1. Divide — разбить задачу на две (или больше) подзадач меньшего размера.
2. Conquer — решить подзадачи (рекурсивно).
3. Combine — объединить решения подзадач в решение исходной.

Большинство классических O(n log n) алгоритмов — это divide and conquer. Они получают эту сложность не случайно, а из структуры паттерна: каждый уровень рекурсии делает O(n) работы (комбинация), уровней log(n) (каждый раз делим пополам).

Merge sort

Канонический пример divide and conquer. Алгоритм:

1. Divide: массив длины n делится на две половины длины n/2.
2. Conquer: каждая половина рекурсивно сортируется.
3. Combine: две отсортированные половины сливаются (merge) в один отсортированный массив.

def merge_sort(xs):
    if len(xs) <= 1:
        return xs                                  # base case

    mid = len(xs) // 2
    left = merge_sort(xs[:mid])                    # divide + conquer
    right = merge_sort(xs[mid:])                   # divide + conquer
    return merge(left, right)                      # combine

def merge(a, b):
    """Слияние двух отсортированных списков."""
    result = []
    i, j = 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

print(merge_sort([5, 2, 8, 1, 9, 3]))   # [1, 2, 3, 5, 8, 9]

Сложность: на каждом уровне рекурсии общая работа O(n) (merge суммарно по всем парам). Уровней log(n). Итого O(n log n).

Память: O(n) на промежуточные массивы. Это не in-place сортировка.

Quicksort

Другой классик. Алгоритм:

1. Divide: выбираем элемент-pivot. Разбиваем массив на три части: меньше pivot, равные, больше pivot.
2. Conquer: рекурсивно сортируем меньшую и большую части.
3. Combine: ничего не делаем — конкатенация уже отсортированных частей даёт результат.

def quicksort(xs):
    if len(xs) <= 1:
        return xs                                  # base case

    pivot = xs[len(xs) // 2]
    less = [x for x in xs if x < pivot]            # divide
    equal = [x for x in xs if x == pivot]
    greater = [x for x in xs if x > pivot]

    return quicksort(less) + equal + quicksort(greater)

Quicksort интересен тем, что divide — нетривиальная работа O(n), а combine — почти бесплатно. Merge sort, наоборот: divide почти бесплатно, combine — O(n).

Средний случай O(n log n). Худший случай O(n²), если pivot постоянно неудачный (например, отсортированный массив с pivot = первый элемент).

Бинарный поиск как divide and conquer

Бинарный поиск тоже подходит под паттерн, но с одним отличием: после разбиения мы решаем только одну подзадачу, а не обе.

1. Divide: разделили на две половины относительно середины.
2. Conquer: решили одну из половин (ту, где может быть target).
3. Combine: ничего не делаем — ответ из одной половины и есть ответ.

def binary_search(xs, target, lo=0, hi=None):
    if hi is None:
        hi = len(xs)
    if lo >= hi:
        return -1                          # base case
    mid = lo + (hi - lo) // 2
    if xs[mid] == target:
        return mid                         # base case
    if xs[mid] < target:
        return binary_search(xs, target, mid + 1, hi)   # одна подзадача
    return binary_search(xs, target, lo, mid)

Поэтому бинарный поиск — O(log n), а не O(n log n). Уровней log(n), но на каждом уровне работа O(1) (одно сравнение), а не O(n).

Master theorem (упрощённо)

Чтобы не выводить сложность вручную каждый раз, существует master theorem. Для рекурсии вида:

T(n) = a * T(n/b) + O(n^c)

где a — число рекурсивных вызовов, b — во сколько раз уменьшается каждая подзадача, c — степень полинома работы на текущем уровне.

Три случая:

1. Если c > log_b(a) -> T(n) = O(n^c). Работа на верхнем уровне доминирует.
2. Если c == log_b(a) -> T(n) = O(n^c log n). Все уровни одинаково затратны.
3. Если c < log_b(a) -> T(n) = O(n^(log_b a)). Работа в листьях рекурсии доминирует.

Применения:

Это упрощённая версия теоремы. Полный текст есть в CLRS — но для практики достаточно знать три случая и применять подстановку.

Fast power

Ещё один пример divide and conquer — быстрое возведение в степень. Наивно a^n это n умножений, O(n). Быстрая версия:

• Если n чётное: a^n = (a^(n/2))^2.
• Если n нечётное: a^n = a * a^(n-1).

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

print(fast_power(2, 100))   # 1267650600228229401496703205376

Сложность O(log n) умножений вместо O(n). На больших степенях разница катастрофическая.

Применения: модулярное возведение в степень (RSA-криптография), вычисление n-го числа Фибоначчи через матричное умножение, fast Fourier transform — везде, где «много шагов одного типа».

Сравнение паттернов

Когда divide and conquer плох

Не каждая задача — divide and conquer. Иногда:

• Перекрытие подзадач. Если подзадачи дублируются (как в наивном Фибоначчи), нужна мемоизация — это dynamic programming, не чистый divide and conquer.
• Невозможно поделить. Если задача не разбивается на меньшие независимые куски — divide and conquer не помогает.
• Combine дорогой. Если merge — O(n²), то O(n²) умножается на log(n) уровней — может оказаться хуже простой линейной итерации.

Главное — проверить инвариант: «решение исходной задачи действительно собирается из решений подзадач, и это собирание дешевле, чем решение исходной целиком».

Попробуй сам

Реализуйте maximum subarray (Kadane’s в divide-conquer форме). Дан массив, найти подотрезок с максимальной суммой.

def max_subarray(xs, lo, hi):
    """Максимальная сумма подотрезка xs[lo:hi]."""
    if hi - lo == 1:
        return xs[lo]                              # base case

    mid = (lo + hi) // 2

    # подсказки:
    # 1. max в левой половине: max_subarray(xs, lo, mid)
    # 2. max в правой половине: max_subarray(xs, mid, hi)
    # 3. max, пересекающий mid: суффикс-сумма слева + префикс-сумма справа
    # 4. ответ = max из трёх

    left_max = max_subarray(xs, lo, mid)
    right_max = max_subarray(xs, mid, hi)

    # max suffix sum left of mid
    cross_left = float('-inf')
    s = 0
    for i in range(mid - 1, lo - 1, -1):
        s += xs[i]
        if s > cross_left:
            cross_left = s

    # max prefix sum right of mid
    cross_right = float('-inf')
    s = 0
    for i in range(mid, hi):
        s += xs[i]
        if s > cross_right:
            cross_right = s

    return max(left_max, right_max, cross_left + cross_right)

xs = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(xs, 0, len(xs)))   # 6 (подотрезок [4, -1, 2, 1])

Это O(n log n). Kadane’s algorithm делает то же за O(n), но через dynamic programming, а не divide and conquer.