Dziel i zwyciężaj
Słownik kwalifikacji INF.03 - Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych
Co to jest technika „dziel i zwyciężaj”?
Dziel i zwyciężaj to technika projektowania algorytmów polegająca na podziale dużego problemu na mniejsze podproblemy tego samego typu. Podproblemy są dzielone dalej, aż staną się na tyle proste, że można je rozwiązać bezpośrednio. Następnie wyniki częściowe są łączone w rozwiązanie całego problemu.
Główne etapy
- Podział problemu – problem główny dzieli się na mniejsze fragmenty.
- Rozwiązanie podproblemów – każdy fragment rozwiązuje się osobno, często rekurencyjnie.
- Scalenie wyników – wyniki podproblemów łączy się w wynik końcowy.
Przykłady algorytmów
Technikę „dziel i zwyciężaj” wykorzystują między innymi:
- sortowanie przez scalanie (merge sort),
- sortowanie szybkie (quick sort),
- wyszukiwanie binarne,
- niektóre algorytmy obliczania potęg,
- algorytmy przetwarzania dużych zbiorów danych.
Przykład: wyszukiwanie binarne
Wyszukiwanie binarne działa na posortowanej tablicy. Zamiast sprawdzać elementy po kolei, algorytm sprawdza środkowy element i odrzuca połowę danych.
Jeśli szukana wartość jest mniejsza od środkowej,
szukaj w lewej połowie.
Jeśli jest większa,
szukaj w prawej połowie.
Dzięki temu liczba sprawdzanych elementów bardzo szybko maleje.
Ważne na egzaminie
Jeśli w pytaniu pojawia się opis: „dzielenie problemu na mniejsze podproblemy, aż da się je łatwo rozwiązać”, poprawnym terminem jest dziel i zwyciężaj. Nie należy mylić tej techniki z konkretnymi algorytmami, np. sitem Eratostenesa lub sortowaniem przez wybór.