V tomto výučbe sa dozviete, ako funguje algoritmus rozdelenia a dobývania. Budeme tiež porovnávať prístup rozdeliť a panovať s ostatnými prístupmi k riešeniu rekurzívneho problému.
Rozdeľ a panuj je stratégií na riešenie vysokej problému
- rozdelenie problému na menšie čiastkové problémy
- riešenie čiastkových problémov a
- ich kombináciou získate požadovaný výstup.
Na použitie algoritmu divide and conquer sa používa rekurzia . Dozviete sa viac o rekurzii v rôznych programovacích jazykoch:
- Rekurzia v Jave
- Rekurzia v Pythone
- Rekurzia v C ++
Ako fungujú algoritmy rozdelenia a dobývania?
Týka sa to týchto krokov:
- Rozdeliť : Rozdeľte daný problém na čiastkové problémy pomocou rekurzie.
- Dobyť : Menšie čiastkové problémy riešte rekurzívne. Ak je podproblém dosť malý, vyriešte ho priamo.
- Kombinovať: Skombinujte riešenia čiastkových problémov, ktoré sú súčasťou rekurzívneho procesu, na vyriešenie skutočného problému.
Pochopme tento koncept pomocou príkladu.
Tu zoradíme pole pomocou prístupu rozdelenia a dobytia (tj. Zlúčenie).
- Nech je dané pole:
Pole pre zlúčenie - Pole rozdeľte na dve polovice.
Rozdeľte pole na dve podčasti.
Opäť rozdelte každú podčasti rekurzívne na dve polovice, kým nezískate jednotlivé prvky.
Rozdeľte pole na menšie časti - Teraz kombinujte jednotlivé prvky triedeným spôsobom. Tu idú dobyvané a kombinované kroky vedľa seba.
Spojte podčasti
Časová zložitosť
Zložitosť algoritmu rozdelenia a dobývania sa počíta pomocou hlavnej vety.
T (n) = aT (n / b) + f (n), kde, n = veľkosť vstupu a = počet čiastkových problémov v rekurzii n / b = veľkosť každého čiastkového problému. Predpokladá sa, že všetky podproblémy majú rovnakú veľkosť. f (n) = náklady na prácu vykonanú mimo rekurzívneho hovoru, ktorá zahŕňa náklady na rozdelenie problému a náklady na zlúčenie riešení
Zoberme si príklad na zistenie časovej zložitosti rekurzívneho problému.
Pre zlúčenie je možné rovnicu napísať ako:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Kde a = 2 (zakaždým je problém rozdelený na 2 podproblémy) n / b = n / 2 (veľkosť každého čiastkového problému je polovica vstupu) f (n) = čas potrebný na rozdelenie problému a zlúčenie čiastkových problémov T (n / 2) = O (n log n) (Aby ste tomu porozumeli, pozrite si prosím hlavná veta.) Teraz, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Dynamický prístup Divide and Conquer Vs
Prístup rozdelenia a dobývania rozdeľuje problém na menšie podproblémy; tieto subproblémy sa ďalej riešia rekurzívne. Výsledok každého čiastkového problému nie je uložený pre budúce použitie, zatiaľ čo pri dynamickom prístupe je výsledok každého čiastkového problému uložený pre budúce použitie.
Použite prístup rozdelenia a panovania, keď sa rovnaký podproblém nevyrieši viackrát. Dynamický prístup použite, ak sa má v budúcnosti použiť výsledok čiastkového problému viackrát.
Pochopme to na príklade. Predpokladajme, že sa snažíme nájsť Fibonacciho sériu. Potom,
Prístup Rozdeľuj a panuj:
fib (n) Ak n <2, návrat 1 Inak, návrat f (n - 1) + f (n -2)
Dynamický prístup:
mem = () fib (n) Ak n v mem: návrat mem (n) else, Ak n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f návrat f
V dynamickom prístupe mem ukladá výsledky každého čiastkového problému.
Výhody algoritmu Divide and Conquer
- Zložitosť násobenia dvoch matíc pomocou naivnej metódy je O (n 3 ), zatiaľ čo použitie prístupu rozdelenia a panovania (tj. Strassenova maticová multiplikácia) je O (n 2,8074 ). Tento prístup tiež zjednodušuje ďalšie problémy, napríklad Hanojskú vežu.
- Tento prístup je vhodný pre systémy s viacerými procesmi.
- Efektívne využíva pamäte cache.
Rozdeľujte a dobývajte aplikácie
- Binárne vyhľadávanie
- Zlúčiť zoradenie
- Rýchle triedenie
- Strassenovo násobenie matíc
- Karatsuba Algoritmus
