Podijeli pa vladaj je algoritamski obrazac. U algoritamskim metodama, dizajn je uzeti spor na velikom ulazu, razbiti ulaz na manje dijelove, odlučiti o problemu na svakom od malih dijelova, a zatim spojiti rješenja po dijelovima u globalno rješenje. Ovaj mehanizam rješavanja problema naziva se strategija zavadi i vladaj.

Algoritam Podijeli pa vladaj sastoji se od spora koji koristi sljedeća tri koraka.

Podijelitiizvorni problem u skup podproblema.Osvojiti:Riješite svaki podproblem pojedinačno, rekurzivno.Kombinirati:Sastavite rješenja podproblema kako biste dobili rješenje cijelog problema.

Općenito, možemo pratiti zavadi-pa-vladaj pristup u procesu od tri koraka.

Primjeri: Specifični računalni algoritmi temelje se na pristupu Podijeli i vladaj:

1. Maksimalni i minimalni problem
2. Binarno pretraživanje
3. Sortiranje (sortiranje spajanjem, brzo sortiranje)
4. Hanojski toranj.

Osnove strategije Podijeli i vladaj:

Dva su temelja strategije Podijeli i vladaj:

1. Relacijska formula
2. Stanje zaustavljanja

1. Relacijska formula: To je formula koju generiramo iz dane tehnike. Nakon generiranja formule primjenjujemo D&C strategiju, tj. rekurzivno rastavljamo problem i rješavamo pokvarene podprobleme.

2. Uvjet zaustavljanja: Kada rješavamo problem korištenjem strategije Podijeli i vladaj, tada moramo znati koliko vremena trebamo primjenjivati ​​Zavadi i vladaj. Dakle, uvjet u kojem je potrebno zaustaviti naše korake rekurzije D&C-a naziva se Uvjet zaustavljanja.

Primjene pristupa Podijeli pa vladaj:

Sljedeći algoritmi temelje se na konceptu tehnike Podijeli pa vladaj:

Binarno pretraživanje:Binarni algoritam pretraživanja je algoritam pretraživanja koji se također naziva poluintervalnim pretraživanjem ili logaritamskim pretraživanjem. Djeluje uspoređujući ciljnu vrijednost sa srednjim elementom koji postoji u sortiranom nizu. Nakon usporedbe, ako se vrijednost razlikuje, tada će se polovica koja ne može sadržavati cilj na kraju eliminirati, nakon čega slijedi nastavak pretraživanja na drugoj polovici. Ponovno ćemo razmotriti srednji element i usporediti ga s ciljnom vrijednošću. Proces se ponavlja sve dok se ciljna vrijednost ne postigne. Ako smo nakon završetka pretrage ustanovili da je druga polovica prazna, tada se može zaključiti da meta nije prisutna u nizu.Brzo sortiranje:To je najučinkovitiji algoritam sortiranja, koji je također poznat kao sortiranje particijom-razmjenom. Započinje odabirom zaokretne vrijednosti iz niza nakon čega slijedi dijeljenje ostatka elemenata niza u dva podniza. Podjela je napravljena usporedbom svakog od elemenata sa pivot vrijednošću. Uspoređuje ima li element veću ili manju vrijednost od stožerne točke, a zatim sortira nizove rekurzivno.Spoji sortiraj:To je algoritam za sortiranje koji sortira niz usporedbom. Započinje dijeljenjem niza u podnizove, a zatim rekurzivno sortira svaki od njih. Nakon što je sortiranje završeno, ponovno ih spaja.Najbliži par točaka:To je problem računalne geometrije. Ovaj algoritam naglašava pronalaženje najbližeg para točaka u metričkom prostoru, danih n točaka, tako da udaljenost između para točaka treba biti minimalna.Strassenov algoritam:To je algoritam za množenje matrice, koji je dobio ime po Volkeru Strassenu. Dokazao se da je mnogo brži od tradicionalnog algoritma kada radi na velikim matricama.Cooley-Tukeyjev algoritam brze Fourierove transformacije (FFT):Algoritam za brzu Fourierovu transformaciju nazvan je po J. W. Cooleyu i Johnu Turkeyu. Slijedi pristup Podijeli pa vladaj i nameće složenost O(nlogn).Karatsuba algoritam za brzo množenje:To je jedan od najbržih algoritama tradicionalnog množenja, izumio ga je Anatolij Karatsuba kasnih 1960., a objavljen je 1962. Množi dva n-znamenkasta broja na takav način reducirajući ih na najviše jednoznamenkasti.

Prednosti Podijeli pa vladaj

• Podijeli pa vladaj teži uspješnom rješavanju jednog od najvećih problema, kao što je toranj u Hanoju, matematička zagonetka. Izazovno je rješavati komplicirane probleme za koje nemate osnovnu ideju, ali uz pomoć pristupa podijeli pa vladaj, smanjio je napor jer radi na dijeljenju glavnog problema na dvije polovice i zatim ih rješava rekurzivno. Ovaj algoritam je puno brži od ostalih algoritama.
• Učinkovito koristi predmemoriju bez zauzimanja puno prostora jer rješava jednostavne podprobleme unutar predmemorije umjesto pristupa sporijoj glavnoj memoriji.
• Vještija je od svoje slične tehnike Brute Force.
• Budući da ovi algoritmi sprječavaju paralelizam, on ne uključuje nikakve izmjene i njime upravljaju sustavi koji uključuju paralelnu obradu.

Nedostaci Zavadi pa vladaj

• Budući da je većina njegovih algoritama dizajnirana uključivanjem rekurzije, potrebno je visoko upravljanje memorijom.
• Eksplicitni stog može pretjerano koristiti prostor.
• Može čak i srušiti sustav ako se rekurzija izvodi rigorozno više od stoga prisutnog u CPU-u.