Tempa wzrostu, nie absolutne koszty
Big O: Pomiar tempa wzrostu kosztów
Notacja Big O mierzy tempo wzrostu kosztu algorytmu — nie koszt absolutny.
Pytanie, na które odpowiada Big O: gdy rozmiar danych wejściowych N się podwoi, czy praca się podwoi? Czworokrotnie? Zostanie taka sama?
Litera 'O' oznacza 'rząd wielkości'. Wyrażenie w nawiasach opisuje kształt krzywej wzrostu.
Kluczowe klasy złożoności:
- O(1) — stała: koszt nie rośnie. Przykład: wyszukanie wartości po indeksie w tablicy. Niezależnie od tego, czy tablica ma 10 czy 10 milionów elementów, jedno wyszukanie to jedno wyszukanie.
- O(N) — liniowa: koszt rośnie z danymi wejściowymi. Przykład: przeczytanie każdego elementu na liście raz. Podwój listę, podwój odczyty.
- O(N²) — kwadratowa: koszt rośnie jako kwadrat danych wejściowych. Przykład: porównanie każdego elementu z każdym innym elementem. Podwój N, czworokrotnie wzrośnie praca.
Tabela porównania wzrostu:
| N | O(1) | O(N) | O(N²) |
|---|---|---|---|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10 000 |
| 1 000 | 1 | 1 000 | 1 000 000 |
Przy N=10 różnica wygląda na małą. Przy N=1 000 przepaść staje się ogromna.
Porównaj O(N) do O(N²)
Użyj tabeli porównania wzrostu powyżej.
Przy N=1 000: O(N) wymaga 1 000 operacji. O(N²) wymaga 1 000 000 operacji.
Jak struktura kodu ujawnia złożoność
Jak zidentyfikować Big O z kodu
Big O chowa się w kształcie twojego kodu. Cztery wzorce obejmują większość przypadków:
Jedna pętla przez N elementów: O(N)
# O(N): jeden przebieg przez listę
for item in list_of_n_items:
process(item)Zagnieżdżone pętle, każda przez N elementów: O(N²)
# O(N²): każdy element sparowany z każdym innym elementem
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)Wyszukiwanie w stałym czasie: O(1)
Dostęp do indeksu tablicy, wyszukiwanie w tabeli mieszającej — jeden krok niezależnie od rozmiaru.
Dziel i podbijaj (zmniejszanie problemu o połowę w każdym kroku): O(log N)
Wyszukiwanie binarne: każde sprawdzenie zmniejsza o połowę pozostałe elementy.
---
Ukryte O(N²): lista wewnątrz pętli
# Wygląda to jak O(N), ale to faktycznie O(N²)
visited = []
for item in list_of_n_items:
if item not in visited: # skanuje wszystkie elementy visited: O(N)
visited.append(item) # cała pętla: O(N²)Linia if item not in visited skanuje każdy element visited w każdej iteracji. Skanowanie listy kosztuje O(N). Pętla, która działa N razy, każda wykonując O(N) pracy: O(N) × O(N) = O(N²).
Ten wzorzec pojawia się w 1 000+ projektów open-source. Naprawa zajmuje jeden znak: zamień visited = [] na visited = set(). Sprawdzenie przynależności do zestawu kosztuje O(1), nie O(N). Jedna zmiana. Takie same wyniki. 1 000× szybciej przy N=1 000.
Klasyfikuj i napraw ten kod
Przeczytaj ten kod:
result = []
for name in student_names:
if name not in result:
result.append(name)Teoria spotyka praktykę
Big O w prawdziwym świecie
Big O nie jest tylko teorią. Rozdziela programy, które kończą się w sekundach, od programów, które zajmują 17 minut — na dokładnie tym samym zadaniu.
Rzeczywisty przykład: detekcja cyklu zależności w systemie budowania.
Gdy instalujesz oprogramowanie, komputer rozwiązuje graf zależności: pakiet A potrzebuje B, B potrzebuje C i tak dalej. System budowania sprawdza ten graf pod kątem cykli.
Algorytm detekcji cykli O(N²) działa dobrze przy N=100 pakietach. Przy N=50 000 pakietów (rzeczywisty projekt): zajmuje 17 minut. Naprawa O(N): 10 sekund.
Ten dokładnie defekt istnieje w GHC (kompilator Haskella), pip (menedżer pakietów Pythona), Maven (system budowania Javy), Cargo (menedżer pakietów Rusta) i 1 000+ innych projektach.
Nie dlatego, że ich autorzy byli niedbali. visited = [] zostało napisane, gdy N było małe. Kod zamarł. N wzrosło. Nikt tego nie zauważył, aż budowanie zajęło pół godziny.
Big O to słownictwo, które pozwala ci nazwać to, co się stało — i to naprawić.
---
Chcesz się zagłębić bardziej? Nasz kurs unhamming zawiera pełny rozdział o Big O, MOAD-0001 (rzeczywisty defekt O(N²) znaleziony w 1 000+ projektach open-source) i dlaczego nazwanie wzorca pozwala ci go znaleźć wszędzie. Patrz The Missing Chapter: Algorithmic Complexity.
Przewidź czasy budowania
System budowania używa detekcji cykli O(N²).
Zmierzone czasy budowania:
- N=100 pakietów: 0,01 sekund
- N=1 000 pakietów: 1 sekunda
Dla O(N²): czas skaluje się jako (N_new / N_old)².
Dla O(N): czas skaluje się jako (N_new / N_old).