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.

Wykorzystanie

Omawiana metoda wykorzystywana jest między innymi w algorytmach:

• wyszukiwania binarnegoPiVb7f8s2wyszukiwania binarnego,

• sortowania przez scalaniePNHdnGJ4Isortowania przez scalanie,

• znajdowania w ciągu największego i najmniejszego elementu jednocześnieP38l9ymrFznajdowania w ciągu największego i najmniejszego elementu jednocześnie,

• sortowania szybkiegoPpzx1Yyemsortowania szybkiego.

Ciekawostka

R1QrvqS2N7NLr1

Zdjęcie przedstawia rzeźbę w kolorze jasnobeżowym przedstawiającą głowę i szyję Filipa drugiego Macedońskiego. Mężczyzna posiada kręcone, krótkie włosy, krótki zarost – brodę i wąsy, prosty nos i niewielkie oczy, Rzeźba zwrócona jest przodem do odbiorcy.

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 $O\left({\log }_{2}n\right)$. 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:

[1,2,5,9,12,15,27,50,94,100]

• 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:

[15,27,50,94,100]

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:

[15,27,50]

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:

funkcja wyszukiwanie_binarne(tablica, szukana, pocz, kon):
	jeżeli pocz > kon:
    	zwróć -1
    
    środek ← (pocz + kon) div 2
    jeżeli tablica[środek] = szukana:
    	zwróć środek
    w przeciwnym wypadku jeżeli tablica[środek] < szukana:
    	zwróć wyszukiwanie_binarne(tablica, szukana, środek + 1, kon)
    w przeciwnym wypadku:
    	zwróć wyszukiwanie binarne(tablica, szukana, pocz, środek - 1)

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:

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

Ilustracja przedstawia ciąg cyfr: 85924173.

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

Ilustracja przedstawia ciąg cyfr: 85924173. Biegną od niego w dół dwie strzałki – jedna w lewą stronę do ciągu cyfr 8592, druga w prawą stronę do ciągu cyfr 4173. Od ciągu cyfr 8592 biegną w dół dwie strzałki – biegnąca w lewą stronę do ciągu cyfr 85, biegnąca w prawą stronę do ciągu cyfr 92. Od ciągu cyfr 4173 biegną w dół dwie strzałki – biegnąca w lewą stronę do ciągu cyfr 41, biegnąca w prawą stronę do ciągu cyfr 73. Od ciągu cyfr 85 biegną w dół dwie strzałki - jedna w lewą stronę do cyfry 8, druga w prawą stronę do cyfry 5. Od ciągu cyfr 92 biegną w dół dwie strzałki - jedna w lewą stronę do cyfry 9, druga w prawą stronę do cyfry 2. Od ciągu cyfr 41 biegną w dół dwie strzałki - jedna w lewą stronę do cyfry 4, druga w prawą stronę do cyfry 1. Od ciągu cyfr 73 biegną w dół dwie strzałki - jedna w lewą stronę do cyfry 7, druga w prawą stronę do cyfry 3. Rysunek ten obejmuje z lewej strony klamra z podpisem: podziel.

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

Ilustracja przedstawia ciąg cyfr: 85924173. Biegną od niego w dół dwie strzałki – jedna w lewą stronę do ciągu cyfr 8592, druga w prawą stronę do ciągu cyfr 4173. Od ciągu cyfr 8592 biegną w dół dwie strzałki – biegnąca w lewą stronę do ciągu cyfr 85, biegnąca w prawą stronę do ciągu cyfr 92. Od ciągu cyfr 4173 biegną w dół dwie strzałki – biegnąca w lewą stronę do ciągu cyfr 41, biegnąca w prawą stronę do ciągu cyfr 73. Od ciągu cyfr 85 biegną w dół dwie strzałki - jedna w lewą stronę do cyfry 8, druga w prawą stronę do cyfry 5. Od ciągu cyfr 92 biegną w dół dwie strzałki - jedna w lewą stronę do cyfry 9, druga w prawą stronę do cyfry 2. Od ciągu cyfr 41 biegną w dół dwie strzałki - jedna w lewą stronę do cyfry 4, druga w prawą stronę do cyfry 1. Od ciągu cyfr 73 biegną w dół dwie strzałki - jedna w lewą stronę do cyfry 7, druga w prawą stronę do cyfry 3. Tą część rysunku obejmuje z lewej strony klamra z podpisem: podziel. Od cyfry 8 i 5 biegną w dół dwie strzałki, które łączą te cyfry w ciąg: 58. Od cyfry 9 i 2 biegną w dół dwie strzałki, które łączą te cyfry w ciąg: 29. Od cyfry 4 i 1 biegną w dół dwie strzałki, które łączą te cyfry w ciąg: 14. Od cyfry 7 i 3 biegną w dół dwie strzałki, które łączą te cyfry w ciąg: 37. Od ciągu cyfr 58 i 29 biegną w dół dwie strzałki, które łączą te cyfry w ciąg:2589, a od ciągu cyfr 14 i 37 biegną w dół dwie strzałki, które łączą te cyfry w ciąg:1347. Od ciągu cyfr 2589 i 1347 biegną w dół dwie strzałki, które łączą te cyfry w ciąg:123456789. Tą część rysunku obejmuje z lewej strony klamra z podpisem: scal.

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 $n$. 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 mamy${\log }_2\left(n\right)$ 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 $O(1)$, 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 $n$, zatem scalenie wszystkich części, które sumarycznie mają rozmiar $n$, zajmie $O(n)$ 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ą:

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 $n$, stąd scalenie wszystkich tablic zajmie $O(n)$. Gdy połączymy to z dzieleniem tablicy na połowy (złożoność logarytmiczna), otrzymamy złożoność $O\left(n·{\log }_{2}n\right)$.

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:

funkcja ZnajdzMinMax(tablica, pocz, kon)
    jeżeli kon = pocz
        min ← tablica[pocz]
        max ← tablica[pocz]
        zwróć (min, max)
    jeżeli kon = pocz + 1
        jeżeli tablica[pocz] <= tablica[kon]
            min ← tablica[pocz]
            max ← tablica[kon]
        w przeciwnym razie
            min ← tablica[kon]
            max ← tablica[pocz]
        zwróć (min, max)

    polowa ← (pocz + kon) // 2

    (minLewa, maxLewa) ← ZnajdzMinMax(tablica, pocz, polowa)
    (minPrawa, maxPrawa) ← ZnajdzMinMax(tablica, polowa + 1, kon)

    min ← min(minLewa, minPrawa)
    max ← max(maxLewa, maxPrawa)

    zwróć (min, max)

Słownik