TechCodeview

Divide and Conquer on algoritminen malli. Algoritmisissa menetelmissä suunnitellaan kiistaa valtavasta syötteestä, jakaa syöte pienempiin osiin, päättää kunkin pienen palan ongelma ja sitten yhdistää palakohtaiset ratkaisut globaaliksi ratkaisuksi. Tätä ongelmanratkaisumekanismia kutsutaan Divide & Conquer -strategiaksi.

Divide and Conquer -algoritmi koostuu kiistasta seuraavien kolmen vaiheen avulla.

Jakaaalkuperäinen ongelma osaongelmien joukkoon.Valloittaa:Ratkaise jokainen osaongelma yksitellen, rekursiivisesti.Yhdistää:Yhdistä aliongelmien ratkaisut saadaksesi ratkaisun koko ongelmaan.

Yleensä voimme seurata hajota ja hallitse lähestymistapa kolmivaiheisessa prosessissa.

Esimerkkejä: Tietyt tietokonealgoritmit perustuvat Divide & Conquer -lähestymistapaan:

1. Suurin ja pienin ongelma
2. Binäärihaku
3. Lajittelu (yhdistä lajittelu, nopea lajittelu)
4. Hanoin torni.

Divide & Conquer -strategian perusteet:

Divide & Conquer -strategiassa on kaksi perusperiaatetta:

1. Suhdekaava
2. Pysähdysehto

1. Suhdekaava: Se on kaava, jonka luomme annetusta tekniikasta. Kaavan luomisen jälkeen käytämme D&C-strategiaa, eli puramme ongelman rekursiivisesti ja ratkaisemme rikkinäiset osaongelmat.

2. Pysähdysehto: Kun ratkaisemme ongelman Divide & Conquer -strategian avulla, meidän on tiedettävä, että kuinka kauan meidän on sovellettava Divide & Conquer -ohjelmaa. Joten tilaa, jossa tarvetta pysäyttää D&C:n rekursiovaiheet, kutsutaan pysäytysehdoksi.

Hajota ja hallitse -lähestymistavan sovellukset:

Seuraavat algoritmit perustuvat Divide and Conquer -tekniikan käsitteeseen:

Binäärihaku:Binäärihakualgoritmi on hakualgoritmi, jota kutsutaan myös puolivälihauksi tai logaritmiksi hauksi. Se toimii vertaamalla tavoitearvoa lajitellun taulukon keskimmäiseen elementtiin. Vertailun jälkeen, jos arvo poikkeaa, puolikko, joka ei voi sisältää kohdetta, lopulta eliminoituu, minkä jälkeen hakua jatketaan toiselta puoliskolta. Tarkastelemme jälleen keskimmäistä elementtiä ja vertaamme sitä tavoitearvoon. Prosessi toistuu, kunnes tavoitearvo saavutetaan. Jos havaitsimme toisen puolen tyhjäksi haun päätyttyä, voidaan päätellä, että kohdetta ei ole taulukossa.Pikalajittelu:Se on tehokkain lajittelualgoritmi, joka tunnetaan myös nimellä osionvaihtolajittelu. Se alkaa valitsemalla pivot-arvo taulukosta ja jakamalla loput taulukon elementit kahdeksi alitaulukoksi. Osio tehdään vertaamalla kutakin elementtiä pivot-arvoon. Se vertaa, onko elementillä suurempi vai pienempi arvo kuin pivot, ja lajittelee sitten taulukot rekursiivisesti.Yhdistä lajittelu:Se on lajittelualgoritmi, joka lajittelee taulukon tekemällä vertailuja. Se alkaa jakamalla taulukon alitaulukkoon ja lajittelee sitten rekursiivisesti jokaisen niistä. Kun lajittelu on suoritettu, se yhdistää ne takaisin.Lähin pistepari:Se on laskennallisen geometrian ongelma. Tämä algoritmi korostaa lähimmän pisteparin selvittämistä metrisestä avaruudesta annettuna n pistettä siten, että pisteparien välinen etäisyys on minimaalinen.Strassenin algoritmi:Se on matriisin kertolaskualgoritmi, joka on nimetty Volker Strassenin mukaan. Se on osoittautunut paljon nopeammaksi kuin perinteinen algoritmi, kun se toimii suurilla matriiseilla.Cooley-Tukey Fast Fourier Transform (FFT) -algoritmi:Fast Fourier Transform -algoritmi on nimetty J. W. Cooleyn ja John Turkeyn mukaan. Se noudattaa hajota ja hallitse -lähestymistapaa ja asettaa O(nlogn) monimutkaisuuden.Karatsuba-algoritmi nopeaan kertolaskuun:Se on yksi perinteisen ajan nopeimmista kertolaskualgoritmeista, jonka Anatoli Karatsuba keksi 1960-luvun lopulla ja julkaistiin vuonna 1962. Se kertoo kaksi n-numeroista lukua tällä tavalla vähentämällä sen enintään yksinumeroiseksi.

Hajota ja hallitse -ohjelman edut

• Divide and Conquer yleensä ratkaisee onnistuneesti yhden suurimmista ongelmista, kuten Hanoin tornin, matemaattisen palapelin. On haastavaa ratkaista monimutkaisia ​​ongelmia, joista sinulla ei ole perusideaa, mutta hajota ja hallitse -lähestymistavan avulla se on vähentänyt vaivaa, koska se pyrkii jakamaan pääongelman kahteen puolikkaaseen ja ratkaisemaan ne sitten rekursiivisesti. Tämä algoritmi on paljon nopeampi kuin muut algoritmit.
• Se käyttää välimuistia tehokkaasti viemättä paljon tilaa, koska se ratkaisee välimuistin yksinkertaiset aliongelmat hitaamman päämuistin käyttämisen sijaan.
• Se on taitavampi kuin vastineensa Brute Force -tekniikka.
• Koska nämä algoritmit estävät rinnakkaisuuden, siihen ei liity mitään muutoksia ja niitä käsittelevät järjestelmät, jotka sisältävät rinnakkaiskäsittelyn.

Hajota ja hallitse -ohjelman haitat

• Koska suurin osa sen algoritmeista on suunniteltu sisällyttämällä rekursio, se vaatii korkeaa muistinhallintaa.
• Selkeä pino voi käyttää tilaa liikaa.
• Se voi jopa kaataa järjestelmän, jos rekursio suoritetaan tiukasti suurempi kuin CPU:ssa oleva pino.