Алгоритм поділу та підкорення Значення: Пояснення на прикладах

Що таке алгоритми поділу та підкорення? (І ні, це не "Розділяйся та згоджуйся")

Divide and Conquer - це алгоритмічна парадигма (іноді помилково називана "Divide and Concur" - смішна і влучна назва), подібна до Жадібного та Динамічного програмування. Типовий алгоритм Divide and Conquer вирішує проблему, використовуючи наступні три кроки.

  1. Розділити : Розбийте задану задачу на підзадачі одного типу. Цей крок передбачає розбиття проблеми на менші підзадачі. Підзадачі повинні представляти собою частину вихідної проблеми. Цей крок, як правило, застосовує рекурсивний підхід для розподілу проблеми до тих пір, поки жодна підзадача не поділиться далі. На цьому етапі підпроблеми набувають атомної природи, але все ще представляють певну частину актуальної проблеми.
  2. Conquer : Рекурсивно вирішуйте ці підзадачі. Цей крок отримує багато менших підзадач, які потрібно вирішити. Як правило, на цьому рівні проблеми вважаються «вирішеними» самостійно.
  3. Поєднати : Відповідно поєднати відповіді. Коли вирішуються менші підзадачі, цей етап рекурсивно поєднує їх, доки вони не сформулюють рішення вихідної проблеми. Цей алгоритмічний підхід працює рекурсивно, і кроки conquer & merge працюють настільки близько, що здаються єдиними.

Цей метод, як правило, дозволяє нам значно зменшити складність часу.

Наприклад, Bubble Sort використовує складність O(n^2), тоді як швидка сортування (додаток Divide And Conquer) зменшує складність часу до O(nlog(n)). Лінійний пошук має складність у часі O(n), тоді як двійковий пошук (додаток "Розділи та завоюй") зменшує складність часу до O(log(n)).

Нижче наведено деякі стандартні алгоритми, що належать до різноманітних алгоритмів Divide and Conquer.

Двійковий пошук  - це алгоритм пошуку. На кожному кроці алгоритм порівнює вхідний елемент (x) зі значенням середнього елемента в масиві. Якщо значення збігаються, поверніть індекс середнього. В іншому випадку, якщо x менше середнього елемента, тоді алгоритм повторюється до лівої сторони середнього елемента, інакше він повторюється до правої сторони середнього елемента.

Quicksort  - це алгоритм сортування. Алгоритм вибирає елемент повороту, переставляє елементи масиву таким чином, що всі елементи, менші за вибраний поворотний елемент, переміщаються в ліву сторону повороту, а всі більші елементи - у праву сторону. Нарешті, алгоритм рекурсивно сортує підмасиви ліворуч та праворуч від елемента обертання.

Merge Sort  - це також алгоритм сортування. Алгоритм ділить масив на дві половини, рекурсивно їх сортує і, нарешті, об’єднує дві відсортовані половини. Часова складність цього алгоритму - O(nLogn)це найкращий випадок, середній випадок чи найгірший випадок. Це тимчасова складність можна легко зрозуміти з рекурентних прирівнює до: T(n) = 2T(n/2) + n.

Найближча пара точок  Проблема полягає в тому, щоб знайти найближчу пару точок у безлічі точок у площині xy. Проблему можна вирішити O(n^2)вчасно, обчисливши відстані кожної пари точок і порівнявши відстані, щоб знайти мінімум. Алгоритм Divide and Conquer вирішує проблему O(nLogn)вчасно.

Алгоритм Штрассена  - це ефективний алгоритм множення двох матриць. Простий метод множення двох матриць потребує 3 вкладених циклів і є O(n^3). Алгоритм Штрассена множить дві матриці в O(n^2.8974)часі.

Кулі – Тукі Швидке перетворення Фур'є (БПФ)  є найпоширенішим алгоритмом ШПФ. Це алгоритм поділу та завоювання, який працює в O(nlogn)часі.

Алгоритм Карацуби  був першим алгоритмом множення, який був асимптотично швидшим за квадратний алгоритм "шкільної школи". Це зменшує множення двох n-значних чисел щонайбільше до n ^ 1,585 (що є наближенням журналу 3 в основі 2) однозначних добутків. Отже, це швидше, ніж класичний алгоритм, який вимагає n ^ 2 одноцифрових продуктів.

Діли і владай (D & C) проти динамічного програмування (DP)

Обидві парадигми (D & C та DP) поділяють задану задачу на підзадачі та вирішують підзадачі. Як вибрати одну з них для даної задачі? Розділяй і володар слід використовувати, коли одні й ті ж підзадачі не оцінюються багато разів. В іншому випадку слід використовувати динамічне програмування або пам'ять.

Наприклад, двійковий пошук - це алгоритм Divide and Conquer, ми більше ніколи не оцінюємо ті самі підзадачі. З іншого боку, для обчислення n-го числа Фібоначчі слід віддавати перевагу динамічному програмуванню.