Notacja Big O — proste wyjaśnienie złożoności czasowej

Notacja Big O mówi, jak szybko może rosnąć czas działania algorytmu lub zużycie pamięci wraz ze wzrostem rozmiaru danych wejściowych. Jeśli pytasz: „Co się stanie, gdy problem stanie się dużo większy?”, Big O jest standardowym sposobem odpowiedzi.

Dlatego mówi się, że wyszukiwanie liniowe ma złożoność $O(n)$, a wyszukiwanie binarne $O(\log n)$. Celem nie jest przewidywanie dokładnej liczby milisekund na jednej maszynie. Celem jest porównywanie wzorców wzrostu.

Co oznacza Big O

Jeśli algorytm potrzebuje czasu $T(n)$ dla danych wejściowych o rozmiarze $n$, to

$$T(n) = O(f(n))$$

oznacza, że istnieją stałe $C > 0$ oraz $n_0$, takie że

$$T(n) \le C f(n) \quad \text{dla wszystkich } n \ge n_0$$

To znaczy, że Big O jest stwierdzeniem o górnym ograniczeniu wzrostu dla dostatecznie dużych danych wejściowych.

Mówiąc prościej: gdy $n$ jest już wystarczająco duże, czas działania nie rośnie szybciej niż stała wielokrotność $f(n)$.

Dlaczego Big O jest przydatne

Big O daje niezależny od maszyny sposób porównywania algorytmów. Program może działać szybciej na jednym laptopie niż na innym, ale trend wzrostu nadal ma znaczenie.

Ten trend jest najważniejszy wtedy, gdy rozmiar danych wejściowych bardzo się zmienia. Algorytm, który działa dobrze dla $100$ elementów, może stać się niepraktyczny dla $10^6$ elementów, jeśli jego tempo wzrostu jest słabe.

Najczęstsze złożoności czasowe w skrócie

• $O(1)$: ilość pracy pozostaje ograniczona, gdy $n$ rośnie.
• $O(\log n)$: ilość pracy rośnie powoli, często wtedy, gdy rozmiar problemu jest wielokrotnie zmniejszany.
• $O(n)$: ilość pracy rośnie w przybliżeniu proporcjonalnie do rozmiaru danych wejściowych.
• $O(n \log n)$: nieco więcej niż liniowo, często spotykane w wydajnych algorytmach sortowania.
• $O(n^2)$: ilość pracy rośnie jak kwadrat rozmiaru danych wejściowych, często z powodu zagnieżdżonych pętli nad tymi samymi danymi.

Te oznaczenia porównują wzrost, a nie dokładną szybkość. Algorytm $O(n)$ może być nadal wolniejszy od algorytmu $O(n^2)$ dla małych danych wejściowych, jeśli ma duże czynniki stałe.

Przykład: dlaczego wyszukiwanie liniowe ma złożoność $O(n)$

Załóżmy, że przeglądasz listę od lewej do prawej, szukając docelowej wartości. W najgorszym przypadku tej wartości nie ma albo znajduje się na samym końcu, więc może być konieczne sprawdzenie każdego elementu jeden raz.

Jeśli lista ma $n$ elementów, liczba sprawdzeń może wynosić najwyżej $n$. Dlatego złożoność czasowa w najgorszym przypadku to

$$O(n)$$

Praktyczny wniosek jest prosty: jeśli rozmiar listy się podwoi, to liczba sprawdzeń w najgorszym przypadku też może się w przybliżeniu podwoić. Właśnie taki wzorzec opisuje Big O.

Co Big O pomija

Big O celowo pomija czynniki stałe i wyrazy niższego rzędu przy porównywaniu wzrostu dla dużych danych wejściowych.

Na przykład, jeśli

$$T(n) = 3n + 2$$

to $T(n)$ nadal jest rzędu $O(n)$. Stała $3$ i dodatkowe $2$ mają znaczenie dla dokładnego czasu wykonania, ale nie zmieniają głównego wzorca wzrostu.

Nie oznacza to, że stałe nigdy nie mają znaczenia w praktyce. Oznacza to, że Big O odpowiada na węższe pytanie: jak koszt skaluje się, gdy $n$ staje się duże.

Typowe błędy związane z Big O

Błąd 1: Traktowanie Big O jako dokładnego czasu działania

$O(n)$ nie oznacza, że czas działania wynosi dokładnie $n$ kroków. Oznacza, że wzrost jest ograniczony z góry przez stałą wielokrotność $n$, gdy $n$ jest już wystarczająco duże.

Błąd 2: Pomijanie warunku dużego $n$

Formalna definicja musi być spełniona tylko dla wszystkich $n \ge n_0$. Big O dotyczy zachowania asymptotycznego, a nie każdego bardzo małego przypadku wejściowego.

Błąd 3: Zakładanie, że Big O zawsze oznacza typowy czas działania

W dyskusjach o algorytmach Big O często opisuje czas w najgorszym przypadku, ale jest to konwencja zależna od kontekstu. Złożoność średniego przypadku i najlepszego przypadku to inne pytania i powinny być wyraźnie oznaczane.

Błąd 4: Porównywanie algorytmów wyłącznie przez Big O

Big O jest ważne, ale zużycie pamięci, koszt implementacji i czynniki stałe także mogą mieć duże znaczenie w rzeczywistych systemach.

Gdzie spotyka się notację Big O

Big O pojawia się w informatyce, matematyce dyskretnej i analizie wydajności. Jest szczególnie przydatne przy porównywaniu algorytmów wyszukiwania, sortowania, przeszukiwania grafów i programowania dynamicznego.

Szerzej patrząc, używa się go wszędzie tam, gdzie liczy się to, jak proces się skaluje, a nie tylko jak zachowuje się dla jednego ustalonego rozmiaru.

Spróbuj podobnego przykładu

Weź prostą zagnieżdżoną pętlę, która przechodzi przez siatkę $n \times n$. Policz, ile razy wykonuje się operacja wewnętrzna. Jeśli całkowita ilość pracy rośnie jak $n^2$, masz konkretny przykład tego, dlaczego powtarzające się pętle nad tymi samymi danymi często prowadzą do zachowania typu $O(n^2)$.