Divide & Conquer

Divide and Conquer — это не просто «разбей задачу пополам». Это фундаментальный паттерн проектирования алгоритмов, основанный на трёх этапах: разделение исходной задачи на несколько независимых подзадач того же типа, рекурсивное решение каждой подзадачи, и объединение их результатов в итоговый ответ. Ключевое слово здесь — «независимых». Если подзадачи пересекаются и повторно вычисляются, вам нужна не D&C, а динамическое программирование с мемоизацией.

Представьте, что вам нужно отсортировать миллион записей. Можно сделать это наивно за O(n²), но есть способ лучше: разделите массив пополам, рекурсивно отсортируйте каждую половину, затем слейте два отсортированных массива за линейное время. Это и есть Merge Sort — идеальный пример D&C с гарантированной сложностью O(n log n). Сравните с QuickSort: тоже D&C, но разделение происходит вокруг pivot-элемента, и в худшем случае можно получить O(n²), если постоянно выбирать плохой pivot.

Когда применять / Мотивация

Идея / Как работает

Почему D&C эффективен? Потому что рекурсия создаёт дерево вызовов высотой log n (при делении пополам), а на каждом уровне мы делаем O(n) работы суммарно. Это интуиция Master Theorem: T(n) = a·T(n/b) + f(n), где a — количество подзадач, n/b — размер каждой, f(n) — стоимость разделения и объединения. Для Merge Sort: a=2, b=2, d=1 (где f(n)=O(n^d)), получаем случай d = log_b(a) → O(n log n). Для Binary Search: a=1, b=2, d=0 → O(log n). Для Karatsuba умножение: a=3, b=2, d=1 → d < log₂(3) ≈ 1.585 → O(n^1.585).

Типичные ошибки: забыть базовый случай (бесконечная рекурсия), неправильно определить границы при делении (особенно в целочисленной арифметике: используйте mid = left + (right - left) / 2 вместо (left + right) / 2 для избежания переполнения), и самое главное — не учесть, что подзадачи должны быть строго меньше исходной. Если после разделения у вас остаётся подзадача того же размера, вы получите бесконечную рекурсию.

Edge cases: единичные элементы (базовый случай), чётные vs нечётные размеры (всегда проверяйте деление посередине), дублирующиеся элементы (важно для stable sort — Merge Sort стабилен, QuickSort обычно нет), пустые массивы. В многопоточных системах D&C идеально для параллелизма, так как подзадачи независимы — можно раскидать по разным ядрам. Но будьте осторожны с памятью: рекурсивный стек съедает O(log n) пространства, а Merge Sort требует O(n) дополнительной памяти для буфера слияния.

Реализация

Задача: Maximum Subarray через D&C

Дан массив целых чисел (могут быть отрицательные). Найти подмассив с максимальной суммой. Пример: [-2,1,-3,4,-1,2,1,-5,4] → ответ 6 (подмассив [4,-1,2,1]).

Подход D&C: Разделим массив пополам в точке mid. Максимальный подмассив может быть в трёх местах: (1) полностью в левой половине, (2) полностью в правой половине, (3) пересекает середину. Первые два случая решаем рекурсивно. Для третьего — найдём максимальную сумму справа от mid и слева от mid, идя к границам. Это O(n) работы на уровне, умножаем на высоту дерева log n → O(n log n). Интересно, что классический алгоритм Кадане решает это за O(n) одним проходом, но D&C демонстрирует универсальную технику.

function maxSubarrayDC(nums) {
    function helper(left, right) {
      if (left === right) return nums[left]; // базовый случай

      const mid = left + ((right - left) >> 1);
      const leftMax = helper(left, mid);
      const rightMax = helper(mid + 1, right);

      // Сумма через середину: максимум слева от mid и справа
      let leftSum = -Infinity, sum = 0;
      for (let i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
      }

      let rightSum = -Infinity;
      sum = 0;
      for (let i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
      }

      const crossMax = leftSum + rightSum;
      return Math.max(leftMax, rightMax, crossMax);
    }

    return helper(0, nums.length - 1);
  }

  // Для сравнения: Kadane O(n)
  function maxSubarrayKadane(nums) {
    let maxSoFar = nums[0], maxEndingHere = nums[0];
    for (let i = 1; i < nums.length; i++) {
      maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
      maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
  }

Трассировка

Трассировка для [-2,1,-3,4,-1,2,1,-5,4]:

Разделяем [0..8] → mid=4, левая часть [-2,1,-3,4,-1], правая [-1,2,1,-5,4]
Левая часть → mid=2, рекурсивно: левее [-2,1,-3] даёт 1, правее [4,-1] даёт 4
Для левой части через середину: слева от mid=2 максимум -2, справа 4-1=3, crossMax=-2+3=1
Максимум левой части: max(1, 4, 1) = 4
Правая часть [mid+1..8] аналогично → 6 (подмассив [2,1,-5,4] даёт 2, но [2,1]=3 лучше внутри)
Через главную середину: слева от mid=4 максимум 4, справа 2+1=3, crossMax=7? Нет, нужно идти от mid=4 влево: [-1]+4=3…

(детальный trace громоздкий, но идея: на каждом уровне O(n) слияние)

Итог: max(4, rightMax, crossMax) → 6 из правой части или через cross.

Сложность

Анализ сложности: Время O(n log n) — на каждом из log n уровней рекурсии делаем O(n) работы (проходы для crossMax). Память O(log n) на стек вызовов. Kadane быстрее O(n), но D&C показывает универсальный паттерн, который обобщается на 2D случаи (max rectangle in matrix).

Когда применять: сортировка (Merge Sort, QuickSort), поиск k-го элемента (QuickSelect за O(n) в среднем), задачи на двумерных структурах (ближайшая пара точек за O(n log n)), умножение больших чисел и матриц (Karatsuba, Strassen), FFT для умножения многочленов. Красный флаг: если вы заметили, что одна и та же подзадача вычисляется многократно — это сигнал для DP, а не D&C. Например, вычисление чисел Фибоначчи через простую рекурсию — это катастрофа O(2^n), хотя формально подходит под D&C паттерн.

Типичные ошибки и подводные камни

Overflow при (left+right)/2 для больших left/right — используйте left + ((right-left)>>1). Забытый базовый случай if (left === right) приведёт к infinite recursion. При делении чётного массива на две части помните: [left, mid] и [mid+1, right], не [left, mid-1]. Для стабильности сортировки в Merge важно брать элемент из левого массива при равенстве: if (a[i] <= a[j]), не <. Отрицательные числа в Maximum Subarray требуют правильной инициализации: используйте -Infinity, а не 0, иначе для массива из одних отрицательных получите неправильный 0.

Follow-up вопросы интервьюера

Как Master Theorem применяется к Binary Search?
T(n) = T(n/2) + O(1) → a=1, b=2, d=0. log₂(1)=0, d=0 → случай 2 Master Theorem → O(n⁰ log n) = O(log n).
Почему QuickSort в худшем случае O(n²), а Merge Sort всегда O(n log n)?
QuickSort выбирает pivot и делит на две части. Если pivot всегда минимальный/максимальный (например, отсортированный массив с плохим выбором), одна часть остаётся n-1, дерево рекурсии становится высотой n → O(n²). Merge Sort гарантированно делит пополам, высота всегда log n.
Можно ли Merge Sort сделать in-place без O(n) памяти?
Теоретически да (in-place merge algorithms существуют, например, block merge), но они сложны и на практике теряют стабильность. Классический Merge Sort требует O(n) буфер для слияния. QuickSort проще сделать in-place (O(log n) только стек).
Как использовать D&C для подсчёта инверсий в массиве?
Инверсия — пара (i, j) где i<j, но a[i]>a[j]. Модифицируйте Merge Sort: при слиянии, когда берёте элемент из правого массива, все оставшиеся в левом образуют инверсии с ним (так как левый отсортирован и все больше). Подсчитайте их. O(n log n).
Почему Karatsuba умножение быстрее наивного?
Наивное умножение двух n-битных чисел: O(n²). Karatsuba разбивает на 4 подзадачи размера n/2, но через хитрость (3 умножения вместо 4): T(n)=3T(n/2)+O(n). Master Theorem: log₂(3)≈1.585 > 1 → O(n^1.585). Экономия на больших числах значительна.
Когда НЕ стоит использовать D&C?
Когда подзадачи пересекаются и повторно вычисляются — переходите к DP с мемоизацией. Когда базовый случай дорогой или разделение не уменьшает задачу. Когда память ограничена и рекурсия глубокая (стек переполнится) — рассмотрите итеративные подходы.

Чеклист на собес

Знаю три шага: divide (разбить), conquer (рекурсивно решить), combine (объединить).
Применяю Master Theorem для анализа: T(n) = aT(n/b) + f(n) — выбираю случай по соотношению f(n) и n^log_b(a).
Узнаю D&C по сигналам: «разбить на половины», «независимые подзадачи», «merge результатов».
Классические примеры: merge sort O(n log n), quicksort, binary search, closest pair, Karatsuba.
D&C — частый источник для распараллеливания: подзадачи независимы и могут считаться параллельно.
Отличаю от DP: в D&C подзадачи не пересекаются, в DP — пересекаются и кешируются.
Не забываю про базовый случай и про корректность combine-шага — самые частые ошибки.