Metoda „dziel i zwyciężaj”

Strategię „dziel i zwyciężaj” można podzielić na trzy etapy:

  • Podziel problem na podproblemy.

  • Znajdź rozwiązanie dla każdego podproblemu.

  • Połącz rozwiązania podproblemów w rozwiązanie problemu głównego.

Należy pamiętać, że problem musi zostać podzielony na takie same lub bardzo do siebie podobne podproblemy (przynajmniej dwa). Ponadto zbiory danych, dla których rozwiązywane są podproblemy, powinny być niemal jednakowe i stanowić stałą część całego zbioru danych.

Ważne!

Należy zadbać o poprawne zaprojektowanie trzeciego kroku, polegającego na scalaniu rozwiązań. Jeżeli będzie on nieoptymalny, niekorzystnie wpłynie na końcową złożoność czasową algorytmu.

Wykorzystanie

Omawiana metoda wykorzystywana jest między innymi w algorytmach:

Ciekawostka
R1QrvqS2N7NLr1
Filip II Macedoński
Źródło: dostępny w internecie: commons.wikimedia.org [dostęp 21.07.2022], domena publiczna.

Zasada „dziel i rządź” (łac. divide et impera) mówi o tym, by wzniecać wewnętrzne konflikty wśród wrogów, np. między ludami na podbitych terenach, aby nimi rządzić.

Jej autorstwo przypisuje się Filipowi II Macedońskiemu, ojcu Aleksandra Wielkiego. Stosowali ją również Rzymianie (między innymi Juliusz Cezar).

Najeźdźcy podpisywali umowy z podbitymi ludami, które odtąd nazywano sprzymierzeńcami. Warunkiem paktów było to, że „sprzymierzeńcy” nie mogli zawierać umów między sobą, przez co prowincje nie mogły się zjednoczyć, aby pokonać Rzymian (czy też innych najeźdźców).

Przykłady zastosowania

Wyszukiwanie binarne

Wyszukiwanie binarne jest metodą szybkiego odnajdowania danych w posortowanym ciągu liczbowym. Jego czasowa złożoność obliczeniowa wynosi Olog2n. Czym jednak różni się ono od przeglądania tablicy metodą liniową element po elemencie i porównywania kolejnych liczb z poszukiwaną wartością?

W przypadku wyszukiwania binarnego wybierany jest element środkowy, względem którego ciąg jest dzielony na dwie części. Sprawdzamy, czy środkowy element jest poszukiwanym elementem. Jeśli nie, sprawdzamy, czy środkowy element jest większy, czy mniejszy od poszukiwanego elementu. Zależnie od tego wybieramy tylko lewy albo prawy podciąg, czyli działamy wyłącznie na jednej z wydzielonych części.

Zaprezentujmy działanie algorytmu na konkretnym przykładzie.

Dany jest następujący posortowany ciąg liczb całkowitych:

Linia 1. otwórz nawias kwadratowy 1 przecinek 2 przecinek 5 przecinek 9 przecinek 12 przecinek 15 przecinek 27 przecinek 50 przecinek 94 przecinek 100 zamknij nawias kwadratowy.
  • Lewą najmniejszą liczbą w tym ciągu jest liczba 1 (indeks 0).

  • Prawą najmniejszą liczbą w tym ciągu jest liczba 100 (indeks 9).

  • Poszukujemy pozycji liczby 27.

Chcemy wyznaczyć indeks elementu środkowego. Dodajemy do siebie indeksy lewej i prawej najmniejszej liczby w tym ciągu – otrzymujemy liczbę 9. Dzielimy ją całkowicie przez 2. Otrzymujemy wynik 4.

Pod indeksem 4 znajduje się liczba 12. Szukana liczba jest od niej większa, zatem wiemy, że liczby o indeksach 4 i mniejszych nie będą już brane pod uwagę.

Zostaje podciąg składający się z liczb większych od 12:

Linia 1. otwórz nawias kwadratowy 15 przecinek 27 przecinek 50 przecinek 94 przecinek 100 zamknij nawias kwadratowy.

Lewą najmniejszą liczbą w tym ciągu zostaje liczba o indeksie 5, czyli liczba 15.

Prawą najmniejszą liczbą w tym ciągu zostaje liczba 100 o indeksie 9.

Ponownie dodajemy do siebie wartości indeksów i dzielimy je całkowicie przez 2. Otrzymany wynik to 7.

Liczbą o indeksie równym 7 jest 50.

Poszukiwana liczba 27 jest od niej mniejsza, więc szukany element może się znajdować na miejscach o indeksach od 5 do 7.

Teraz analizowany podciąg wygląda następująco:

Linia 1. otwórz nawias kwadratowy 15 przecinek 27 przecinek 50 zamknij nawias kwadratowy.

Ponawiamy dodawanie do siebie indeksów. Tym razem środkiem zostaje liczba o indeksie 6. Jest to liczba 27, czyli poszukiwana wartość.

Zapiszmy analizowany algorytm za pomocą pseudokodu:

Linia 1. funkcja wyszukiwanie podkreślnik binarne otwórz nawias okrągły tablica przecinek szukana przecinek pocz przecinek kon zamknij nawias okrągły dwukropek. Linia 2. jeżeli pocz zamknij nawias ostrokątny kon dwukropek. Linia 3. zwróć minus 1. Linia 5. środek ← otwórz nawias okrągły pocz plus kon zamknij nawias okrągły div 2. Linia 6. jeżeli tablica otwórz nawias kwadratowy środek zamknij nawias kwadratowy znak równości szukana dwukropek. Linia 7. zwróć środek. Linia 8. w przeciwnym wypadku jeżeli tablica otwórz nawias kwadratowy środek zamknij nawias kwadratowy otwórz nawias ostrokątny szukana dwukropek. Linia 9. zwróć wyszukiwanie podkreślnik binarne otwórz nawias okrągły tablica przecinek szukana przecinek środek plus 1 przecinek kon zamknij nawias okrągły. Linia 10. w przeciwnym wypadku dwukropek. Linia 11. zwróć wyszukiwanie binarne otwórz nawias okrągły tablica przecinek szukana przecinek pocz przecinek środek minus 1 zamknij nawias okrągły.

Przedstawiliśmy rozwiązanie rekurencyjne, ale możliwe jest również zapisanie tego algorytmu w postaci iteracyjnej.

Więcej o wyszukiwaniu binarnym możesz przeczytać w e‑materiale Znajdowanie określonego elementu w zbiorzePiVb7f8s2Znajdowanie określonego elementu w zbiorze. Znajduje się tam również wersja iteracyjna algorytmu. Zachęcamy do porównania obydwu zapisów.

Złożoność czasowa

Aby zrozumieć złożoność czasową algorytmu wyszukiwania binarnego, warto przeanalizować jego działanie. W każdym kroku algorytmu dzielimy badaną tablicę na pół, odrzucając jedną połowę i kontynuując szukanie w drugiej.

Przykładowo, jeżeli tablica miałaby osiem elementów, to po pierwszym kroku analizowalibyśmy już tylko cztery elementy, po drugim dwa, a po trzecim mielibyśmy już do dyspozycji tylko jeden element.

Dla tablicy 16‑elementowej zawężenie wyszukiwania do jednego elementu zajęłoby cztery kroki.

Algorytm wykonuje logarytmiczną liczbę operacji w stosunku do liczby danych wejściowych. Jeżeli tablica ma n elementów, potrzebna liczba kroków wynosi log n, ponieważ w każdym kroku dzielimy tablicę na połowę.

Stąd złożoność czasowa algorytmu wyszukiwania binarnego wynosi:

Olog2n

Sortowanie przez scalanie

Przykładem wykorzystania metody „dziel i zwyciężaj” (uwaga: nie myl jej z zasadą „dziel i rządź”!) jest algorytm sortowania przez scalanie. Więcej na jego temat znajdziesz w e‑materiale Sortowanie przez scalaniePNHdnGJ4ISortowanie przez scalanie.

Naszym zadaniem jest posortowanie niemalejąco następującego zbioru danych:

RLTmWb8SCYT6w
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Najpierw należy podzielić tablicę na mniejsze, osobno sortowane tablice. W tym celu tablicę dzielimy na pół – jeżeli liczba elementów jest nieparzysta, pierwsza tablica będzie zawierała o jeden element więcej. Konieczne jest też wyznaczenie elementu środkowego, który stanowi podstawę podziału. Proces powtarzamy tak długo, aż uzyskamy tablice jednoelementowe. Jest to etap dzielenia (dziel).

RRkuvszKknRnB
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Wiemy, że tablica zawierająca jeden element już jest posortowana. Dzięki temu możemy scalić dwie tablice jednoelementowe i uzyskać kolejną posortowaną tablicę dwuelementową. Następnie scalamy dwie posortowane tablice dwuelementowe, aby uzyskać tablicę czteroelementową i tak dalej. Jest to etap scalania (zwyciężaj).

RhKadbMuJ45uU
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Szczegółowe omówienie sortowania przez scalanie oraz funkcji scal znajduje się w e‑materiale Sortowanie przez scalaniePNHdnGJ4ISortowanie przez scalanie.

Złożoność czasowa

Biorąc pod uwagę przedstawiony przykład zastosowania metody „dziel i zwyciężaj”, jakim jest sortowanie przez scalanie, przeanalizujemy teraz złożoność czasową algorytmu.

Załóżmy, że tablica, którą mamy posortować, ma rozmiar . W każdym kolejnym kroku algorytmu (czyli w każdym kolejnym wywołaniu rekurencyjnym funkcji) dzielimy ją na dwie części. W wypadku parzystej liczby elementów są to zawsze dwie równe części. W przypadku nieparzystej liczby elementów pierwsza część zawiera tylko o jeden element więcej od drugiej. Zatem dla n‑elementowej tablicy mamylog2n poziomów zagnieżdżenia funkcji. Jest to równocześnie złożoność czasowa tej operacji. Jest to etap „dziel”.

W każdym kroku szukamy indeksu, który stanowi połowę obecnego łańcucha. Ten krok wykonujemy w czasie , a zatem nie zwiększa on złożoności obliczeniowej.

Pod koniec algorytmu scalamy mniejsze części tablicy w jedną posortowaną. Oryginalna tablica ma rozmiar , zatem scalenie wszystkich części, które sumarycznie mają rozmiar , zajmie  czasu. Jest to część „zwyciężaj” omawianej metody.

Algorytm sortowania przez scalanie w każdym przypadku (zarówno pesymistycznym, jak i optymistycznym) ma następującą złożoność czasową:

On · log2n

Porównanie złożoności czasowych

W przypadku wyszukiwania binarnego jedynym wykonywanym działaniem jest dzielenie w każdym kroku tablicy na pół. Stąd złożoność czasowa tego algorytmu jest logarytmiczna. W przeciwieństwie do sortowania przez scalanie, już po wykonaniu kroku „dziel” z metody „dziel i zwyciężaj” mamy odpowiedź.

W sortowaniu przez scalanie, po podzieleniu tablic na połowy, należy je jeszcze scalić. Łączna długość tablicy wynosi , stąd scalenie wszystkich tablic zajmie . Gdy połączymy to z dzieleniem tablicy na połowy (złożoność logarytmiczna), otrzymamy złożoność On · log2n.

Algorytm jednoczesnego wyszukiwania minimum i maksimum

Przykładem algorytmu typu „dziel i zwyciężaj” jest algorytm równoczesnego wyszukiwania w zbiorze największej i najmniejszej wartościP38l9ymrFalgorytm równoczesnego wyszukiwania w zbiorze największej i najmniejszej wartości.

Algorytm jednoczesnego wyszukiwania wartości minimalnej i maksymalnej, który wykorzystuje strategię dziel i zwyciężaj, składa się z następujących kroków:

  1. Sprawdź rozmiar tablicy. Jeśli rozmiar wynosi 1, zwróć element jako minimum i maksimum.

  2. Podziel tablicę na dwie równe części.

  3. Rekurencyjnie wywołaj algorytm dla dwóch połówek tablicy.

  4. W wyniku wywołania rekurencyjnego otrzymasz wartości minimalne i maksymalne dla każdej połówki.

  5. Porównaj wartości minimalne i maksymalne dla obu połówek i zwróć wyniki.

  6. Porównaj wartości minimalne i maksymalne z obu połówek i wybierz mniejszą wartość jako minimum całej tablicy oraz większą wartość jako maksimum całej tablicy.

  7. Zwróć minimum i maksimum jako wynik.

Kroki 2‑5 są wykonywane rekurencyjnie dla każdej połówki tablicy aż do momentu, gdy rozmiar tablicy wynosi 1. W tym przypadku algorytm zwraca jedyny element tablicy jako zarówno minimum, jak i maksimum.

Algorytm wykorzystuje strategię „dziel i zwyciężaj”, dzieląc problem na mniejsze części. Następnie łączy wyniki z mniejszych problemów, aby uzyskać wynik dla całego problemu. W tym przypadku dzieli tablicę na dwie równe części, znajduje wartości minimalne i maksymalne dla każdej połowy, a następnie porównuje je, aby znaleźć wartości minimalne i maksymalne dla całej tablicy.

Pseudokod algorytmu:

Linia 1. funkcja ZnajdzMinMax otwórz nawias okrągły tablica przecinek pocz przecinek kon zamknij nawias okrągły. Linia 2. jeżeli kon znak równości pocz. Linia 3. min ← tablica otwórz nawias kwadratowy pocz zamknij nawias kwadratowy. Linia 4. max ← tablica otwórz nawias kwadratowy pocz zamknij nawias kwadratowy. Linia 5. zwróć otwórz nawias okrągły min przecinek max zamknij nawias okrągły. Linia 6. jeżeli kon znak równości pocz plus 1. Linia 7. jeżeli tablica otwórz nawias kwadratowy pocz zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości tablica otwórz nawias kwadratowy kon zamknij nawias kwadratowy. Linia 8. min ← tablica otwórz nawias kwadratowy pocz zamknij nawias kwadratowy. Linia 9. max ← tablica otwórz nawias kwadratowy kon zamknij nawias kwadratowy. Linia 10. w przeciwnym razie. Linia 11. min ← tablica otwórz nawias kwadratowy kon zamknij nawias kwadratowy. Linia 12. max ← tablica otwórz nawias kwadratowy pocz zamknij nawias kwadratowy. Linia 13. zwróć otwórz nawias okrągły min przecinek max zamknij nawias okrągły. Linia 15. polowa ← otwórz nawias okrągły pocz plus kon zamknij nawias okrągły prawy ukośnik prawy ukośnik 2. Linia 17. otwórz nawias okrągły minLewa przecinek maxLewa zamknij nawias okrągły ← ZnajdzMinMax otwórz nawias okrągły tablica przecinek pocz przecinek polowa zamknij nawias okrągły. Linia 18. otwórz nawias okrągły minPrawa przecinek maxPrawa zamknij nawias okrągły ← ZnajdzMinMax otwórz nawias okrągły tablica przecinek polowa plus 1 przecinek kon zamknij nawias okrągły. Linia 20. min ← min otwórz nawias okrągły minLewa przecinek minPrawa zamknij nawias okrągły. Linia 21. max ← max otwórz nawias okrągły maxLewa przecinek maxPrawa zamknij nawias okrągły. Linia 23. zwróć otwórz nawias okrągły min przecinek max zamknij nawias okrągły.

Słownik

iteracja
iteracja

(z łac. iteratio) powtarzanie w pętli tych samych instrukcji aż do spełnienia pewnego warunku

metoda „dziel i zwyciężaj”
metoda „dziel i zwyciężaj”

metoda polegająca na podzieleniu problemu na mniejsze, prostsze do rozwiązania podproblemy; po całkowitym rozbiciu problemu oraz rozwiązaniu podproblemów, łączymy je z powrotem w całość i rozwiązujemy cały problem

rekurencja
rekurencja

technika programowania polegająca na odwoływaniu się procedur lub funkcji do samych siebie, aż do momentu spełnienia warunku podstawowego

rozwiązanie naiwne
rozwiązanie naiwne

najprostsze, bezpośrednie rozwiązanie danego problemu, pozbawione jakichkolwiek usprawnień i optymalizacji, przez co zazwyczaj jest to rozwiązanie nieoptymalne; przykładami mogą być algorytmy, które sprawdzają wszystkie możliwe rozwiązania (podczas gdy wystarczyłoby sprawdzenie tylko części), przeszukują całe zbiory danych (podczas gdy wystarczyłoby tylko częściowe przeszukiwanie) itp.

sortowanie przez scalanie
sortowanie przez scalanie

jeden z algorytmów sortowania bazujący na metodzie „dziel i zwyciężaj”; możemy w nim wyróżnić dwa główne etapy:

  • podzielenie nieposortowanej listy na  list podrzędnych, z których każda zawiera jeden element;

  • łączenie kolejnych podlist, aby utworzyć nowe posortowane podlisty, aż pozostanie tylko jedna lista

wyszukiwanie binarne
wyszukiwanie binarne

metoda odnajdowania elementów w uporządkowanych zbiorach, polegająca na wielokrotnym dzieleniu przeszukiwanego zbioru na dwie równe części i porównywaniu wartości szukanej z elementem znajdującym się w środku dzielonego obszaru

złożoność czasowa
złożoność czasowa

czas niezbędny do rozwiązania określonego problemu, podawany zazwyczaj w liczbach operacji dominujących; złożoność czasowa zależy od ilości danych wejściowych