#4 Jak naprawdę mierzyć wydajność kodu (Wstęp do Big O)

Wyobraź sobie klasyczną sytuację: piszesz swój pierwszy algorytm wyszukiwania danych. Odpalasz program, mierzysz czas stoperem w telefonie albo za pomocą System.currentTimeMillis() w Javie i dumnie ogłaszasz: "Działa błyskawicznie! Zaledwie 0,02 sekundy!".

Potem wysyłasz ten sam kod koledze ze starszym laptopem, a on czeka na wynik… pół minuty. Kiedy z kolei wrzucacie na wejście bazę zawierającą nie 100, a 1 000 000 rekordów – program całkowicie zawiesza komputer.

Dlaczego tak się stało? Ponieważ mierzenie czasu w sekundach to największa pułapka początkującego programisty. W tym wpisie pokażę, jak profesjonaliści oceniają jakość kodu za pomocą notacji Big O (Wielkie O) oraz dlaczego czasem warto poświęcić pamięć RAM, by zyskać cenne ułamki sekund procesora.

1. Dlaczego stoper kłamie?

Pomiar czasu zegarowego zależy od dziesiątek czynników niezwiązanych z samym algorytmem:

Informatycy potrzebowali uniwersalnej miary, która będzie prawdziwa zarówno na smartfonie, domowym PC, jak i na superkomputerze. Zamiast liczyć sekundy, zaczęli liczyć operacje podstawowe (takie jak porównanie liczb, przypisanie zmiennej czy operacja dodawania) w relacji do wielkości danych wejściowych, którą oznaczamy literą $ n $.

Pytanie nie brzmi: "Ile sekund to zajmie?", lecz:
"Jak szybko spuchnie czas działania, gdy podwoimy lub zwiększymy tysiąckrotnie liczbę danych ($ n $)?"

2. Czym jest Notacja Big O?

Notacja Big O (Wielkie O) opisuje tempo wzrostu zapotrzebowania programu na czas lub pamięć wraz ze wzrostem wielkości danych wejściowych.

Co ważne: informatycy to pesymiści. Big O skupia się niemal zawsze na scenariuszu najgorszym (worst-case scenario). Jeśli szukasz kluczy w pokoju, Big O interesuje sytuacja, w której klucze leżą w ostatniej przeszukiwanej szufladzie lub w ogóle ich tam nie ma.

Przyjrzyjmy się trzem fundamentalnym klasom złożoności, z którymi będziesz spotykać się codziennie.

3. Święta Trójca: $ O(1), O(n) $ i $ O(n^{2}) $ 

$ O(1) $ - Złożoność stała: Błyskawica

W złożoności stałej liczba operacji nie zależy w ogóle od tego, jak duży jest zbiór danych.

Metafora z życia:
Wchodzisz do szatni z numerkiem 42. Idziesz prosto do szafki 42 i odbierasz kurtkę. Czy jeśli w szatni będzie 20 szafek, zajmie Ci to tyle samo czasu co wtedy, gdy w szatni będzie 20 000 szafek? Dokładnie tyle samo – znasz dokładny adres.

W kodzie to po prostu sięgnięcie do elementu tablicy po jego indeksie:

public static int pobierzElement(int[] tablica, int indeks) {
    return tablica[indeks]; // Dokładnie 1 operacja, niezależnie czy tablica ma 10 czy 10 000 000 elementów
}

$ O(n) $ - Złożoność liniowa: Wprost proporcjonalnie

Czas rośnie idealnie proporcjonalnie do liczby danych. Masz dwa razy więcej danych? Wykonasz dwa razy więcej operacji.

Metafora z życia:
Zgubiłeś w sali niepodpisany pendrive. Podchodzisz po kolei do każdego ucznia i pytasz: "Czy to Twój?". Jeśli w sali jest 10 osób, w najgorszym razie zapytasz 10 razy. Jeśli jesteś na auli z 600 osobami – zadasz pytanie 600 razy.

W kodzie to najczęściej pojedyncza pętla:

public static boolean czyZawieraWartosc(int[] liczby, int szukana) {
    for (int i = 0; i < liczby.length; i++) {
        if (liczby[i] == szukana) {
            return true;
        }
    }
    return false;
}

$ O(n^{2}) $ - Złożoność kwadratowa: Równia pochyła

Złożoność kwadratowa to moment, w którym algorytm zaczyna gwałtownie tracić na wydajności. Każde podwojenie danych oznacza czterokrotny wzrost liczby operacji!

Metafora z życia:
Zasada pierwszego dnia w szkole: każdy musi podejść do każdego innego ucznia, przedstawić się i podać rękę. Dla 4 osób to około 12–16 uścisków dłoni. Ale jeśli na apelu stoi 1000 uczniów i każdy ma przywitać się z każdym, mamy $ 1000 \times 1000 = 1  000  000 $ powitań! Apel potrwa do nocy.

W kodzie to zazwyczaj pętla wewnątrz pętli:

public static void wyswietlWszystkiePary(int[] liczby) {
    int n = liczby.length;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println(liczby[i] + " - " + liczby[j]);
        }
    }
}

4. Efekt skali: Zobacz różnicę

Spójrz na poniższe zestawienie. Wyobraź sobie, że jedna operacja zajmuje procesorowi 1 mikrosekundę:

Rozmiar danych ($ n $) $ O(1) $ $ O(n) $ $ O(n^{2}) $
$ n = 10 $ 1 operacja 10 operacji 100 operacji
$ n = 100 $ 1 operacja 100 operacji 10 000 operacji
$ n = 10  000 $ 1 operacja 10 000 operacji 100 000 000 operacji (~100 sekund)
$ n = 100  000 $ 1 operacja 100 000 operacji 10 000 000 000 operacji (~kilka godzin)

Rozwiązanie $ O(n^{2}) $ dla małych danych działa niewidocznie szybko, ale na danych produkcyjnych może położyć cały serwer.

5. Czas vs Pamięć – Wielki Kompromis

Wydajność to nie tylko czas procesora. Mamy jeszcze pamięć operacyjną (RAM). To prowadzi nas do pojęcia złożoności pamięciowej (Space Complexity).

W programowaniu rzadko dostajesz coś za darmo. Często musisz wybrać:

Życiowy przykład
Wyobraź sobie, że masz skomplikowany wzór, którego musisz użyć 20 razy podczas egzaminu.

  • Wariant 1 (Oszczędzasz pamięć, tracisz czas): Za każdym razem wyprowadzasz wzór od nowa w myślach. Twoja ławka i marginesy są puste, ale brakuje Ci czasu na skończenie testu.
  • Wariant 2 (Oszczędzasz czas, tracisz pamięć): Raz wyprowadzasz wzór i zapisujesz gotowy wynik na boku kartki (w podręcznym buforze/cache). Za każdym kolejnym razem tylko na niego zerkasz w ułamku sekundy ($ O(1) $ czasu), ale zużyłeś miejsce na papierze.

W komercyjnych aplikacjach ten mechanizm nazywamy buforowaniem (cachingiem) lub memoizacją.