Divide and Conquer Algorithm Merkitys: Selitetty esimerkeillä

Mitä ovat Divide and Conquer -algoritmit? (Ja ei, se ei ole "Jaa ja yhty")

Divide and Conquer on algoritminen paradigma (joskus virheellisesti nimeltään "Divide and Concur" - hauska ja sopiva nimi), samanlainen kuin ahne ja dynaaminen ohjelmointi. Tyypillinen Divide and Conquer -algoritmi ratkaisee ongelman seuraavien kolmen vaiheen avulla.

  1. Jaa : Jaa annettu ongelma samantyyppisiin ongelmiin. Tähän vaiheeseen sisältyy ongelman jakaminen pienemmiksi alaongelmiksi. Aliongelmien on oltava osa alkuperäistä ongelmaa. Tässä vaiheessa käytetään yleensä rekursiivista lähestymistapaa ongelman jakamiseen, kunnes mikään osa-ongelma ei ole enää jaettavissa. Tässä vaiheessa alakysymyksistä tulee luonteeltaan atomisia, mutta ne edustavat silti jonkin osan todellisesta ongelmasta.
  2. Valloita : Ratkaise nämä alaongelmat rekursiivisesti. Tämä vaihe saa paljon pienempiä ratkaistavia alaongelmia. Yleensä tällä tasolla ongelmat katsotaan "ratkaistuiksi" yksinään.
  3. Yhdistä : Yhdistä vastaukset asianmukaisesti. Kun pienemmät alaongelmat ratkaistaan, tämä vaihe yhdistää ne rekursiivisesti, kunnes ne muodostavat ratkaisun alkuperäiseen ongelmaan. Tämä algoritminen lähestymistapa toimii rekursiivisesti ja valloitus- ja yhdistämisvaiheet toimivat niin lähellä, että ne näkyvät yhtenä.

Tämän menetelmän avulla voimme yleensä vähentää ajan monimutkaisuutta suuressa määrin.

Esimerkiksi Bubble Sort käyttää monimutkaisuutta O(n^2), kun taas quicksort (Divide And Conquer -sovellus) vähentää ajan monimutkaisuuden O(nlog(n)). Lineaarisella haulla on aika monimutkaisuus O(n), kun taas binaarihaku (Divide And Conquer -sovellus) vähentää ajan monimutkaisuutta O(log(n)).

Seuraavassa on joitain standardialgoritmeja, jotka kuuluvat Divide and Conquer -algoritmeihin.

Binaarihaku  on hakualgoritmi. Kussakin vaiheessa algoritmi vertaa syöttöelementtiä (x) matriisin keskiosan arvoon. Jos arvot vastaavat, palauta keskiarvo. Muussa tapauksessa, jos x on pienempi kuin keskielementti, algoritmi palaa keskielementin vasemmalle puolelle, muuten se palaa keskielementin oikealle puolelle.

Quicksort  on lajittelualgoritmi. Algoritmi poimii kääntöelementin, järjestää taulukkoelementit uudelleen siten, että kaikki poimittua kääntöelementtiä pienemmät elementit siirtyvät kääntymän vasemmalle puolelle ja kaikki suuremmat elementit siirtyvät oikealle puolelle. Lopuksi algoritmi lajittelee rekursiivisesti alaelementit kääntöelementin vasemmalle ja oikealle puolelle.

Yhdistä lajittelu  on myös lajittelualgoritmi. Algoritmi jakaa matriisin kahteen puolikkaaseen, lajittelee ne rekursiivisesti ja yhdistää lopuksi kaksi lajiteltuja puolikkaita. Tämän algoritmin ajan monimutkaisuus on O(nLogn)joko paras tapa, keskimääräinen tapaus tai pahin tapa. On aika monimutkaisuutta voidaan helposti ymmärrettävissä toistuminen vastaa osoitteeseen: T(n) = 2T(n/2) + n.

Lähin  pistepari Ongelmana on löytää lähin pistepari pistejoukosta xy-tasossa. Ongelma voidaan ratkaista O(n^2)ajoissa laskemalla jokaisen pisteparin etäisyydet ja vertaamalla etäisyyksiä löytääksesi minimin. Divide and Conquer -algoritmi ratkaisee ongelman O(nLogn)ajoissa.

Strassenin algoritmi  on tehokas algoritmi kahden matriisin kertomiseen. Yksinkertainen menetelmä kahden matriisin kertomiseen vaatii 3 sisäkkäistä silmukkaa ja on O(n^3). Strassenin algoritmi kertoo kaksi matriisia O(n^2.8974)ajassa.

Cooley – Tukey nopea Fourier-muunnos (FFT) -algoritmi  on yleisin FFT: n algoritmi. Se on jaa ja valloita -algoritmi, joka toimii O(nlogn)ajoissa.

Karatsuban algoritmi  oli ensimmäinen kertolaskualgoritmi asymptoottisesti nopeampi kuin asteen asteen "luokan koulu" algoritmi. Se vähentää kahden n-merkitsevän luvun kertoluvun korkeintaan arvoon n ^ 1,585 (mikä on lähentämisen log 2 lähde 2: ssa) yksinumeroisiin tuotteisiin. Siksi se on nopeampi kuin klassinen algoritmi, joka vaatii n ^ 2 yksinumeroista tuotetta.

Divide and Conquer (D & C) vs. dynaaminen ohjelmointi (DP)

Molemmat paradigmat (D, C ja DP) jakavat annetun ongelman osahäiriöiksi ja ratkaisevat ongelmat. Kuinka valita yksi niistä tietylle ongelmalle? Jaa ja hallitse -toimintoa tulisi käyttää, kun samoja osahäiriöitä ei arvioida monta kertaa. Muuten tulisi käyttää dynaamista ohjelmointia tai muistiinpanoa.

Esimerkiksi binaarihaku on Divide and Conquer -algoritmi, emme koskaan arvioi samoja alaongelmia uudelleen. Toisaalta, n: nnen Fibonacci-luvun laskemiseksi on suositeltava dynaaminen ohjelmointi.