V tomto tutoriálu se dozvíte, jak funguje algoritmus rozdělení a dobývání. Rovněž porovnáme přístup rozděl a panuj s jinými přístupy k řešení rekurzivního problému.
Rozděl a panuj je strategií pro řešení velkého problému
- rozdělení problému na menší dílčí problémy
- řešení dílčích problémů a
- jejich kombinací získáte požadovaný výstup.
K použití algoritmu rozděl a panuj se používá rekurze . Další informace o rekurzi v různých programovacích jazycích:
- Rekurze v Javě
- Rekurze v Pythonu
- Rekurze v C ++
Jak fungují algoritmy rozdělení a dobývání?
Jedná se o tyto kroky:
- Rozdělit : Rozdělte daný problém na dílčí problémy pomocí rekurze.
- Dobýt : Řešte menší dílčí problémy rekurzivně. Pokud je dílčí problém dostatečně malý, vyřešte ho přímo.
- Kombinovat: Kombinujte řešení dílčích problémů, které jsou součástí rekurzivního procesu, k vyřešení skutečného problému.
Pochopme tento koncept pomocí příkladu.
Zde budeme řadit pole pomocí přístupu rozděl a panuj (tj. Sloučit řazení).
- Nechť dané pole je:
Pole pro sloučení - Rozdělte pole na dvě poloviny.
Rozdělte pole na dvě podčásti
Znovu rozdělte každou podčást rekurzivně na dvě poloviny, dokud nezískáte jednotlivé prvky.
Rozdělte pole na menší části - Nyní jednotlivé prvky kombinujte tříděným způsobem. Tady dobývejte a kombinujte kroky vedle sebe.
Zkombinujte části
Časová složitost
Složitost algoritmu rozděl a panuj se vypočítá pomocí hlavní věty.
T (n) = aT (n / b) + f (n), kde, n = velikost vstupu a = počet dílčích problémů v rekurzi n / b = velikost každého dílčího problému. Předpokládá se, že všechny dílčí problémy mají stejnou velikost. f (n) = náklady na práci provedenou mimo rekurzivní volání, která zahrnuje náklady na rozdělení problému a náklady na sloučení řešení
Vezměme si příklad, abychom našli časovou složitost rekurzivního problému.
Pro sloučení lze rovnici zapsat jako:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Kde a = 2 (pokaždé je problém rozdělen na 2 dílčí problémy) n / b = n / 2 (velikost každého dílčího problému je polovina vstupu) f (n) = čas potřebný k rozdělení problému a sloučení dílčích problémů T (n / 2) = O (n log n) (Chcete-li tomu porozumět, podívejte se na hlavní věta.) Nyní T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Dynamický přístup Divide and Conquer Vs
Přístup rozděl a panuj rozděluje problém na menší dílčí problémy; tyto dílčí problémy jsou dále řešeny rekurzivně. Výsledek každého dílčího problému není uložen pro budoucí použití, zatímco v dynamickém přístupu je výsledek každého dílčího problému uložen pro budoucí použití.
Pokud není vyřešen stejný dílčí problém vícekrát, použijte přístup rozděl a panuj. Pokud má být v budoucnu výsledek dílčího problému použit vícekrát, použijte dynamický přístup.
Pochopme to na příkladu. Předpokládejme, že se snažíme najít sérii Fibonacci. Pak,
Přístup Divide and Conquer:
fib (n) Pokud n <2, návrat 1 Jinak, návrat f (n - 1) + f (n -2)
Dynamický přístup:
mem = () fib (n) If n in mem: return mem (n) else, If n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f návrat f
V dynamickém přístupu ukládá mem výsledek každého dílčího problému.
Výhody algoritmu Divide and Conquer
- Složitost pro násobení dvou matic pomocí naivní metody je O (n 3 ), zatímco použití přístupu rozděl a panuj (tj. Strassenova maticová multiplikace) je O (n 2,8074 ). Tento přístup také zjednodušuje další problémy, například Hanojskou věž.
- Tento přístup je vhodný pro systémy s více procesy.
- Efektivně využívá mezipaměti paměti.
Rozdělujte a dobývejte aplikace
- Binární vyhledávání
- Sloučit třídění
- Rychlé třídění
- Strassenovo násobení matice
- Karatsuba Algorithm
