Dziel i zwyciężaj — rama metody

🎯 Po co Ci to?

Poznałeś już trzy algorytmy, które robią w gruncie rzeczy to samo: scalanie (6.6), szybkie (6.7) i — w miniaturze — szybkie potęgowanie (4.6). Wszystkie tną problem na kawałki, rozwiązują kawałki rekurencyjnie i składają wynik. To nie zbieg okoliczności, tylko jedna metoda projektowania algorytmów o własnej nazwie i własnym schemacie — dziel i zwyciężaj. Nauczyć się jej jako ramy (a nie jako trzech osobnych sztuczek) to awans z „znam parę algorytmów" do „umiem projektować algorytmy". Rozszerzona podstawa wymaga tego wprost.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • rozpoznać trzy fazy metody dziel i zwyciężaj w dowolnym algorytmie;
  • wyjaśnić, skąd bierze się koszt (drzewo: poziomy × praca na poziomie);
  • zastosować schemat do nowego problemu (np. potęgowania, sumy, szukania max).

📘 Wyjaśnienie

📐 DEFINICJA — dziel i zwyciężaj: metoda rozwiązywania problemu w trzech fazach: PODZIEL problem na mniejsze podproblemy tego samego typu, ZWYCIĘŻAJ — rozwiąż każdy rekurencyjnie (aż do trywialnej bazy), POŁĄCZ rozwiązania podproblemów w rozwiązanie całości.

Po ludzku: pokrój, ugotuj kawałki osobno, złóż danie. Czym NIE jest: zwykłą dekompozycją (1.4). Dekompozycja tnie na różne podproblemy (gazetka: treści + oprawa + druk); dziel i zwyciężaj tnie na podproblemy tego samego typu, mniejsze — dlatego można je rozwiązać tą samą funkcją rekurencyjnie.

Zobacz ramę w znanych algorytmach — to ćwiczenie z rozpoznawania wzorca:

algorytm PODZIEL ZWYCIĘŻAJ POŁĄCZ
scalanie (6.6) na dwie połowy posortuj połowy scal (liniowo)
szybkie (6.7) względem osi posortuj grupy sklej (za darmo)
szybka potęga (4.6) wykładnik na pół policz $a^{n/2}$ podnieś do kwadratu
binarne (6.2) na dwie połowy szukaj w jednej — (druga odrzucona)

Zauważ, gdzie siedzi „ciężar": scalanie robi robotę w POŁĄCZ, szybkie — w PODZIEL, binarne w ogóle rezygnuje z jednej połowy (i dlatego jest logarytmiczne, nie $n \log n$). Ta sama rama, różne rozłożenie akcentów.

Skąd koszt? Dla metody, która dzieli problem rozmiaru $n$ na dwa o rozmiarze $n/2$ i łączy je liniową pracą (jak scalanie), rachunek z obrazka 6.6 uogólnia się: poziomów jest $\log_2 n$ (bo połowienie), pracy na poziom — łącznie $n$ (kawałki różne, suma stała), razem $n \log n$. Zmień „liniowe łączenie" na „stałe" (jak szybka potęga: po policzeniu połówki jedno mnożenie) — i praca na poziom jest stała, więc koszt spada do $\log n$. Zmień „dwie połowy" na „jedną" (binarne: druga odrzucona) — też $\log n$. Trzy klasy kosztu z jednego schematu, w zależności od tego, ile podproblemów i ile pracy przy łączeniu. To jest właśnie moc myślenia ramą: koszt czytasz z kształtu, bez liczenia od zera.

💭 Pomyśl: Zaprojektuj metodą dziel i zwyciężaj funkcję znajdującą maksimum listy. Jak wyglądają trzy fazy? Jaki koszt — i czy to lepiej niż jedno przejście pętlą?

Sprawdź odpowiedź

PODZIEL: lista na dwie połowy. ZWYCIĘŻAJ: znajdź max lewej i max prawej (rekurencyjnie; baza: lista jednoelementowa → ten element). POŁĄCZ: większy z dwóch maksimów. Koszt: $\log n$ poziomów × $n$ pracy przy łączeniu (na każdym poziomie łącznie $n$ porównań?… nie — na najniższym poziomie $n/2$ porównań, wyżej mniej) — sumarycznie $n-1$ porównań, czyli liniowo, tyle samo co pętla. Wniosek uczciwy: dziel i zwyciężaj nie zawsze wygrywa! Dla maksimum pętla jest równie dobra i prostsza (płytsza, bez stosu). Metoda błyszczy, gdy łączenie wykorzystuje posortowanie/strukturę podwyników (scalanie); gdy łączenie to zwykłe porównanie — pętla wystarcza. Znajomość ramy to także wiedza, kiedy jej nie używać.

⚠️ Uwaga, pułapka

Dziel i zwyciężaj opłaca się, gdy faza POŁĄCZ jest tańsza niż rozwiązanie problemu od zera — i gdy podproblemy są rozłączne (7.2!). Zastosowana do problemu z nachodzącymi podproblemami (jak Fibonacci) degeneruje się do wykładniczej katastrofy: to nie jest już „dziel i zwyciężaj", to „dziel i powtarzaj w kółko". Sygnał ostrzegawczy: jeśli Twoje podproblemy wołają o te same dane, potrzebujesz innej metody (programowanie dynamiczne, dział 8), nie dziel-i-zwyciężaj.

🛠️ Teraz Ty

Zaprojektuj i zaimplementuj metodą dziel i zwyciężaj: (a) sumę listy (PODZIEL na pół, ZWYCIĘŻAJ rekurencyjnie, POŁĄCZ = dodaj), (b) sprawdzenie, czy lista jest posortowana (POŁĄCZ = obie połowy posortowane ∧ styk lewa[-1] ≤ prawa[0]). Dla każdej wypisz trzy fazy i oszacuj koszt. Bez komputera: narysuj drzewo podziału sumy dla listy 8-elementowej.

📐 Definicje tej lekcji

  • Dziel i zwyciężaj — PODZIEL na mniejsze podproblemy tego samego typu → ZWYCIĘŻAJ rekurencyjnie → POŁĄCZ wyniki.
  • Koszt z kształtu — liczba podproblemów i praca przy łączeniu wyznaczają klasę ($\log n$ / $n \log n$ / …) bez liczenia od zera.

📌 Najważniejsze w pigułce

  • Jedna rama, wiele algorytmów: scalanie, szybkie, binarne, potęgowanie — różnią się tym, gdzie leży ciężar.
  • Koszt czytasz z kształtu: ile podproblemów × ile pracy przy łączeniu.
  • Metoda wymaga rozłącznych podproblemów i taniego łączenia; inaczej nie warto (albo wręcz katastrofa).

🎒 Zadania

  1. Dla każdego wskaż fazy PODZIEL/ZWYCIĘŻAJ/POŁĄCZ: (a) liczenie, ile razy wartość $x$ występuje w liście, (b) sprawdzenie, czy wszystkie elementy są równe.
Wskazówka i odpowiedź

(a) PODZIEL na pół; ZWYCIĘŻAJ: policz w lewej i prawej; POŁĄCZ: dodaj oba wyniki. Koszt liniowy (jak pętla — więc metoda nie wygrywa, tylko ilustruje ramę). (b) PODZIEL na pół; ZWYCIĘŻAJ: czy lewa jednorodna, czy prawa; POŁĄCZ: obie jednorodne ∧ lewa[0] == prawa[0]. Oba to przykłady, gdzie rama działa, ale nie daje przewagi nad pętlą — dobra lekcja pokory.

  1. Algorytm dzieli problem rozmiaru $n$ na trzy podproblemy rozmiaru $n/3$ i łączy je liniowo. Ile poziomów ma drzewo, jaka klasa kosztu? (Podpowiedź: teraz połowienie zamienia się na „trzeciowanie".)
Wskazówka i odpowiedź

Poziomów: ile razy dzielisz $n$ przez 3 do jedynki, czyli $\log_3 n$; praca na poziom łącznie $n$ (kawałki różne). Razem $n \log_3 n$ — a że $\log_3 n$ różni się od $\log_2 n$ tylko stałym czynnikiem, klasa to wciąż $O(n \log n)$! Podstawa logarytmu nie zmienia klasy (różni się o stałą — 6.5). Trzy kawałki zamiast dwóch to inna stała, nie inna liga.

  1. Kiedy metoda dziel i zwyciężaj daje realną przewagę nad prostą pętlą, a kiedy tylko „ładnie wygląda"? Sformułuj kryterium na podstawie przykładów z tej jednostki.
Wskazówka i odpowiedź

Przewaga jest realna, gdy faza POŁĄCZ wykorzystuje strukturę rozwiązań podproblemów, by osiągnąć coś taniej niż od zera — scalanie łączy dwie posortowane listy liniowo (a posortowanie od zera kosztowałoby więcej), szybka potęga z $a^{n/2}$ robi $a^n$ jednym mnożeniem. Gdy POŁĄCZ to zwykłe „dodaj/porównaj" bez zysku ze struktury (suma, maksimum, zliczanie) — metoda daje ten sam koszt co pętla, więc jest tylko ćwiczeniem. Kryterium: czy łączenie jest tańsze dzięki temu, że podproblemy są już rozwiązane? Tak — używaj; nie — iteruj.

🔍 Sprawdź, czy umiesz

  • Rozłożyć dowolny znany algorytm na PODZIEL/ZWYCIĘŻAJ/POŁĄCZ.
  • Oszacować koszt z kształtu drzewa (podproblemy × praca łączenia).
  • Rozstrzygnąć, czy dla danego problemu metoda daje przewagę, czy tylko elegancję.

Ucz się tej jednostki z asystentem