Który szybszy? — porównywanie algorytmów
🎯 Po co Ci to?
Masz już cztery algorytmy wyszukiwania i sortowania, liczniki porównań z 🛠️ i intuicję z 1.5. Czas na jednostkę-zwornik: jak o kosztach mówić precyzyjnie i krótko. Bo „bąbelkowe wykonuje $\frac{n(n-1)}{2}$ porównań, a przy włączonej fladze na posortowanej liście $n-1$…" — to zdanie prawdziwe i niewygodne jak sweter z metką do środka. Informatycy całego świata skracają je do trzech znaków: $O(n^2)$. W rozszerzeniu nauczysz się tego języka na tyle, by czytać dokumentację bibliotek i zadania maturalne; w podstawie — ugruntujesz rzemiosło uczciwego porównywania.
✅ Czego się nauczysz
Po tej jednostce potrafisz:
- porównać algorytmy uczciwie: te same dane, trzy przypadki, liczniki operacji;
- rozpoznać typowe tempa wzrostu: stałe, logarytmiczne, liniowe, $n \log n$, kwadratowe, wykładnicze;
- (w rozszerzeniu) posługiwać się notacją $O$: co mówi, czego nie mówi i jak jej nie nadużywać.
📘 Wyjaśnienie
Uczciwe derby. Porównanie algorytmów to eksperyment — i jak każdy eksperyment, ma metodologię. Po pierwsze: te same dane dla wszystkich zawodników (losowa lista dla A i odwrócona dla B to nie wyścig, to ustawka). Po drugie: trzy przypadki (najlepszy/typowy/najgorszy) — bo jak widziałeś, wstawianie i bąbelkowe remisują w najgorszym, a różnią się o klasę w najlepszym. Po trzecie: licz operacje, nie sekundy — czas zależy od komputera, obciążenia i pogody; liczba porównań jest twarda i przenośna. (Pomiar czasu ma swoje miejsce — jako ostateczna weryfikacja — ale wnioskować ucz się z liczników.)
Zbierzmy wyniki działu w jedną tabelę (porównania, rząd wielkości):
| algorytm | najlepszy | typowy | najgorszy |
|---|---|---|---|
| wyszukiwanie liniowe | $1$ | $n/2$ | $n$ |
| wyszukiwanie binarne | $1$ | $\log_2 n$ | $\log_2 n$ |
| bąbelkowe (z flagą) | $n$ | $\sim n^2/2$ | $\sim n^2/2$ |
| wstawianie | $n$ | $\sim n^2/4$ | $\sim n^2/2$ |
Tempo wzrostu bije stałą. Kluczowa lekcja tej tabeli: na dużych danych o zwycięstwie decyduje kształt zależności od $n$, nie mnożniki. Algorytm robiący $100 \cdot n$ operacji pobije algorytm robiący $n^2/2$ dla każdego $n > 200$ — i dalej już tylko powiększa przewagę. Dlatego informatycy w pierwszym odruchu klasyfikują algorytmy po tempie wzrostu, a stałymi przejmują się w drugim.
[R] Notacja O. Skoro liczy się kształt — nazwijmy kształty.
📐 DEFINICJA — notacja $O$ („duże O"): zapis $O(f(n))$ oznacza klasę algorytmów, których liczba operacji rośnie co najwyżej tak szybko jak $f(n)$ — z dokładnością do stałego mnożnika i dla dostatecznie dużych $n$.
Po ludzku: „$O(n^2)$" czytaj: „rośnie jak kwadrat rozmiaru danych, plus minus stała". Zaniedbujemy mnożniki ($3n^2$ i $n^2/2$ to jedno $O(n^2)$) i wyrazy niższego rzędu ($n^2 + 5n + 100$ → $O(n^2)$), bo przy dużych $n$ rządzi najszybszy składnik. Czym NIE jest: obietnicą co do małych danych ani co do stałych. Algorytm $O(n)$ ze stałą 10 000 przegrywa z $O(n^2)$ na krótkich listach — notacja mówi, kto wygra w nieskończoności, nie kto wygra dziś po południu.
Kanoniczna drabina klas — od marzenia do koszmaru — z czasem dla $n = 10^6$ przy miliardzie operacji na sekundę:
| klasa | nazwa | przykład z tej książki | czas dla $n = 10^6$ |
|---|---|---|---|
| $O(1)$ | stała | wzór Gaussa (1.5), hasz (5.6) | natychmiast |
| $O(\log n)$ | logarytmiczna | binarne (6.2), Euklides (4.2), szybka potęga (4.6) | natychmiast |
| $O(n)$ | liniowa | liniowe (6.1), suma pętlą, sito ~ | 0,001 s |
| $O(n \log n)$ | liniowo-logarytmiczna | scalanie (6.6), dobre sortowania | 0,02 s |
| $O(n^2)$ | kwadratowa | bąbelkowe, wstawianie, naiwny wzorzec (5.2) | ~17 minut |
| $O(2^n)$ | wykładnicza | naiwny Fibonacci (4.3), atak siłowy (5.3) | wieki wszechświata (już dla $n = 60$) |
Tabelę czytaj jak mapę pogody: między $n \log n$ a $n^2$ przebiega front, za którym „duże dane" stają się nieosiągalne; między wielomianowymi a $2^n$ — granica świata możliwego. I trzy zawodowe zastrzeżenia, żeby nowy język Cię nie zwodził: (1) $O$ opisuje górne ograniczenie — mówiąc precyzyjnie „wstawianie jest $O(n^2)$" nie przeczysz, że na posortowanych danych działa liniowo; dlatego dopowiada się, o który przypadek chodzi. (2) Istnieją też symbole dolnego ograniczenia i dokładnego rzędu (Ω i Θ) — spotkasz je w literaturze; w tej książce mówimy „najgorszy przypadek $O(\dots)$", co załatwia sprawę uczciwie. (3) Za każdym $O$ stoi konkretna suma, którą umiesz policzyć — Gauss z 6.3 to nie folklor, to dowód. Notacja skraca rachunek; nie zastępuje go.
💭 Pomyśl: Programista mówi: „zoptymalizowałem funkcję — była $O(n^2)$, jest dwa razy szybsza". Co jest nie tak z tym zdaniem?
Sprawdź odpowiedź
„Dwa razy szybsza" to zmiana stałej — klasa została $O(n^2)$ (notacja właśnie stałe zaniedbuje!). To bywa cenna optymalizacja (patrz wartownik, 6.1) — ale nie zmienia wyroku dla dużych danych: podwojenie $n$ nadal czterokrotnie wydłuża czas, tylko od niższego progu. Prawdziwy przełom to zmiana klasy: $n^2 \to n \log n$ (inne sortowanie), $n \to \log n$ (posortuj i szukaj binarnie). Rozróżnienie „szybsza stała" vs „lepsza klasa" to pierwsza rzecz, o którą zapyta Cię każdy, komu zreferujesz optymalizację.
⚠️ Uwaga, pułapka
Mierzenie czasu zamiast liczenia operacji ma zdradliwe rafy: pierwszy pomiar bywa wolniejszy (rozgrzewka), system w tle kradnie czas, a dla małych $n$ szum przekracza sygnał. Jeśli mierzysz — mierz wielokrotnie, bierz minimum lub medianę, i zmieniaj $n$: podwój dane i patrz, co z czasem. Czas ×2 → liniowy; ×4 → kwadratowy; +stała → logarytmiczny. „Podwój i patrz" to poligonowy test tempa wzrostu, dostępny bez żadnej teorii.
🛠️ Teraz Ty
Masz liczniki z 6.3 i 6.4. Dołóż trzecią serię: dla $n$ = 100, 200, 400, 800 (listy losowe) zbierz porównania bąbelkowego i wstawiania; sprawdź regułę „podwój i patrz" (kwadratowe: ×4?). [R] Zapisz wnioski w notacji $O$ z zaznaczeniem przypadku. Bez komputera: uszereguj od najlepszej do najgorszej klasy: $O(n \log n)$, $O(2^n)$, $O(\log n)$, $O(n^2)$, $O(1)$, $O(n)$.
📐 Definicje tej lekcji
- Uczciwe porównanie — te same dane, trzy przypadki, liczniki operacji; czas tylko jako weryfikacja.
- [R] Notacja $O(f(n))$ — klasa tempa wzrostu: co najwyżej jak $f(n)$, bez stałych i wyrazów niższych; zawsze dopowiadaj przypadek.
📌 Najważniejsze w pigułce
- Kształt zależności od $n$ bije stałe mnożniki — klasyfikuj najpierw po tempie wzrostu.
- Drabina: $1 < \log n < n < n \log n < n^2 < 2^n$; między $n \log n$ a $n^2$ przebiega granica „dużych danych".
- „Dwa razy szybszy" ≠ „lepsza klasa"; podwój dane i patrz na czas — test tempa bez teorii.
🎒 Zadania
- Przypisz klasę [R] (lub opisowo tempo wzrostu) każdemu: (a) sprawdzenie parzystości, (b) suma listy, (c) test pierwszości z 4.1, (d) wypisanie wszystkich par elementów listy, (e) sprawdzenie wszystkich podzbiorów 30-elementowego zbioru.
Wskazówka i odpowiedź
(a) $O(1)$ — jedno mod. (b) $O(n)$. (c) $O(\sqrt{n})$ — klasa spoza kanonicznej drabiny, między $\log n$ a $n$ (drabina to najczęstsze szczeble, nie wszystkie). (d) $O(n^2)$ — par jest $\frac{n(n-1)}{2}$. (e) $O(2^n)$ — podzbiorów jest $2^{30} \approx 10^9$: na granicy wykonalności, a przy 60 elementach już za granicą. Zwróć uwagę na (c): rozmiar danych trzeba nazwać — dla liczby $n$ „rozmiarem" bywa jej wartość albo liczba cyfr, i klasy wychodzą różne. Precyzyjne „względem czego" to połowa poprawnej odpowiedzi.
- Sklep ma 10 000 produktów. Kasjerka skanuje kod i system znajduje cenę. Zaproponuj organizację danych i oszacuj koszt jednego skanowania dla: listy nieposortowanej, posortowanej, [R] tablicy haszującej (5.6). Które rozwiązanie wybierzesz?
Wskazówka i odpowiedź
Nieposortowana: liniowo, ~5000 porównań na skan. Posortowana po kodzie: binarnie, 14. Haszująca: praktycznie stała, 1–2 zajrzenia. Wybór: hasz — kody produktów to idealne klucze; porządek nie jest do niczego potrzebny (nikt nie pyta „jaki produkt jest alfabetycznie następny"). Ale gdyby system miał też wypisywać produkty po kolei (raporty!), porządek wraca do gry — struktura danych podąża za wszystkimi operacjami, które trzeba wspierać, nie za jedną. Pełna paleta struktur — dział 9.
- [R] Algorytm A: $1000n$ operacji; algorytm B: $n^2$. Dla jakich $n$ szybszy jest B? Co to mówi o zdaniu „algorytmy $O(n)$ są lepsze od $O(n^2)$"?
Wskazówka i odpowiedź
$n^2 < 1000n \iff n < 1000$. Dla list krótszych niż tysiąc wygrywa „gorszy" B! Zdanie o wyższości klas jest prawdziwe asymptotycznie (od pewnego $n$), a praktyka bywa małoskalowa — dokładnie dlatego biblioteki sortujące przełączają się na wstawianie ($O(n^2)$, malutka stała) dla krótkich fragmentów. Inżynieria to klasy i stałe: klasa wybiera strategię, stała rozstrzyga remisy i małe $n$.
🔍 Sprawdź, czy umiesz
- Przeprowadzić uczciwe derby dwóch algorytmów i zreferować wynik trzema przypadkami.
- Zastosować test „podwój i patrz" do nieznanego programu.
- [R] Przetłumaczyć rachunek kosztów na notację $O$ — i wskazać, czego ta notacja nie mówi.