U ovom vodiču naučit ćete kako funkcionira algoritam podijeli i osvoji. Također ćemo usporediti pristup podijeliti i osvojiti s drugim pristupima za rješavanje rekurzivnog problema.
Podijeli pa vladaj algoritam je strategija rješavanja veliki problem
- razbijanje problema na manje podprobleme
- rješavanje potproblema i
- kombinirajući ih da bi se dobio željeni izlaz.
Da bi se koristio algoritam podijeli i osvoji, koristi se rekurzija . Saznajte o rekurziji na različitim programskim jezicima:
- Rekurzija na Javi
- Rekurzija u Pythonu
- Rekurzija u C ++
Kako funkcioniraju algoritmi za podjelu i osvajanje?
Ovdje su navedeni koraci:
- Podijeli : podijeli zadani problem na pod-probleme pomoću rekurzije.
- Osvajanje : Riješite manje pod-probleme rekurzivno. Ako je potproblem dovoljno mali, riješite ga izravno.
- Kombiniranje: Kombinirajte rješenja potproblema koji su dio rekurzivnog postupka da biste riješili stvarni problem.
Shvatimo ovaj koncept uz pomoć primjera.
Ovdje ćemo sortirati niz koristeći pristup podijeli i osvoji (tj. Spajanje sortiraj).
- Neka zadati niz bude: Niz
za sortiranje spajanjem - Podijelite niz na dvije polovice.
Podijelite niz u dva poddjela
Ponovno podijelite svaki poddio rekurzivno u dvije polovice dok ne dobijete pojedinačne elemente.
Podijelite niz na manje dijelove - Sada kombinirajte pojedinačne elemente na sortirani način. Ovdje osvajajte i kombinirajte korake jedan uz drugi.
Kombinirajte dijelove
Složenost vremena
Složenost algoritma "podijeli i osvoji" izračunava se pomoću glavnog teorema.
T (n) = aT (n / b) + f (n), gdje je, n = veličina ulaza a = broj potproblema u rekurziji n / b = veličina svakog potproblema. Pretpostavlja se da svi podproblemi imaju istu veličinu. f (n) = trošak posla obavljenog izvan rekurzivnog poziva, koji uključuje trošak podjele problema i trošak spajanja rješenja
Uzmimo primjer kako bismo pronašli vremensku složenost rekurzivnog problema.
Za sortiranje spajanja, jednadžba se može zapisati kao:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Gdje je, a = 2 (svaki put je problem podijeljen u 2 potproblema) n / b = n / 2 (veličina svakog pod problema je polovica ulaza) f (n) = vrijeme potrebno za podjelu problema i spajanje potproblema T (n / 2) = O (n log n) (Da biste to razumjeli, pogledajte glavni teorem.) Sada je T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Podijeli i osvoji protiv dinamičnog pristupa
Pristup podijeli i osvoji osvoji problem dijeli na manje potprobleme; ti se podproblemi dalje rješavaju rekurzivno. Rezultat svakog potproblema nije pohranjen za buduću referencu, dok se u dinamičkom pristupu rezultat svakog podproblema pohranjuje za buduću referencu.
Koristite pristup podijeli i osvoji kada isti podproblem nije riješen više puta. Upotrijebite dinamički pristup kada će se rezultat potproblema u budućnosti koristiti više puta.
Razumijemo to na primjeru. Pretpostavimo da pokušavamo pronaći Fibonaccijevu seriju. Zatim,
Pristup podijeli i osvoji:
fib (n) Ako je n <2, vrati 1 Else, vrati f (n - 1) + f (n -2)
Dinamički pristup:
mem = () fib (n) Ako je n u mem: vratiti mem (n) else, Ako je n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f povratak f
U dinamičkom pristupu mem pohranjuje rezultat svakog potproblema.
Prednosti algoritma podijeli i osvoji
- Složenost množenja dviju matrica korištenjem naivne metode je O (n 3 ), dok je upotreba pristupa podijeli i osvoji (tj. Množenje Strassenove matrice) O (n 2,8074 ). Ovaj pristup također pojednostavljuje i druge probleme, poput Hanojskog tornja.
- Ovaj je pristup prikladan za višeprocesorske sustave.
- Učinkovito koristi memorijske predmemorije.
Podijeli i osvoji programe
- Binarno pretraživanje
- Spoji sortiranje
- Brzo sortiranje
- Množenje Strassenove matrice
- Karatsuba algoritam
