INF.04Algorytmika i Struktury Danych
Paradygmat Dziel i Zwyciężaj (Divide and Conquer)
Wiodąca technika projektowania algorytmów polegająca na rekurencyjnym podziale problemu na mniejsze podproblemy tego samego typu, ich rozwiązaniu i scaleniu wyników.
Trzy kroki paradygmatu Dziel i Zwyciężaj:
- Dziel (Divide): Podział głównego problemu na mniejsze, niezależne podproblemy tego samego typu.
- Zwyciężaj (Conquer): Rekurencyjne rozwiązanie podproblemów. Gdy podproblem staje się dostatecznie mały (przypadek bazowy), rozwiązuje się go bezpośrednio.
- Połącz / Scalaj (Combine): Złożenie rozwiązań cząstkowych w ostateczny wynik problemu pierwotnego.
Klasyczne przykłady algorytmów typu Dziel i Zwyciężaj:
- Wyszukiwanie binarne (Binary Search): Podział posortowanej tablicy na pół w każdym kroku (O(log n)).
- Sortowanie przez scalanie (Merge Sort): Dzielenie tablicy na połowy, sortowanie ich i scalanie (O(n log n)).
- Sortowanie szybkie (Quick Sort): Podział elementów względem elementu osiowego (pivot).
- Algorytm Strassena: Szybkie mnożenie macierzy.
- Problem Wież z Hanoi.
Pułapki na egzaminie INF.04:
- Do algorytmów realizujących strategię Dziel i Zwyciężaj należą m.in. Merge Sort, Quick Sort oraz Wyszukiwanie Binarne.
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Paradygmat Dziel i Zwyciężaj (Divide and Conquer) lub rozpocznij trening.