У цьому підручнику ви дізнаєтесь, як працює алгоритм поділу та завоювання. Ми також порівняємо підхід "розділи і завоюй" та інші підходи для вирішення рекурсивної проблеми.
Алгоритм « розділи і завоюй» - це стратегія вирішення великої проблеми за допомогою
- розбиття проблеми на менші підзадачі
- вирішення підзадач, і
- комбінуючи їх, щоб отримати бажаний результат.
Для використання алгоритму поділу та завоювання використовується рекурсія . Дізнайтеся про рекурсію на різних мовах програмування:
- Рекурсія на Java
- Рекурсія в Python
- Рекурсія в C ++
Як працюють алгоритми поділу та завоювання?
Ось такі кроки:
- Розділити : Розділіть задану задачу на підзадачі за допомогою рекурсії.
- Conquer : Розв’язуйте менші підзадачі рекурсивно. Якщо підзадача досить мала, вирішіть її безпосередньо.
- Об’єднати: об’єднайте рішення підзадач, які є частиною рекурсивного процесу, для вирішення фактичної проблеми.
Давайте розберемося в цьому понятті на прикладі.
Тут ми будемо сортувати масив, використовуючи підхід розділити та завоювати (тобто сортувати злиттям).
- Нехай даний масив буде:
Масив для сортування за злиттям - Розділіть масив на дві половини.
Поділіть масив на дві підчастини
Знову ж, розділіть кожну підчастину рекурсивно на дві половини, поки не отримаєте окремі елементи.
Поділіть масив на менші частини - Тепер об’єднайте окремі елементи в сортуванні. Тут підкорюйте та комбінуйте сходинки йдіть поруч.
Поєднайте підрозділи
Складність часу
Складність алгоритму поділу та завоювання обчислюється за допомогою головної теореми.
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 Інакше, поверніть f (n - 1) + f (n -2)
Динамічний підхід:
mem = () fib (n) Якщо n у mem: повернути mem (n) else, якщо n <2, f = 1 ще, f = f (n - 1) + f (n -2) mem (n) = f повернення f
При динамічному підході mem зберігає результат кожної підзадачі.
Переваги алгоритму поділу та завоювання
- Складність множення двох матриць за допомогою наївного методу становить O (n 3 ), тоді як за допомогою підходу поділяй і володар (тобто множення матриць Штрассена) дорівнює O (n 2.8074 ). Цей підхід також спрощує інші проблеми, такі як Ханойська вежа.
- Цей підхід підходить для багатопроцесорних систем.
- Це ефективно використовує кеші пам'яті.
Розділіть і завоюйте програми
- Двійковий пошук
- Сортувати злиття
- Швидке сортування
- Множення матриці Штрассена
- Алгоритм Карацуби
