Algorytmy Divide and Conquer

Wprowadzenie

Divide and Conquer (dziel i zwyciężaj) to fundamentalny paradygmat projektowania algorytmów, który polega na podziale problemu na mniejsze podproblemy, rozwiązaniu ich rekurencyjnie, a następnie połączeniu wyników w rozwiązanie całości.

Trzy główne etapy: 1. Divide (Dziel) - podziel problem na mniejsze podproblemy tego samego typu 2. Conquer (Zwyciężaj) - rozwiąż podproblemy rekurencyjnie (lub bezpośrednio jeśli są wystarczająco małe) 3. Combine (Łącz) - połącz rozwiązania podproblemów w rozwiązanie całości

Algorytmy Divide and Conquer są wykorzystywane w:

Sortowaniu (merge sort, quick sort)
Wyszukiwaniu (binary search)
Operacjach na macierzach (mnożenie Strassena)
Geometrii obliczeniowej (najbliższa para punktów)
Analizie danych (znajdowanie mediany)
Przetwarzaniu sygnałów (FFT - Fast Fourier Transform)

Schemat ogólny Divide and Conquer

Struktura algorytmu

Wyjście:

=== Struktura algorytmu Divide and Conquer ===

1. DIVIDE (Dziel):
   - Podziel problem na k podproblemów
   - Zazwyczaj k = 2 (podział binarny)
   - Wielkość podproblemu: n/k

2. CONQUER (Zwyciężaj):
   - Rozwiąż każdy podproblem rekurencyjnie
   - Przypadek bazowy: problem wystarczająco mały
   - Rozwiązanie bezpośrednie dla przypadku bazowego

3. COMBINE (Łącz):
   - Połącz rozwiązania podproblemów
   - Złożoność łączenia wpływa na całkowitą złożoność
   - Może być O(1), O(n), O(n log n) itp.

Równanie rekurencyjne:
  T(n) = k·T(n/k) + f(n)

gdzie:
  - k = liczba podproblemów
  - n/k = wielkość każdego podproblemu
  - f(n) = koszt dzielenia i łączenia

Przykład 1: Binary Search (wyszukiwanie binarne)

Implementacja z wizualizacją kroków

Wyjście:

=== Binary Search - przykład Divide and Conquer ===

Tablica: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
Szukana wartość: 15

============================================================

Rekurencja głębokość 0:
  Zakres: [0, 12]
  Fragment: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
  Środek: index=6, wartość=13
  13 < 15 → szukaj w prawej połowie

Rekurencja głębokość 1:
  Zakres: [7, 12]
  Fragment: [15, 17, 19, 21, 23, 25]
  Środek: index=9, wartość=19
  19 > 15 → szukaj w lewej połowie

Rekurencja głębokość 2:
  Zakres: [7, 8]
  Fragment: [15, 17]
  Środek: index=7, wartość=15
  → ZNALEZIONO na indeksie 7!

============================================================

Wynik: Znaleziono na indeksie 7

============================================================
ANALIZA DIVIDE AND CONQUER:
============================================================

DIVIDE:
  - Dzielimy tablicę na dwie połowy w każdym kroku
  - Punkt podziału: środek tablicy

CONQUER:
  - Wybieramy jedną połowę do dalszego przeszukania
  - Druga połowa jest odrzucana
  - Rekurencyjne wywołanie dla wybranej połowy

COMBINE:
  - Nie ma łączenia! (O(1))
  - Wynik jest zwracany bezpośrednio

Równanie rekurencyjne:
  T(n) = T(n/2) + O(1)
  Rozwiązanie: T(n) = O(log n)

Przykład 2: Merge Sort (sortowanie przez scalanie)

Implementacja z wizualizacją

Wyjście (fragment):

=== Merge Sort - klasyczny przykład D&C ===

Tablica początkowa: [38, 27, 43, 3, 9, 82, 10]

======================================================================

[Poziom 0] Sortowanie: [38, 27, 43, 3, 9, 82, 10]
  DIVIDE na:
    Lewa:  [38, 27, 43]
    Prawa: [3, 9, 82, 10]

[Poziom 1] Sortowanie: [38, 27, 43]
  DIVIDE na:
    Lewa:  [38]
    Prawa: [27, 43]

  [Poziom 2] Sortowanie: [38]
    → Bazowy (1 element): [38]

  [Poziom 2] Sortowanie: [27, 43]
    DIVIDE na:
      Lewa:  [27]
      Prawa: [43]

    [Poziom 3] Sortowanie: [27]
      → Bazowy (1 element): [27]

    [Poziom 3] Sortowanie: [43]
      → Bazowy (1 element): [43]

    COMBINE:
      [27] + [43]
      → [27, 43]

  COMBINE:
    [38] + [27, 43]
    → [27, 38, 43]

[... dalsze kroki ...]

======================================================================

Tablica posortowana: [3, 9, 10, 27, 38, 43, 82]

Przykład 3: Quick Sort

Implementacja z wyborem pivota

Wyjście:

=== Quick Sort - D&C z partycjonowaniem ===

Tablica początkowa: [10, 7, 8, 9, 1, 5]

======================================================================

[Poziom 0] Zakres [0:5]: [10, 7, 8, 9, 1, 5]
  Pivot: 5 (index 1)
  Po partycjonowaniu: [1, 5, 8, 9, 10, 7]
    Lewa:  [1]
    Prawa: [8, 9, 10, 7]

  [Poziom 1] Zakres [2:5]: [8, 9, 10, 7]
    Pivot: 7 (index 2)
    Po partycjonowaniu: [7, 9, 10, 8]
      Lewa:  []
      Prawa: [9, 10, 8]

    [Poziom 2] Zakres [3:5]: [9, 10, 8]
      Pivot: 8 (index 3)
      Po partycjonowaniu: [8, 10, 9]
        Lewa:  []
        Prawa: [10, 9]

      [Poziom 3] Zakres [4:5]: [10, 9]
        Pivot: 9 (index 4)
        Po partycjonowaniu: [9, 10]
          Lewa:  []
          Prawa: [10]

======================================================================

Tablica posortowana: [1, 5, 7, 8, 9, 10]

======================================================================
MERGE SORT vs QUICK SORT:
======================================================================

Aspekt                 Merge Sort                 Quick Sort
---------------------- -------------------------- --------------------------
DIVIDE                 Połowa array (O(1))        Partycjonowanie (O(n))
CONQUER                2 podproblemy n/2          2 podproblemy n/2
COMBINE                Scalanie (O(n))            Brak! (O(1))
Złożoność średnia      O(n log n)                 O(n log n)
Złożoność najgorsza    O(n log n)                 O(n²)
Pamięć dodatkowa       O(n)                       O(log n)
Stabilny?              TAK                        NIE
In-place?              NIE                        TAK

Problem maksymalnej podtablicy (Maximum Subarray)

Algorytm Kadane'a i podejście D&C

Wyjście:

=== Problem maksymalnej podtablicy ===

Tablica: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Rozwiązanie Divide and Conquer:
  Maksymalna suma: 6
  Podtablica: [4, -1, 2, 1]
  Indeksy: [3, 6]
  Złożoność: O(n log n)

Algorytm Kadane'a:
  Maksymalna suma: 6
  Podtablica: [4, -1, 2, 1]
  Indeksy: [3, 6]
  Złożoność: O(n)

======================================================================
ANALIZA D&C dla maksymalnej podtablicy:
======================================================================

DIVIDE:
  - Podziel tablicę na dwie połowy w środku

CONQUER:
  - Rekurencyjnie znajdź max w lewej połowie
  - Rekurencyjnie znajdź max w prawej połowie

COMBINE:
  - Znajdź max podtablicę przechodzącą przez środek
  - Wybierz najlepszą z trzech opcji:
    1. Max w lewej połowie
    2. Max w prawej połowie
    3. Max przechodząca przez środek

Równanie rekurencyjne:
  T(n) = 2·T(n/2) + O(n)
  Rozwiązanie: T(n) = O(n log n)

Uwaga: Algorytm Kadane'a jest lepszy (O(n)),
       ale D&C pokazuje elegancki podział problemu!

Mnożenie macierzy Strassena

Klasyczne vs Strassen

Wyjście:

=== Mnożenie macierzy Strassena ===

Macierz A:
  [1, 2, 3, 4]
  [5, 6, 7, 8]
  [9, 10, 11, 12]
  [13, 14, 15, 16]

Macierz B:
  [1, 0, 0, 1]
  [0, 1, 0, 1]
  [0, 0, 1, 1]
  [1, 1, 1, 0]

A × B (klasyczne):
  [5, 6, 7, 6]
  [13, 14, 15, 22]
  [21, 22, 23, 38]
  [29, 30, 31, 54]

A × B (Strassen):
  [5, 6, 7, 6]
  [13, 14, 15, 22]
  [21, 22, 23, 38]
  [29, 30, 31, 54]

Wyniki identyczne? True

======================================================================
ALGORYTM STRASSENA:
======================================================================

KLASYCZNE MNOŻENIE:
  C = A × B wymaga 8 mnożeń podmacierzy:
  C11 = A11×B11 + A12×B21
  C12 = A11×B12 + A12×B22
  C21 = A21×B11 + A22×B21
  C22 = A21×B12 + A22×B22
  Złożoność: T(n) = 8·T(n/2) + O(n²) = O(n³)

ALGORYTM STRASSENA:
  Używa tylko 7 mnożeń (zamiast 8):
  M1 = (A11 + A22) × (B11 + B22)
  M2 = (A21 + A22) × B11
  M3 = A11 × (B12 - B22)
  M4 = A22 × (B21 - B11)
  M5 = (A11 + A12) × B22
  M6 = (A21 - A11) × (B11 + B12)
  M7 = (A12 - A22) × (B21 + B22)

  Następnie:
  C11 = M1 + M4 - M5 + M7
  C12 = M3 + M5
  C21 = M2 + M4
  C22 = M1 + M3 - M2 + M6

  Złożoność: T(n) = 7·T(n/2) + O(n²) = O(n^2.807)

  Poprawa: O(n³) → O(n^2.807) ✓

Problem najbliższej pary punktów

Geometria obliczeniowa z D&C

Wyjście:

=== Problem najbliższej pary punktów ===

Punkty (10):
  P0: (2, 3)
  P1: (12, 30)
  P2: (40, 50)
  P3: (5, 1)
  P4: (12, 10)
  P5: (3, 4)
  P6: (20, 25)
  P7: (30, 15)
  P8: (25, 20)
  P9: (8, 12)

======================================================================

Brute Force (O(n²)):
  Najbliższa para: (2, 3) - (3, 4)
  Odległość: 1.4142

Divide and Conquer (O(n log n)):
  Najbliższa para: (2, 3) - (3, 4)
  Odległość: 1.4142

======================================================================
ANALIZA ALGORYTMU D&C:
======================================================================

DIVIDE:
  - Sortuj punkty po współrzędnej x
  - Podziel na dwie równe połowy pionową linią

CONQUER:
  - Rekurencyjnie znajdź najbliższą parę w lewej połowie
  - Rekurencyjnie znajdź najbliższą parę w prawej połowie
  - Niech δ = min(δ_left, δ_right)

COMBINE:
  - Sprawdź pary punktów przechodzące przez linię podziału
  - Wystarczy sprawdzić pasmo szerokości 2δ wokół linii
  - Dla każdego punktu sprawdź tylko 7 najbliższych sąsiadów!
  - (dowód matematyczny: w prostokącie δ×2δ max 8 punktów)

Równanie rekurencyjne:
  T(n) = 2·T(n/2) + O(n)
  Rozwiązanie: T(n) = O(n log n)

Master Theorem (Twierdzenie Master)

Analiza złożoności rekurencyjnych algorytmów D&C

Wyjście:

=== Master Theorem dla algorytmów D&C ===

RÓWNANIE REKURENCYJNE:
  T(n) = a·T(n/b) + f(n)

gdzie:
  - a = liczba podproblemów
  - n/b = wielkość każdego podproblemu
  - f(n) = koszt dzielenia i łączenia

======================================================================
TRZY PRZYPADKI MASTER THEOREM:
======================================================================

Niech c = log_b(a)  (wykładnik krytyczny)

PRZYPADEK 1: f(n) = O(n^d) gdzie d < c
  → Praca jest zdominowana przez liście drzewa rekurencji
  → T(n) = Θ(n^c) = Θ(n^(log_b a))
  Przykład: T(n) = 8·T(n/2) + O(n²)
            a=8, b=2, c=log₂(8)=3, f(n)=O(n²), d=2
            d < c → T(n) = Θ(n³)

PRZYPADEK 2: f(n) = Θ(n^c · log^k n) gdzie k ≥ 0
  → Praca jest równomiernie rozłożona na wszystkich poziomach
  → T(n) = Θ(n^c · log^(k+1) n)
  Przykład: T(n) = 2·T(n/2) + O(n)
            a=2, b=2, c=log₂(2)=1, f(n)=Θ(n), d=1
            d = c → T(n) = Θ(n log n)

PRZYPADEK 3: f(n) = Ω(n^d) gdzie d > c
  → Praca jest zdominowana przez korzeń (łączenie)
  → T(n) = Θ(f(n))
  Warunek regularności: a·f(n/b) ≤ k·f(n) dla k < 1
  Przykład: T(n) = 2·T(n/2) + O(n²)
            a=2, b=2, c=log₂(2)=1, f(n)=Θ(n²), d=2
            d > c → T(n) = Θ(n²)

======================================================================
PRZYKŁADY ALGORYTMÓW:
======================================================================

Algorytm:                 Binary Search
Rekurencja:               T(n) = 1·T(n/2) + O(1)
Parametry:                a=1, b=2, f(n)=O(1)
Wykładnik krytyczny:      c = log_2(1) = 0.000
Master Theorem:           Przypadek 2
Złożoność:                Θ(log n)

Algorytm:                 Merge Sort
Rekurencja:               T(n) = 2·T(n/2) + O(n)
Parametry:                a=2, b=2, f(n)=O(n)
Wykładnik krytyczny:      c = log_2(2) = 1.000
Master Theorem:           Przypadek 2
Złożoność:                Θ(n log n)

Algorytm:                 Klasyczne mnożenie macierzy (D&C)
Rekurencja:               T(n) = 8·T(n/2) + O(n²)
Parametry:                a=8, b=2, f(n)=O(n²)
Wykładnik krytyczny:      c = log_2(8) = 3.000
Master Theorem:           Przypadek 1
Złożoność:                Θ(n³)

Algorytm:                 Strassen (mnożenie macierzy)
Rekurencja:               T(n) = 7·T(n/2) + O(n²)
Parametry:                a=7, b=2, f(n)=O(n²)
Wykładnik krytyczny:      c = log_2(7) = 2.807
Master Theorem:           Przypadek 1
Złożoność:                Θ(n^2.807)

Algorytm:                 Karatsuba (mnożenie liczb)
Rekurencja:               T(n) = 3·T(n/2) + O(n)
Parametry:                a=3, b=2, f(n)=O(n)
Wykładnik krytyczny:      c = log_2(3) = 1.585
Master Theorem:           Przypadek 1
Złożoność:                Θ(n^1.585)

Złożoność obliczeniowa

Porównanie algorytmów D&C

Algorytm	Rekurencja	Master Theorem	Złożoność
Binary Search	T(n) = T(n/2) + O(1)	Przypadek 2	O(log n)
Merge Sort	T(n) = 2T(n/2) + O(n)	Przypadek 2	O(n log n)
Quick Sort	T(n) = 2T(n/2) + O(n)	Przypadek 2	O(n log n) średnio
Max Subarray (D&C)	T(n) = 2T(n/2) + O(n)	Przypadek 2	O(n log n)
Closest Pair	T(n) = 2T(n/2) + O(n)	Przypadek 2	O(n log n)
Strassen	T(n) = 7T(n/2) + O(n²)	Przypadek 1	O(n^2.807)
Karatsuba	T(n) = 3T(n/2) + O(n)	Przypadek 1	O(n^1.585)

Podsumowanie

Kiedy używać Divide and Conquer?

✅ Używaj D&C gdy: - Problem można podzielić na niezależne podproblemy - Podproblemy są tego samego typu co oryginalny problem - Rozwiązania podproblemów można efektywnie połączyć - Rekurencja prowadzi do lepszej złożoności niż iteracja

❌ NIE używaj D&C gdy: - Podproblemy nie są niezależne (użyj programowania dynamicznego) - Koszt łączenia jest zbyt wysoki - Problem ma prostsze rozwiązanie iteracyjne

Kluczowe koncepcje

Pojęcie	Opis
Divide	Podział problemu na mniejsze podproblemy
Conquer	Rozwiązanie podproblemów rekurencyjnie
Combine	Połączenie rozwiązań w rozwiązanie całości
Master Theorem	Narzędzie do analizy złożoności
Przypadek bazowy	Warunek zatrzymania rekurencji

Zalety i wady

✅ Zalety: - Eleganckie i intuicyjne rozwiązania - Często optymalna złożoność - Łatwe do zrównoleglenia - Naturalna implementacja rekurencyjna

❌ Wady: - Narzut wywołań rekurencyjnych - Może być trudne do debugowania - Czasem wymaga dodatkowej pamięci - Nie zawsze najszybsze w praktyce

Co dalej?

Po opanowaniu Divide and Conquer, następne tematy to:

Lekcja 78: Backtracking - Problem N-Hetmanów
Strategia backtrackingu
N-Queens problem
Pruning i optymalizacje
Zaawansowane D&C:
Fast Fourier Transform (FFT)
Algorytm Karatsuba (mnożenie wielkich liczb)
Quickselect (k-ty najmniejszy element)
Programowanie dynamiczne:
Różnice między D&C a DP
Memoizacja vs tabulacja
Optymalna podstruktura

Zadania praktyczne

Zadanie 1: Potęgowanie binarne

Zaimplementuj algorytm szybkiego potęgowania używając D&C. Oblicz a^n w czasie O(log n).

Zadanie 2: Median of Medians

Zaimplementuj algorytm Median of Medians do znajdowania k-tego najmniejszego elementu w O(n).

Zadanie 3: Convex Hull

Rozwiąż problem otoczki wypukłej (Convex Hull) używając D&C w czasie O(n log n).

Zadanie 4: Skyline Problem

Rozwiąż problem linii horyzontu (Skyline Problem) dla n budynków używając D&C.

Zadanie 5: Porównanie implementacji

Porównaj wydajność merge sort i quick sort dla różnych rozmiarów danych i różnych rozkładów (losowe, prawie posortowane, odwrotnie posortowane).

Następna lekcja: Backtracking - Problem N-Hetmanów