Tässä opetusohjelmassa opit jakamaan ja hallitsemaan -algoritmin toiminnan. Vertaamme myös jakamisen ja valloittamisen lähestymistapaa muihin lähestymistapoihin rekursiivisen ongelman ratkaisemiseksi.
Hajota ja hallitse algoritmi on strategia ratkaista suuri ongelma
- hajottamalla ongelma pienempiin alaongelmiin
- alaongelmien ratkaiseminen ja
- yhdistämällä ne halutun tuloksen saamiseksi.
Divide and Conquer -algoritmin käyttämiseen käytetään rekursiota . Lisätietoja rekursiosta eri ohjelmointikielillä:
- Rekursio Java-kielellä
- Rekursio Pythonissa
- Rekursio C ++: ssa
Kuinka jakaa ja valloittaa algoritmit toimivat?
Tässä ovat vaiheet:
- Jaa : Jaa annettu ongelma alakysymyksiin rekursiota käyttämällä.
- Valloita : Ratkaise pienemmät alaongelmat rekursiivisesti. Jos osaongelma on tarpeeksi pieni, ratkaise se suoraan.
- Yhdistä: Yhdistä rekursiiviseen prosessiin kuuluvien alaongelmien ratkaisut todellisen ongelman ratkaisemiseksi.
Ymmärretään tämä käsite esimerkin avulla.
Tässä lajitellaan matriisi käyttämällä jakamis- ja valloitusmenetelmää (ts. Yhdistämislajittelu).
- Olkoon annettu taulukko:
Array for merge sort - Jaa taulukko kahteen puolikkaaseen.
Jaa taulukko kahteen osaan
Jälleen, jaa jokainen osa rekursiivisesti kahteen puolikkaaseen, kunnes saat yksittäisiä elementtejä.
Jaa taulukko pienempiin osiin - Yhdistä nyt yksittäiset elementit lajiteltuina. Täällä valloittaa ja yhdistää vaiheet kulkevat rinnakkain.
Yhdistä alaluvut
Ajan monimutkaisuus
Divide and Conquer -algoritmin monimutkaisuus lasketaan pääteoreeman avulla.
T (n) = aT (n / b) + f (n), missä, n = syötteen koko a = rekursiossa olevien aliongelmien lukumäärä n / b = kunkin alaongelman koko. Kaikilla alaongelmilla oletetaan olevan sama koko. f (n) = rekursiivisen puhelun ulkopuolella tehdyn työn hinta, joka sisältää ongelman jakamiskustannukset ja ratkaisujen yhdistämisen kustannukset
Otetaan esimerkki rekursiivisen ongelman aikakompleksin löytämiseksi.
Yhdistämisen lajittelua varten yhtälö voidaan kirjoittaa seuraavasti:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Missä, a = 2 (joka kerta, ongelma on jaettu kahteen osaongelmaan) n / b = n / 2 (jokaisen osaongelman koko on puolet syötteestä) f (n) = aika, joka kului ongelman jakamiseen ja osaongelmien yhdistämiseen T (n / 2) = O (n log n) (Tämän ymmärtämiseksi katso päälause.) Nyt T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Divide and Conquer Vs Dynamic -lähestymistapa
Divide and Conquer -lähestymistapa jakaa ongelman pienempiin osahäiriöihin; nämä alaongelmat ratkaistaan edelleen rekursiivisesti. Kunkin alaongelman tulosta ei tallenneta myöhempää käyttöä varten, kun taas dynaamisessa lähestymistavassa kunkin osaongelman tulos tallennetaan tulevaa käyttöä varten.
Käytä jaa ja valloita -lähestymistapaa, kun samaa osahäiriötä ei ratkaista useita kertoja. Käytä dynaamista lähestymistapaa, kun osaongelman tulosta käytetään tulevaisuudessa useita kertoja.
Ymmärretään tämä esimerkillä. Oletetaan, että yritämme löytää Fibonacci-sarjan. Sitten,
Jaa ja valloita -lähestymistapa:
fib (n) Jos n <2, palauta 1 Muu, palauta f (n - 1) + f (n -2)
Dynaaminen lähestymistapa:
mem = () fib (n) Jos n mem: palauta mem (n) muu, Jos n <2, f = 1 muu, f = f (n - 1) + f (n -2) mem (n) = f paluu f
Dynaamisessa lähestymistavassa mem tallentaa kunkin osaongelman tuloksen.
Divide and Conquer -algoritmin edut
- Kahden naiivimenetelmän matriisien kertomisen monimutkaisuus on O (n 3 ), kun taas divide and conquer -lähestymistapaa (eli Strassenin matriisikertoja) käytettäessä O (n 2,8074 ). Tämä lähestymistapa yksinkertaistaa myös muita ongelmia, kuten Hanoin torni.
- Tämä lähestymistapa soveltuu moniprosessointijärjestelmiin.
- Se käyttää tehokkaasti muistivälimuistia.
Jaa ja hallitse sovelluksia
- Binaarihaku
- Yhdistä lajittelu
- Nopea lajittelu
- Strassenin Matrix-kertolasku
- Karatsuban algoritmi
