W tym samouczku dowiesz się, jak działa algorytm dziel i rządź. Porównamy również podejście dziel i zwyciężaj z innymi podejściami do rozwiązania problemu rekurencyjnego.
Algorytm dziel i rządź jest strategia rozwiązywania duży problem
- podzielenie problemu na mniejsze podproblemy
- rozwiązywanie podproblemów i
- łącząc je, aby uzyskać pożądany efekt.
Aby użyć algorytmu dziel i zwyciężaj, używana jest rekurencja . Dowiedz się o rekurencji w różnych językach programowania:
- Rekursja w Javie
- Rekursja w Pythonie
- Rekurencja w C ++
Jak działają algorytmy dzielenia i zwyciężania?
Oto wymagane kroki:
- Podziel : podziel zadany problem na podproblemy za pomocą rekurencji.
- Conquer : rozwiązuj mniejsze podproblemy rekurencyjnie. Jeśli podproblem jest wystarczająco mały, rozwiąż go bezpośrednio.
- Połącz: połącz rozwiązania podproblemów, które są częścią procesu rekurencyjnego, aby rozwiązać rzeczywisty problem.
Zrozummy tę koncepcję na przykładzie.
Tutaj posortujemy tablicę stosując metodę dziel i zwyciężaj (tj. Sortowanie przez scalanie).
- Niech daną tablicą będzie:
Tablica do sortowania przez scalanie - Podziel tablicę na dwie połowy.
Podziel tablicę na dwie części.
Ponownie podziel rekursywnie każdą podczęść na dwie połowy, aż uzyskasz pojedyncze elementy.
Podziel tablicę na mniejsze części - Teraz połącz poszczególne elementy w posortowany sposób. Tutaj podbijaj i łącz kroki idą obok siebie.
Połącz części podrzędne
Złożoność czasowa
Złożoność algorytmu dziel i zwyciężaj jest obliczana za pomocą twierdzenia głównego.
T (n) = aT (n / b) + f (n), gdzie n = rozmiar wejścia a = liczba podproblemów w rekursji n / b = rozmiar każdego podproblemu. Zakłada się, że wszystkie podproblemy mają ten sam rozmiar. f (n) = koszt pracy wykonanej poza wywołaniem rekurencyjnym, który obejmuje koszt podzielenia problemu i koszt scalenia rozwiązań
Weźmy przykład, aby znaleźć złożoność czasową problemu rekurencyjnego.
W przypadku sortowania przez scalanie równanie można zapisać jako:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Gdzie, a = 2 (za każdym razem problem jest dzielony na 2 podproblemy) n / b = n / 2 (rozmiar każdego problemu podrzędnego to połowa danych wejściowych) f (n) = czas potrzebny na podzielenie problemu i połączenie podproblemów T (n / 2) = O (n log n) (Aby to zrozumieć, zapoznaj się z główne twierdzenie.) Teraz T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Dziel i zwyciężaj Vs Dynamiczne podejście
Podejście „dziel i rządź” dzieli problem na mniejsze podproblemy; te podproblemy są dalej rozwiązywane rekurencyjnie. Wynik każdego podproblemu nie jest przechowywany do wykorzystania w przyszłości, podczas gdy w podejściu dynamicznym wynik każdego podproblemu jest przechowywany do przyszłego odniesienia.
Użyj metody dziel i rządź, gdy ten sam podproblem nie jest rozwiązywany wiele razy. Skorzystaj z podejścia dynamicznego, jeśli wynik podproblemu ma być używany wielokrotnie w przyszłości.
Zrozummy to na przykładzie. Załóżmy, że próbujemy znaleźć szereg Fibonacciego. Następnie,
Podejście dziel i zwyciężaj:
fib (n) Jeśli n <2, return 1 Else, return f (n - 1) + f (n -2)
Dynamiczne podejście:
mem = () fib (n) Jeśli n in mem: return mem (n) else, If n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f powrót f
W podejściu dynamicznym mem przechowuje wynik każdego podproblemu.
Zalety algorytmu dziel i zwyciężaj
- Złożoność mnożenia dwóch macierzy metodą naiwną wynosi O (n 3 ), podczas gdy przy zastosowaniu podejścia dziel i zwyciężaj (tj. Mnożenia macierzy Strassena) wynosi O (n 2,8074 ). Takie podejście upraszcza również inne problemy, takie jak Wieża Hanoi.
- To podejście jest odpowiednie dla systemów wieloprocesowych.
- Efektywnie wykorzystuje pamięci podręczne.
Dziel i podbijaj aplikacje
- Wyszukiwanie binarne
- Merge Sort
- Szybkie sortowanie
- Mnożenie macierzy Strassena
- Algorytm Karatsuba
