Algoritmus Divide and Conquer Význam: Vysvetlený pomocou príkladov

Čo sú to algoritmy Divide and Conquer? (A nie, nie je to „Rozdeľujte a súhlaste“)

Divide and Conquer je algoritmická paradigma (niekedy mylne nazývaná „Divide and Concur“ - vtipný a výstižný názov), podobná chamtivosti a dynamickému programovaniu. Typický algoritmus Divide and Conquer vyrieši problém pomocou nasledujúcich troch krokov.

  1. Rozdeliť : Rozdeliť zadanú úlohu na podproblémy rovnakého typu. Tento krok zahŕňa rozdelenie problému na menšie čiastkové problémy. Čiastkové problémy by mali predstavovať súčasť pôvodného problému. Tento krok všeobecne vyžaduje rekurzívny prístup k rozdeleniu problému, kým nie je ďalej deliteľný žiadny čiastkový problém. V tejto fáze sa čiastkové problémy stávajú atómovou, ale stále predstavujú určitú časť skutočného problému.
  2. Dobyť : Rekurzívne vyriešiť tieto čiastkové problémy. Tento krok obsahuje mnoho menších čiastkových problémov, ktoré je potrebné vyriešiť. Spravidla sa na tejto úrovni problémy považujú za „vyriešené“ samy.
  3. Kombinujte : Vhodne kombinujte odpovede. Keď sa vyriešia menšie čiastkové problémy, táto fáza ich rekurzívne kombinuje, až kým nevymyslia riešenie pôvodného problému. Tento algoritmický prístup funguje rekurzívne a kroky dobývania a spájania fungujú tak blízko, že vyzerajú ako jeden celok.

Táto metóda nám zvyčajne umožňuje do značnej miery znížiť časovú zložitosť.

Napríklad Bubble Sort využíva zložitosť O(n^2), zatiaľ čo quicksort (aplikácia Divide And Conquer) redukuje časovú zložitosť na O(nlog(n)). Lineárne vyhľadávanie má časovú zložitosť O(n), zatiaľ čo binárne vyhľadávanie (aplikácia Divide And Conquer) znižuje časovú zložitosť na O(log(n)).

Nasleduje niekoľko štandardných algoritmov z radu algoritmov Divide and Conquer.

Binárne vyhľadávanie  je vyhľadávací algoritmus. V každom kroku algoritmus porovnáva vstupný prvok (x) s hodnotou stredného prvku v poli. Ak sa hodnoty zhodujú, vráťte index stredu. V opačnom prípade, ak je x menšie ako stredný prvok, potom sa algoritmus vráti na ľavú stranu stredného prvku, inak sa vráti na pravú stranu stredného prvku.

Quicksort  je algoritmus triedenia. Algoritmus vyberie otočný prvok, zmení usporiadanie prvkov poľa tak, že všetky prvky menšie ako vybraný otočný prvok sa presunú na ľavú stranu otočného prvku a všetky väčšie prvky sa presunú na pravú stranu. Nakoniec algoritmus rekurzívne triedi podradné sústavy vľavo a vpravo od otočného prvku.

Zlúčiť zoradenie  je tiež algoritmus triedenia. Algoritmus rozdelí pole na dve polovice, rekurzívne ich roztriedi a nakoniec tieto dve zoradené polovice spojí. Časová zložitosť tohto algoritmu je O(nLogn), či už je to najlepší prípad, priemerný prípad alebo najhorší prípad. Časová náročnosť je to možno ľahko pochopiť z opakovania sa rovná: T(n) = 2T(n/2) + n.

Najbližší pár bodov  Problémom je nájsť najbližšiu dvojicu bodov v množine bodov v rovine xy. Problém je možné vyriešiť O(n^2)včas výpočtom vzdialeností každého páru bodov a porovnaním vzdialeností s cieľom nájsť minimum. Algoritmus Divide and Conquer problém vyrieši O(nLogn)včas.

Strassenov algoritmus  je efektívny algoritmus na znásobenie dvoch matíc. Jednoduchá metóda na násobenie dvoch matíc vyžaduje 3 vnorené slučky a je O(n^3). Strassenov algoritmus vynásobí dve matice v O(n^2.8974)čase.

Cooley – Tukey rýchla Fourierova transformácia (FFT)  je najbežnejším algoritmom pre FFT. Je to algoritmus rozdelenia a dobývania, ktorý funguje O(nlogn)včas.

Algoritmus Karatsuba  bol prvý multiplikačný algoritmus asymptoticky rýchlejší ako kvadratický algoritmus „základnej školy“. Redukuje násobenie dvoch n-ciferných čísel na najviac n ^ 1,585 (čo je aproximácia log 3 v základnom 2) jednociferných produktov. Je preto rýchlejší ako klasický algoritmus, ktorý vyžaduje n ^ 2 jednociferných produktov.

Rozdeľ a panuj (D & C) vs dynamické programovanie (DP)

Obe paradigmy (D & C a DP) rozdeľujú daný problém na podproblémy a riešia podproblémy. Ako si vybrať jeden z nich pre daný problém? Divide and Conquer by sa mali použiť, keď sa rovnaké podproblémy nehodnotia mnohokrát. V opačnom prípade by sa malo použiť dynamické programovanie alebo memorovanie.

Napríklad Binárne vyhľadávanie je algoritmus Divide and Conquer, už nikdy nevyhodnocujeme rovnaké podproblémy. Na druhej strane by sa pre výpočet n-tého Fibonacciho čísla malo uprednostniť dynamické programovanie.