0Pricing
Coding Interview Prep · Урок

Шаблон «Разделяй и властвуй»

Выделите в сортировке слиянием трёхшаговый шаблон — разделение, решение и объединение — и систематически применяйте его к новым типам задач

«Шаблон «Разделяй и властвуй»» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Что такое метод «разделяй и властвуй»?

Метод «разделяй и властвуй» (РиВ) решает задачу, разбивая её на независимые подзадачи того же типа, рекурсивно решая каждую из них и объединяя полученные решения. Ключевое слово здесь — независимые: подзадачи не используют общее состояние, в отличие от DP, где они пересекаются. Классические примеры: сортировка слиянием, двоичный поиск, быстрая сортировка, поиск ближайшей пары точек и быстрое умножение матриц. Благодаря этому трёхэтапному шаблону метод «разделяй и властвуй» обычно обеспечивает время O(n log n).

# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP:  sub-problems OVERLAP (same sub-problem solved multiple times)

# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing

# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n)  [merge sort]
# T(n) = T(n/2) + O(1) → O(log n)     [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]

Шаблон из трёх шагов

Каждый алгоритм РиВ выполняет три шага: (1) разделение — разбить задачу на две или более небольших подзадач, обычно в середине; (2) решение — рекурсивно решить каждую подзадачу. Определить базовый случай, который остановит рекурсию (обычно n ≤ 1); (3) объединение — слить или объединить решения подзадач в общее решение. Вся творческая часть находится именно на шаге объединения: разделение обычно сводится к разбиению в середине.

def divide_and_conquer(arr, lo, hi):
    # BASE CASE: trivial sub-problem
    if lo >= hi:
        return base_case_result(arr, lo, hi)
    
    # DIVIDE: split at midpoint
    mid = (lo + hi) // 2
    
    # CONQUER: solve sub-problems recursively
    left_result  = divide_and_conquer(arr, lo, mid)
    right_result = divide_and_conquer(arr, mid + 1, hi)
    
    # COMBINE: merge results
    return combine(left_result, right_result, arr, lo, mid, hi)

def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)

Сортировка слиянием как классический пример

Сортировка слиянием идеально иллюстрирует метод РиВ: разделить массив в середине; решить задачу, рекурсивно отсортировав каждую половину; объединить результаты, слив две отсортированные половины за O(n). Вся основная работа выполняется на шаге слияния. Рекуррентное соотношение: T(n) = 2T(n/2) + O(n). По второму случаю мастер-теоремы: T(n) = O(n log n). Это самое важное рекуррентное соотношение метода РиВ, которое необходимо запомнить.

def merge_sort(arr):
    # BASE CASE
    if len(arr) <= 1:
        return arr
    # DIVIDE
    mid = len(arr) // 2
    # CONQUER
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # COMBINE
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

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

Краткая памятка по мастер-теореме

Мастер-теорема решает рекуррентные соотношения вида T(n) = aT(n/b) + f(n): случай 1: f(n) = O(n^(log_b(a) - ε)) → T(n) = O(n^log_b(a)). Случай 2: f(n) = O(n^log_b(a)) → T(n) = O(n^log_b(a) × log n). Случай 3: f(n) = Ω(n^(log_b(a) + ε)) → T(n) = O(f(n)). Для сортировки слиянием: a=2, b=2, f(n)=O(n), n^log_2(2)=n → случай 2 → O(n log n).

# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n)    → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1)    → a=2,b=2,f=1,n^1=n >> 1  → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2)  → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1)     → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree

recurrences = [
    ('Merge sort: 2T(n/2)+n', 'O(n log n)'),
    ('Binary search: T(n/2)+1', 'O(log n)'),
    ('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
    ('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)

Максимальный подмассив: подход «разделяй и властвуй»

При подходе РиВ к поиску максимального подмассива ответ находится либо полностью в левой половине, либо полностью в правой, либо пересекает середину. В последнем случае нужно расширяться влево от mid и вправо от mid+1, находя максимальную сумму в каждом направлении, а затем объединить результаты. Этот подход РиВ со временем O(n log n) медленнее алгоритма Кадане со временем O(n), но прекрасно демонстрирует шаблон и часто встречается на собеседованиях по теме РиВ.

def max_subarray_dc(nums, lo=None, hi=None):
    if lo is None: lo, hi = 0, len(nums) - 1
    if lo == hi: return nums[lo]
    mid = (lo + hi) // 2
    # Conquer
    left_max  = max_subarray_dc(nums, lo, mid)
    right_max = max_subarray_dc(nums, mid + 1, hi)
    # Cross-midpoint sum
    left_sum = curr = 0
    for i in range(mid, lo - 1, -1):
        curr += nums[i]
        left_sum = max(left_sum, curr)
    right_sum = curr = 0
    for i in range(mid + 1, hi + 1):
        curr += nums[i]
        right_sum = max(right_sum, curr)
    cross_max = left_sum + right_sum
    return max(left_max, right_max, cross_max)

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums))  # 6

Возведение в степень: быстрое вычисление

Быстрое возведение в степень (LeetCode 50): вычисление x^n за O(log n) с помощью РиВ. Если n чётное: x^n = (x^(n/2))^2. Если n нечётное: x^n = x × x^(n-1). Отрицательное n обрабатывается с помощью x^(-n) = 1/x^n. Каждый рекурсивный вызов уменьшает n вдвое, поэтому глубина рекурсии равна O(log n). Это наглядный пример, в котором шаг объединения представляет собой простое умножение — тривиальное, но эффективное.

def my_pow(x, n):
    if n < 0:
        return 1 / my_pow(x, -n)
    # BASE CASE
    if n == 0: return 1
    # DIVIDE and CONQUER
    half = my_pow(x, n // 2)
    if n % 2 == 0:
        return half * half          # even: x^n = (x^(n/2))^2
    else:
        return x * half * half      # odd: x^n = x * (x^(n/2))^2

print(my_pow(2, 10))   # 1024
print(my_pow(2, -2))   # 0.25
print(my_pow(3, 5))    # 243
print(my_pow(0, 0))    # 1

Преобразование отсортированного массива в BST

Преобразование отсортированного массива в BST (LeetCode 108) использует метод РиВ: середина выбирается в качестве корня, что обеспечивает баланс высоты; затем левое поддерево рекурсивно строится из левой половины, а правое — из правой. В результате получается сбалансированное по высоте BST с минимальной высотой O(log n). Структура РиВ напоминает двоичный поиск: на каждом уровне рекурсии середина становится корнем текущего диапазона.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sorted_array_to_bst(nums):
    def helper(lo, hi):
        if lo > hi: return None
        mid = (lo + hi) // 2
        node = TreeNode(nums[mid])    # DIVIDE at midpoint
        node.left  = helper(lo, mid - 1)  # CONQUER left
        node.right = helper(mid + 1, hi)  # CONQUER right
        # COMBINE: already done by assignment
        return node
    return helper(0, len(nums) - 1)

def inorder(node):
    if not node: return []
    return inorder(node.left) + [node.val] + inorder(node.right)

root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root))  # [-10,-3,0,5,9] (sorted, proving BST property)

Когда метод «разделяй и властвуй» — не лучший выбор

Метод РиВ имеет дополнительные затраты: глубину стека вызовов функций, создание срезов массива (если не использовать индексы) и шаг объединения. Он оптимален, когда шаг объединения занимает O(n) или меньше. Если подзадачи пересекаются, метод РиВ заново вычисляет решения и работает неэффективно — требуется DP. Если шаг объединения доминирует по сложности (например, занимает O(n²)), метод РиВ не даёт преимуществ по сравнению с наивными подходами. Важно понимать, что выбрать: РиВ — для независимых подзадач, DP — для пересекающихся.

# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead

def fib_dc(n):
    if n <= 1: return n
    return fib_dc(n-1) + fib_dc(n-2)  # O(2^n)!

def fib_dp(n):
    a, b = 0, 1
    for _ in range(n): a, b = b, a+b
    return a  # O(n)

print(fib_dp(30))  # fast
# fib_dc(40) would take seconds — do not run large values!

РиВ для двоичного поиска в отсортированной матрице

Поиск в двумерной матрице (LeetCode 240), в которой каждая строка и каждый столбец отсортированы, можно выполнить с помощью РиВ: начать с правого верхнего угла. Если текущее значение > target, перейти влево и исключить столбец. Если текущее значение < target, перейти вниз и исключить строку. Если значения равны, элемент найден. Этот алгоритм со временем O(m+n) технически не является рекурсивным РиВ, но использует ту же ключевую идею: на каждом шаге исключать половину пространства поиска.

def search_matrix(matrix, target):
    if not matrix: return False
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1  # start top-right
    while row < m and col >= 0:
        val = matrix[row][col]
        if val == target:
            return True
        elif val > target:
            col -= 1  # eliminate this column
        else:
            row += 1  # eliminate this row
    return False

matrix = [
    [1,   4,  7, 11, 15],
    [2,   5,  8, 12, 19],
    [3,   6,  9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5))   # True
print(search_matrix(matrix, 20))  # False

Анализ дерева рекурсии

Для рекуррентных соотношений РиВ, которые не подходят под мастер-теорему, используйте метод дерева рекурсии. Изобразите каждый уровень рекурсивных вызовов и просуммируйте работу на каждом уровне. Для сортировки слиянием на уровне k имеется 2^k подзадач размера n/2^k. Работа на одном уровне = 2^k × O(n/2^k) = O(n). Всего уровней = log n. Общий объём работы = O(n log n). Этот наглядный метод работает для любого рекуррентного соотношения и помогает понять, почему метод РиВ обычно достигает O(n log n).

# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)

import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')

Как рассказывать о методе «разделяй и властвуй» на собеседовании

Представляя решение с помощью РиВ на собеседовании: (1) явно назовите три шага: «Я разделю задачу в середине, рекурсивно решу каждую половину, а затем объединю результаты слиянием». (2) Чётко обозначьте базовый случай. (3) Выведите рекуррентное соотношение: T(n) = 2T(n/2) + O(n). (4) Примените мастер-теорему или дерево рекурсии, чтобы получить O(n log n). (5) Укажите, когда РиВ лучше или хуже альтернативных подходов: DP — для пересекающихся подзадач, алгоритм Кадане — для максимального подмассива.

# D&C interview template to memorize:
def dc_template(problem, lo, hi):
    # 1. BASE CASE (state it first)
    if lo == hi: return solve_base(problem, lo)
    # 2. DIVIDE
    mid = (lo + hi) // 2
    # 3. CONQUER
    left  = dc_template(problem, lo, mid)
    right = dc_template(problem, mid + 1, hi)
    # 4. COMBINE (this is where the algorithm-specific logic goes)
    return combine_results(left, right, problem, lo, mid, hi)

def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)

print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')

Быстрая проверка

Проверьте своё понимание концепций «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.

Итоги урока

В этом уроке Вы узнали: метод «разделяй и властвуй» следует шаблону: базовый случай → разделение в середине → рекурсивное решение → объединение, соотношение T(n) = 2T(n/2) + O(n) даёт O(n log n) по второму случаю мастер-теоремы, а также РиВ оптимален для независимых подзадач, тогда как при пересечении подзадач требуется DP. Далее мы применим РиВ для подсчёта инверсий в массиве с помощью модифицированной сортировки слиянием.

Часто задаваемые вопросы

Урок «Шаблон «Разделяй и властвуй»» бесплатный?

Да — полный текст урока «Шаблон «Разделяй и властвуй»» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Шаблон «Разделяй и властвуй»»?

Выделите в сортировке слиянием трёхшаговый шаблон — разделение, решение и объединение — и систематически применяйте его к новым типам задач Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Шаблон «Разделяй и властвуй»»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Шаблон «Разделяй и властвуй»
  2. Подсчёт инверсий с помощью изменённой сортировки слиянием
  3. Элемент большинства: голосование Бойера—Мура
  4. Медиана двух отсортированных массивов
← Назад к Coding Interview Prep