Dziel i zwyciężaj: potęgowanie, wyszukiwanie binarne, min i max

To jedna z najważniejszych technik projektowania algorytmów. Polega na trzech krokach: podziel problem na mniejsze podproblemy tego samego typu, rozwiąż je rekurencyjnie (aż do trywialnego przypadku bazowego), a następnie połącz wyniki cząstkowe w rozwiązanie całościowe. Ta technika często pozwala zejść ze złożoności O(n) do O(log n), albo z O(n²) do O(n log n).

2. Szybkie potęgowanie — O(log n) zamiast O(n)

Naiwne obliczenie aⁿ wymaga n mnożeń. Zauważmy jednak, że: jeśli n jest parzyste, aⁿ = (aⁿᐛ²)², a jeśli n jest nieparzyste, aⁿ = a × aⁿ⁻¹. Każde wywołanie zmniejsza wykładnik o połowę — stąd złożoność O(log n).

def szybka_potega(a, n): if n == 0: return 1 if n % 2 == 0: p = szybka_potega(a, n // 2) return p * p else: return a * szybka_potega(a, n - 1)

3. Wyszukiwanie binarne

Klasyczny przykład "dziel i zwyciężaj": w posortowanej tablicy porównujemy szukaną wartość ze środkowym elementem i odrzucamy połowę tablicy w każdym kroku.

def szukaj_binarnie(tab, x): lewy, prawy = 0, len(tab) - 1 while lewy <= prawy: srodek = (lewy + prawy) // 2 if tab[srodek] == x: return srodek elif tab[srodek] < x: lewy = srodek + 1 else: prawy = srodek - 1 return -1 # nie znaleziono

4. Jednoczesne wyszukiwanie minimum i maksimum

Naiwnie znalezienie min i max osobno wymaga 2n porównań. Metodą dziel i zwyciężaj można to zrobić w około 3n/2 porównań: dzielimy tablicę na połowy, rekurencyjnie znajdujemy (min, max) w każdej połowie, a następnie porównujemy wyniki cząstkowe (tylko 2 dodatkowe porównania na połączenie).

def min_max(tab, lewy, prawy): if lewy == prawy: return tab[lewy], tab[lewy] if prawy - lewy == 1: return min(tab[lewy], tab[prawy]), max(tab[lewy], tab[prawy]) srodek = (lewy + prawy) // 2 min1, max1 = min_max(tab, lewy, srodek) min2, max2 = min_max(tab, srodek + 1, prawy) return min(min1, min2), max(max1, max2)

5. Ćwiczenia praktyczne

Ćwiczenie 1 — zmodyfikuj szybkie potęgowanie

Napisz iteracyjną (bez rekurencji) wersję szybkiego potęgowania, korzystając z zapisu dwójkowego wykładnika n. Wskazówka: przechodzimy przez bity n od najmniej znaczącego, mnożąc wynik przez a za każdym razem, gdy bit jest równy 1, i podnosząc a do kwadratu w każdym kroku.

def szybka_potega_iter(a, n):
    wynik = 1
    while n > 0:
        if n % 2 == 1:
            wynik *= a
        a *= a
        n //= 2
    return wynik

Ćwiczenie 2 — policz porównania

Zmodyfikuj funkcję min_max tak, aby zliczając globalną liczbę wykonanych porównań, potwierdzić empirycznie, że dla n=1000 elementowej tablicy liczba porównań jest bliska 3n/2, a nie 2n.

Sprawdź wiedzę

1. Jaka jest złożoność szybkiego potęgowania metodą dziel i zwyciężaj?

O(n) O(log n) O(n²)

2. Ile w przybliżeniu porównań wymaga znalezienie min i max jednocześnie metodą dziel i zwyciężaj?

2n n² ~3n/2

3. Który warunek kończy wyszukiwanie binarne z wynikiem „nie znaleziono”?

lewy == prawy lewy > prawy srodek == 0

1. Idea metody "dziel i zwyciężaj"