Алгоритм «разделяй и властвуй»

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

Проще говоря, разделяй и властвуй состоит из трёх шагов:Разделяй -> Властвуй -> Объединяй。

Представьте, что перед вами большая куча строительных кубиков, которые нужно отсортировать по цвету. Если взяться за это напрямую, можно растеряться. Более разумный подход таков: сначала разделите кучу на две меньшие кучи, затем отсортируйте каждую меньшую кучу отдельно и, наконец, объедините две отсортированные меньшие кучи вместе. ЭтоРазделяй и властвуйпроцесс — это основная идея алгоритма «разделяй и властвуй».

Алгоритм «разделяй и властвуй»Это похоже на то, как умный руководитель команды решает большую задачу:

  1. Разделяй: Разбейте большую задачу на несколько маленьких задач того же типа.
  2. Покорение: рекурсивно решить эти подзадачи
  3. Объединение (Combine): Объедините решения подзадач в решение исходной задачи.

Примеры из реальной жизни:

  • Управление компанией: Генеральный директор → Руководитель отдела → Руководитель команды → Рядовой сотрудник
  • Военное командование: Командир → Командующий армией → Командир дивизии → Командир полка → Командир роты
  • Организация книг: Сначала классифицируйте по широкой категории, затем по подкатегории и, наконец, отсортируйте по алфавиту.
  • Игра в поиск сокровищ: Разделите большую карту на маленькие блоки и ищите в каждом блоке
Характеристики задачи Другие методы Подход «разделяй и властвуй»
Крупномасштабные данные Может быть неэффективным Декомпозировать и обрабатывать параллельно
Сложные структуры Трудно решить напрямую Упрощать подзадачи
Можно определить рекурсивно Требует сложной логики Естественно подходит для рекурсии
Независимые подзадачи Трудно распараллелить Идеально поддерживает параллелизм

Основные идеи и шаги

Алгоритмы «разделяй и властвуй» обычно следуют чёткой трёхшаговой схеме. Её можно интуитивно понять с помощью следующей блок-схемы:

На рисунке выше показано: сначала алгоритм определяет, достаточно ли текущая задача проста для прямого решения. Если да, он решает её напрямую и возвращает результат; если нет, он разбивает задачу на несколько подзадач, рекурсивно решает каждую подзадачу и в конце объединяет результаты подзадач, чтобы получить окончательный ответ.

Точнее, эти три шага таковы:

  1. Разделение: разбейте исходную задачу на несколько меньших, взаимно независимых подзадач, имеющих ту же форму, что и исходная задача.
  2. Покорение: рекурсивно решите каждую подзадачу. Если подзадача достаточно мала по масштабу, решите её напрямую.
  3. Объединение: объедините решения подзадач, чтобы сформировать решение исходной задачи.

Классические применения алгоритмов «разделяй и властвуй»

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

Применение 1: Сортировка слиянием

Сортировка слиянием — идеальное воплощение идеи разделяй и властвуй. Её цель —отсортировать неупорядоченный массив в упорядоченный массив.。

Шаги алгоритма:

  1. Разделение: разделите текущий массив по средней позиции на левый и правый подмассивы.
  2. Покорение: рекурсивно выполните сортировку слиянием для левого подмассива и правого подмассива.
  3. Merge: Объедините два уже отсортированных упорядоченных подмассива в новый упорядоченный массив.

Пример кода:

Пример

def merge_sort(arr):
    """
Главная функция сортировки слиянием
:param arr: список для сортировки
:return: новый отсортированный список
    """
    # 1. Властвуй: Если длина массива равна 0 или 1, сразу вернуть (базовый случай)
    if len(arr) <= 1:
        return arr
   
    # 2. Разделяй: Найдите середину и разделите массив
    mid = len(arr) // 2
    left_half = arr[:mid]   # Левый подмассив
    right_half = arr[mid:]  # Правый подмассив
   
    # 3. Властвуй: Рекурсивно отсортируйте левый и правый подмассивы
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)
   
    # 4. Слияние: объединить два отсортированных массива
    return merge(left_sorted, right_sorted)

def merge(left, right):
    """
Объединить два отсортированных списка
:param left: Отсортированный список A
:param right: Отсортированный список B
:return: Объединённый отсортированный список
    """
    merged = []  # Список для хранения результата слияния
    i = j = 0    # i и j — указатели на left и right соответственно
   
    # Сравнить первые элементы двух списков и поместить меньший элемент в merged
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
   
    # Добавить все оставшиеся элементы (если таковые имеются) непосредственно в конец merged
    # Поскольку left и right уже отсортированы, оставшаяся часть также отсортирована
    merged.extend(left[i:])
    merged.extend(right[j:])
   
    return merged

# Тестовые данные
test_array = [38, 27, 43, 3, 9, 82, 10]
print("Исходный массив:", test_array)
sorted_array = merge_sort(test_array)
print("Отсортированный массив:", sorted_array)
# Вывод: Исходный массив: [38, 27, 43, 3, 9, 82, 10]
# Вывод: Отсортированный массив: [3, 9, 10, 27, 38, 43, 82]

Применение 2: Бинарный поиск

Бинарный поиск используется вотсортированном массиведля быстрого поиска целевого значения в нём. Он постоянно делит область поиска пополам, что делает его упрощённой версией стратегии «разделяй и властвуй» (обычно обрабатывается только одна подзадача, и нет необходимости выполнять слияние).

Шаги алгоритма:

  1. Разделяй: Найдите средний элемент массива.
  2. Властвуй：
    • Если средний элемент равен целевому значению, поиск завершается успешно.
    • Если целевое значение меньше среднего элемента, выполните рекурсивный поиск в левой половине.
    • Если целевое значение больше среднего элемента, выполните рекурсивный поиск в правой половине.
  3. Слияние: Бинарному поиску обычно не нужен этап слияния, потому что как только целевое значение найдено, его позицию можно вернуть напрямую.

Пример кода:

Пример

def binary_search(arr, target, low, high):
    """
Бинарный поиск (рекурсивная версия)
:param arr: Отсортированный список
:param target: Искомое значение для поиска
:param low: Начальный индекс текущего диапазона поиска
:param high: Конечный индекс текущего диапазона поиска
:return: Индекс искомого значения или -1, если не найдено
    """
    # Базовый случай: диапазон поиска недействителен, значит искомое значение не найдено
    if low > high:
        return -1
   
    # Разделяй: вычислить средний индекс
    mid = (low + high) // 2
   
    # Властвуй: принять решение и выполнить рекурсию
    if arr[mid] == target:
        return mid  # Искомое значение найдено, вернуть индекс
    elif target < arr[mid]:
        # Целевое значение находится в левой половине, рекурсивно искать левую половину
        return binary_search(arr, target, low, mid - 1)
    else:
        # Целевое значение находится в правой половине, рекурсивно искать правую половину
        return binary_search(arr, target, mid + 1, high)

# Тестовые данные (должны быть отсортированы!)
sorted_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_value = 23

result = binary_search(sorted_list, target_value, 0, len(sorted_list) - 1)

if result != -1:
    print(f"Индекс целевого значения {target_value} в массиве: {result}")
else:
    print(f"Целевое значение {target_value} отсутствует в массиве.")
# Вывод: индекс целевого значения 23 в массиве: 5

Характеристики и анализ сложности алгоритмов «разделяй и властвуй»

Характеристики алгоритма

Особенности Описание
Задача может быть декомпозирована Исходная задача должна быть разложима на меньшие подобные подзадачи.
Подзадачи независимы Лучше всего, чтобы подзадачи были независимы друг от друга, что упрощает решение и объединение.
Есть условие завершения Должно существовать простое базовое условие, чтобы при достаточно малом масштабе задачи её можно было решить напрямую.
Решения можно объединять Решения подзадач должны эффективно объединяться в решение исходной задачи.

Анализ временной сложности

Временная сложность алгоритмов «разделяй и властвуй» обычно может быть выражена с помощьюосновной теоремыдля анализа; общий вид её рекуррентного соотношения таков: $$ T(n) = aT(\frac{n}{b}) + f(n) $$ где:

  • n— это размер задачи.
  • a— это количество подзадач, порождаемых декомпозицией.
  • n/b— это размер каждой подзадачи.
  • f(n)— это время, затраченное на этапы декомпозиции и слияния.

Например, для сортировки слиянием:

  • a = 2(разбивается на два подмассива)
  • b = 2(размер каждого подмассива уменьшается вдвое)
  • f(n) = O(n)(слияние двух отсортированных массивов занимает линейное время)
  • Согласно основной теореме, его временная сложность равнаO(n log n)。

Практические упражнения

Теперь пришло время закрепить ваше понимание алгоритмов «разделяй и властвуй». Попробуйте выполнить следующие упражнения:

Упражнение 1: реализуйте быструю сортировкуБыстрая сортировка — ещё один классический алгоритм «разделяй и властвуй». Его идея такова:

  1. Разделяй: Выберите «опорный» элемент (pivot) и переставьте элементы массива так, чтобы все элементы меньше опорного оказались слева, а все элементы больше опорного — справа (операция разделения).
  2. Властвуй: Рекурсивно выполните быструю сортировку для подмассивов слева и справа от опорного элемента.
  3. Слияние: Явное слияние не требуется, потому что после операции разделения массив уже частично упорядочен.

Ваша задача: На основе приведённого выше описания попробуйте написать код на Python для быстрой сортировки.

Упражнение 2: Найдите максимальную сумму подмассива в массивеЗадача: Дан целочисленный массив (который может содержать отрицательные числа), найдите непрерывный подмассив с максимальной суммой. Например, для[-2, 1, -3, 4, -1, 2, 1, -5, 4], максимальный подмассив — это[4, -1, 2, 1], а их сумма равна6。

Подсказка (подход «разделяй и властвуй»)：

  1. Разделите массив на левую и правую половины от середины.
  2. Максимальная сумма подмассива может возникать:в левой половине、в правой половине, илипри пересечении середины。
  3. Рекурсивно найдите максимальную сумму подмассива в левой половине и в правой половине.
  4. Вычислите максимальную сумму подмассива, которая пересекает среднюю точку (для этого нужно отдельно накапливать сумму слева и справа от средней точки, чтобы найти максимум).
  5. Верните максимум из трёх.

Попробуйте решить эту задачу, используя стратегию «разделяй и властвуй».

Другие расширения