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

Разделяй и властвуй (divide and conquer) — алгоритмическая парадигма, рекурсивно разбивающая задачу на меньшие подзадачи того же типа, решающая их независимо, и объединяющая результаты.

Зачем нужно

Разделяй и властвуй позволяет снизить сложность алгоритма, разбивая задачу на подзадачи, которые решаются быстрее. Многие фундаментальные алгоритмы — Merge Sort, Quick Sort, бинарный поиск, быстрое умножение чисел (Karatsuba) — основаны на этой парадигме. Ключевое отличие от DP: подзадачи не перекрываются.

Где используется

  • Merge Sort, Quick Sort (эффективная сортировка)
  • Бинарный поиск (поиск за O(log n))
  • Быстрое умножение матриц (алгоритм Штрассена)
  • Нахождение ближайшей пары точек за O(n log n)
  • FFT (быстрое преобразование Фурье): O(n log n)

Основной контент

Три шага

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

Пример 1: Merge Sort

function mergeSort(arr) {
  if (arr.length <= 1) return arr;             // base case

  const mid = arr.length >> 1;
  const left  = mergeSort(arr.slice(0, mid));  // divide + conquer
  const right = mergeSort(arr.slice(mid));     // divide + conquer

  return merge(left, right);                  // combine
}

function merge(left, right) {
  const result = ;
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

Пример 2: Максимум в массиве рекурсивно

function maxRec(arr, lo = 0, hi = arr.length - 1) {
  if (lo === hi) return arr[lo];           // base case
  const mid = (lo + hi) >> 1;
  const leftMax  = maxRec(arr, lo, mid);   // divide + conquer
  const rightMax = maxRec(arr, mid+1, hi); // divide + conquer
  return Math.max(leftMax, rightMax);       // combine
}
// Сложность: T(n) = 2T(n/2) + O(1) → O(n)

Пример 3: Быстрое возведение в степень

// Наивно: O(n) умножений
// D&C: O(log n) умножений — fast exponentiation
function power(base, exp) {
  if (exp === 0) return 1;
  if (exp % 2 === 0) {
    const half = power(base, exp / 2); // решить подзадачу
    return half * half;                 // combine: не два рекурсивных вызова
  }
  return base * power(base, exp - 1);
}
// power(2, 10) = 1024 за 4 рекурсивных вызова вместо 10

Мастер-теорема (Master Theorem)

Для рекуррентности вида T(n) = a·T(n/b) + f(n):

a = число подзадач
b = во сколько раз уменьшается размер
f(n) = стоимость разделения + объединения

Если f(n) = O(n^c), где c = log_b(a):
  → T(n) = O(n^c · log n)

Примеры:
Merge Sort: T(n) = 2T(n/2) + O(n)  → c = log₂(2) = 1 → O(n log n)
Бин. поиск: T(n) = T(n/2) + O(1)   → c = log₂(1) = 0 → O(log n)

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

  • Путать с Динамическое программирование: в D&C подзадачи независимы, в DP — перекрываются.
  • Не определять base case — бесконечная рекурсия.
  • Неэффективное объединение результатов: создание нового массива в merge — O(n) памяти.
  • Применять D&C когда подзадачи перекрываются — мемоизация/DP эффективнее.

Связанные темы

Ресурсы