Deli in vladaj je algoritemski vzorec. Pri algoritemskih metodah je zasnova vzeti spor o velikem vnosu, razdeliti vhod na manjše dele, odločiti o problemu na vsakem od majhnih kosov in nato združiti rešitve po kosih v globalno rešitev. Ta mehanizem reševanja problema se imenuje strategija deli in vladaj.

Algoritem razdeli in vladaj je sestavljen iz spora v naslednjih treh korakih.

Razdeliprvotni problem v niz podproblemov.Osvoji:Rešite vsak podproblem posebej, rekurzivno.Združite:Sestavite rešitve podproblemov, da dobite rešitev celotnega problema.

Na splošno lahko sledimo deli in vladaj pristop v treh korakih.

Primeri: Posebni računalniški algoritmi temeljijo na pristopu razdeli in vladaj:

1. Največji in najmanjši problem
2. Binarno iskanje
3. Razvrščanje (spojno razvrščanje, hitro razvrščanje)
4. Hanojski stolp.

Osnove strategije deli in vladaj:

Obstajata dva temelja strategije razdeli in vladaj:

1. Relacijska formula
2. Stanje ustavitve

1. Relacijska formula: To je formula, ki jo ustvarimo iz dane tehnike. Po generiranju formule uporabimo strategijo D&C, tj. rekurzivno razčlenimo problem in rešimo zlomljene podprobleme.

2. Pogoj zaustavitve: Ko rešimo težavo s strategijo razdeli in vladaj, potem moramo vedeti, koliko časa moramo uporabljati razdeli in vladaj. Torej se stanje, ko je treba ustaviti naše rekurzivne korake D&C, imenuje pogoj zaustavitve.

Uporaba pristopa deli in vladaj:

Naslednji algoritmi temeljijo na konceptu tehnike deli in vladaj:

Binarno iskanje:Binarni iskalni algoritem je iskalni algoritem, ki ga imenujemo tudi polintervalno iskanje ali logaritemsko iskanje. Deluje tako, da primerja ciljno vrednost s srednjim elementom, ki obstaja v razvrščeni matriki. Če se po primerjavi vrednosti razlikuje, bo polovica, ki ne more vsebovati cilja, sčasoma izločena, čemur bo sledilo nadaljevanje iskanja na drugi polovici. Ponovno bomo upoštevali srednji element in ga primerjali s ciljno vrednostjo. Postopek se ponavlja, dokler ni dosežena ciljna vrednost. Če smo po končanem iskanju ugotovili, da je druga polovica prazna, lahko sklepamo, da cilja ni v nizu.Hitro razvrščanje:Je najučinkovitejši algoritem razvrščanja, ki je znan tudi kot razvrščanje s particijsko izmenjavo. Začne se z izbiro vrtilne vrednosti iz matrike, čemur sledi delitev preostalih elementov matrike na dve podmatriki. Razdelitev je narejena s primerjavo vsakega od elementov z vrtilno vrednostjo. Primerja, ali ima element večjo ali manjšo vrednost od vrtišča, nato pa rekurzivno razvrsti nize.Spoji Razvrsti:Je algoritem za razvrščanje, ki s primerjavami razvršča niz. Začne se tako, da matriko razdeli na podmatriko in nato vsako od njih rekurzivno razvrsti. Ko je razvrščanje končano, jih združi nazaj.Najbližji par točk:To je problem računalniške geometrije. Ta algoritem poudarja iskanje najbližjega para točk v metričnem prostoru glede na n točk, tako da mora biti razdalja med parom točk minimalna.Strassenov algoritem:Gre za algoritem za matrično množenje, ki je dobil ime po Volkerju Strassenu. Izkazalo se je, da je veliko hitrejši od tradicionalnega algoritma, ko deluje na velikih matricah.Algoritem Cooley-Tukey Fast Fourier Transform (FFT):Algoritem hitre Fourierove transformacije je poimenovan po J. W. Cooleyju in Johnu Turkeyju. Sledi pristopu deli in vladaj in uvaja zapletenost O(nlogn).Karatsuba algoritem za hitro množenje:Je eden najhitrejših algoritmov tradicionalnega množenja, ki ga je izumil Anatolij Karacuba konec leta 1960 in je bil objavljen leta 1962. Množi dve n-mestni števili na tak način, tako da ju reducira na največ enomestno.

Prednosti razdeli in vladaj

• Deli in vladaj teži k uspešnemu reševanju enega največjih problemov, kot je Hanojski stolp, matematična uganka. Zahtevno je reševati zapletene probleme, za katere nimate osnovnega pojma, vendar je s pomočjo pristopa deli in vladaj zmanjšal napor, saj deluje tako, da glavni problem razdeli na dve polovici in ju nato rekurzivno rešuje. Ta algoritem je veliko hitrejši od drugih algoritmov.
• Učinkovito uporablja predpomnilnik, ne da bi zasedel veliko prostora, ker rešuje preproste podprobleme znotraj predpomnilnika, namesto da bi dostopal do počasnejšega glavnega pomnilnika.
• Je bolj spretna od svoje nasprotne tehnike Brute Force.
• Ker ti algoritmi zavirajo paralelizem, ne vključuje nobenih sprememb in ga obravnavajo sistemi, ki vključujejo vzporedno procesiranje.

Slabosti razdeli in vladaj

• Ker je večina njegovih algoritmov zasnovanih z vključevanjem rekurzije, je potrebno visoko upravljanje pomnilnika.
• Eksplicitni sklad lahko preveč porabi prostor.
• Lahko se celo zruši sistem, če je rekurzija izvedena rigorozno večja od sklada, ki je prisoten v CPE.