В этом руководстве вы узнаете, как работает алгоритм «разделяй и властвуй». Мы также сравним подход «разделяй и властвуй» с другими подходами для решения рекурсивной проблемы.
Алгоритм разделяй и властвуй стратегия решения большой проблемы путем
- разбиение проблемы на более мелкие подзадачи
- решение подзадач и
- объединяя их, чтобы получить желаемый результат.
Чтобы использовать алгоритм «разделяй и властвуй», используется рекурсия . Узнайте о рекурсии на разных языках программирования:
- Рекурсия в Java
- Рекурсия в Python
- Рекурсия в C ++
Как работают алгоритмы «разделяй и властвуй»?
Вот шаги:
- Разделить : разделите данную проблему на подзадачи с помощью рекурсии.
- Победить : рекурсивно решать более мелкие подзадачи. Если подзадача достаточно мала, решите ее напрямую.
- Объединить: объединить решения подзадач, которые являются частью рекурсивного процесса, для решения актуальной проблемы.
Давайте разберемся с этой концепцией на примере.
Здесь мы будем отсортировать массив, используя подход «разделяй и властвуй» (то есть сортировка слиянием).
- Пусть данный массив будет:
Массив для сортировки слиянием - Разделите массив на две половины.
Разделите массив на две части.
Снова разделите каждую часть рекурсивно на две половины, пока не получите отдельные элементы.
Разделите массив на более мелкие части - Теперь объедините отдельные элементы в отсортированном виде. Здесь побеждайте и соединяйте шаги бок о бок.
Объедините подчасти
Сложность времени
Сложность алгоритма «разделяй и властвуй» рассчитывается с помощью основной теоремы.
T (n) = aT (n / b) + f (n), где n = размер входных данных, a = количество подзадач в рекурсии, n / b = размер каждой подзадачи. Предполагается, что все подзадачи имеют одинаковый размер. f (n) = стоимость работы, выполненной вне рекурсивного вызова, которая включает стоимость разделения проблемы и стоимость объединения решений.
Давайте рассмотрим пример, чтобы найти временную сложность рекурсивной задачи.
Для сортировки слиянием уравнение можно записать как:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Где, a = 2 (каждый раз проблема делится на 2 подзадачи) n / b = n / 2 (размер каждой подзадачи составляет половину входных данных) f (n) = время, затраченное на разделение задачи и слияние подзадач T (n / 2) = O (n log n) (Чтобы понять это, обратитесь к основная теорема.) Теперь T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Разделяй и властвуй против динамического подхода
Подход «разделяй и властвуй» делит проблему на более мелкие подзадачи; эти подзадачи в дальнейшем решаются рекурсивно. Результат каждой подзадачи не сохраняется для использования в будущем, тогда как при динамическом подходе результат каждой подзадачи сохраняется для использования в будущем.
Используйте подход «разделяй и властвуй», когда одна и та же подзадача не решается несколько раз. Используйте динамический подход, если результат подзадачи будет использоваться несколько раз в будущем.
Давайте разберемся в этом на примере. Предположим, мы пытаемся найти ряд Фибоначчи. Потом,
Подход «разделяй и властвуй»:
fib (n) Если n <2, вернуть 1 Else, вернуть f (n - 1) + f (n -2)
Динамический подход:
mem = () fib (n) Если n в памяти: вернуть mem (n) else, Если n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f возврат f
При динамическом подходе mem хранит результат каждой подзадачи.
Преимущества алгоритма разделяй и властвуй
- Сложность умножения двух матриц с использованием наивного метода составляет O (n 3 ), тогда как при использовании подхода «разделяй и властвуй» (т. Е. Умножения матриц Штрассена) составляет O (n 2,8074 ). Этот подход также упрощает другие проблемы, такие как Ханойская башня.
- Этот подход подходит для многопроцессорных систем.
- Он эффективно использует кеши памяти.
Разделяй и властвуй приложения
- Бинарный поиск
- Сортировка слиянием
- Быстрая сортировка
- Умножение матриц Штрассена
- Алгоритм Карацубы
