Jak rośnie koszt

Big O mierzy, jak rośnie koszt wraz ze wzrostem danych wejściowych. Nie stały czynnik — tempo. Dwa algorytmy, które oba działają w „kilka milisekund” przy N=100, mogą się różnić o czynnik 10 000 przy N=10 000, jeśli jeden działa w czasie O(N), a drugi w O(N²).

Najpopularniejsze klasy złożoności

O(1) — Stała. Ten sam koszt niezależnie od N. Przykłady: wyszukiwanie w tablicy mieszającej po kluczu, dostęp do elementu tablicy po indeksie, push/pop na stosie. Podwojenie N nic nie zmienia.

O(log N) — Logarytmiczna. Każdy krok zmniejsza pozostałą pracę o połowę. Przykłady: wyszukiwanie binarne w posortowanej tablicy, zapytanie przestrzenne BVH w silniku gry, operacje na zbalansowanym drzewie binarnym. Przy N=1 000 000: log₂(1 000 000) ≈ 20 kroków.

O(N) — Liniowa. Koszt rośnie wraz z rozmiarem danych wejściowych. Przykłady: liniowe przeszukiwanie listy, odczyt pliku, zliczanie elementów w kolekcji. Przy N=10 000: 10 000 operacji.

O(N log N) — Liniowo-logarytmiczna. Prawie liniowa, nieco gorsza. Przykłady: sortowanie przez scalanie, efektywne algorytmy najkrótszej ścieżki (Dijkstra z kopcem). Przy N=10 000: ~133 000 operacji.

O(N²) — Kwadratowa. Koszt rośnie wykładniczo. Przykłady: list.contains() wywoływane wewnątrz pętli po tej samej liście, sortowanie bąbelkowe, naiwne porównywanie wszystkich par. Przy N=1 000: 1 000 000 operacji. Przy N=10 000: 100 000 000 operacji.

O(2^N) — Wykładnicza. Nieużyteczna przy jakiejkolwiek znaczącej skali. Przykłady: brute-force kombinatoryki, znajdowanie wszystkich podzbiorów. Przy N=30: ponad 1 000 000 000 operacji.

Skala, która to uwidacznia

Porównania dla N=10:
O(N):   10
O(N²):  100
stosunek:  10x

N=1 000 porównań:
O(N):   1 000
O(N²):  1 000 000
stosunek:  1 000x

N=10 000 porównań:
O(N):   10,000
O(N²):  100,000,000
ratio:  10,000x

Przy N=10 różnica jest prawie niezauważalna. Przy N=10 000 algorytm O(N²) działa 10 000 razy wolniej. Dlatego MOAD-0001 pozostawał niewidoczny przez dekady: grafy, na których działał w 1993 roku, miały 50 węzłów. Do 2020 roku ten sam kod działał na grafach zależności z 50 000 węzłami.

Klasyfikacja trzech operacji

Zastosuj klasy złożoności do konkretnych operacji. Kluczowe pytanie dla każdej z nich: ile operacji wymaga przy rosnącym N?

Poprawny kod, niewłaściwa krzywa wzrostu

Poprawny kod działający w czasie O(N²) daje identyczne wyniki jak kod O(N). Testy przechodzą. Wynik się zgadza. Nie pojawia się żaden wyjątek. Defekt ukrywa się w krzywej wzrostu.

Ta właściwość sprawia, że defekty O(N²) są osadowe: krzepną wewnątrz działającego kodu i stają się widoczne dopiero, gdy N przekroczy pewien próg. Kod się nie zmienił. Zmienił się świat wokół niego.

MOAD-0001: Osadowy defekt

Najbardziej rozpowszechniony przypadek: visited = [] wewnątrz pętli przechodzenia grafu.

visited = []
for node in graph:
if node not in visited:  # skan O(N) przy każdym wywołaniu
visited.append(node)
process(node)

Każde wywołanie not in visited skanuje od 0 do len(visited)-1 elementów. N wywołań × średnio N/2 skanowanych elementów = O(N²) łącznie. Rozwiązanie: jedna linia.

visited = set()  # test przynależności O(1)
for node in graph:
if node not in visited:  # wyszukiwanie haszowe O(1)
visited.add(node)
process(node)

To samo zachowanie. Ten sam wynik. Te same testy przechodzą. Tempo wzrostu spada z O(N²) do O(N). Przy N=1000: 1000× szybciej. Przy N=10 000: 10 000× szybciej.

Dlaczego era Hamminga zasiała ten problem

We wczesnych wersjach Javy i C domyślnym kontenerem sekwencyjnym była ArrayList (tablica dynamiczna). Zbiory istniały, ale nie były idiomatyczne — programiści sięgali po to, co znali. Przejście grafu przy N=50 w 1993 roku działało w mikrosekundach z visited = []. Ten kod trafił do kontroli wersji, był kopiowany, trafił do bibliotek i został dostarczony w menedżerach pakietów. Do 2020 roku ten sam wzorzec działał na grafach zależności z 50 000 węzłami.

Kod był poprawny w 1993 roku. Stał się kosztowny, gdy zmienił się otaczający go świat. Era Hamminga zasiała tę klasę defektów, ponieważ nigdy nie nazwano pytania o tempo wzrostu.

Diagnoza i naprawa

Zastosuj diagnozę: znajdź wzorzec O(N²) i zidentyfikuj poprawkę.

Jakie zmiany nazewnictwa

Zanim notacja Big O zyskała nazwę, programiści zauważali, że „to działa wolno”. Profilowali kod. Przepisywali go. Ale nie mogli nauczyć wzorca — mogli jedynie wskazywać pojedyncze przypadki. Wzorzec bez nazwy nie może się upowszechniać.

Gdy notacja Big O zyskała nazwę, starszy inżynier mógł powiedzieć: „to jest O(N²), zastąp to zbiorem” — a młodszy inżynier mógł to zrozumieć, zastosować i w przyszłości nauczyć tego wzorca innych. Nazwa uczyniła wzorzec przenośną jednostką wiedzy.

Hamming dostrzegł ten mechanizm w innych dziedzinach. Opisał, jak nadanie nazwy „spaghetti code” w latach 60. pozwoliło społeczności rozpoznać, omawiać i w końcu wyeliminować klasę błędów, której wszyscy doświadczali, ale której nikt wcześniej nie nazwał. Ten sam mechanizm dotyczy klas złożoności.

Unhamming dodaje słownictwo, którego Hamming nie uwzględnił: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Te nazwy pozwalają dostrzec krzywą wzrostu w czytanym kodzie, przewidzieć wydajność przy skalowaniu oraz precyzyjnie komunikować poprawki. Spełniają one własny test Hamminga dla pojęcia fundamentalnego: są trwałe i generują większość pozostałych elementów dziedziny. [TITLE who_coined_big_o/]

Od teorii liczb do informatyki

Notacja Big O nie powstała w informatyce. Zrodziła się w matematyce czystej — konkretnie w teorii liczb — 74 lata przed tym, jak Donald Knuth zaadaptował ją do algorytmów.

Paul Bachmann, 1894

Paul Bachmann, niemiecki matematyk, wprowadził notację O w swojej książce z 1894 roku Die Analytische Zahlentheorie (Analityczna teoria liczb). Potrzebował zwięzłego sposobu wyrażenia, że jedna wielkość rośnie nie szybciej niż inna, z dokładnością do stałej. Zapis „f(n) = O(g(n))” oznaczał: f rośnie co najwyżej tak szybko jak g. Pozwoliło to teoretykom liczb wnioskować o błędach przybliżeń bez śledzenia dokładnych stałych.

Bachmann nie myślał o pętlach, strukturach danych ani czasie wykonania. Interesowało go, jak rozkładają się liczby pierwsze — szczególnie błędy w Twierdzeniu o liczbach pierwszych.

Edmund Landau, 1909

Edmund Landau, kolejny niemiecki matematyk, spopularyzował tę notację w swoim dziele z 1909 roku Handbuch der Lehre von der Verteilung der Primzahlen (Podręcznik o rozkładzie liczb pierwszych). Landau wprowadził także powiązaną notację o (little-o) i tak intensywnie używał rodziny symboli asymptotycznych, że zaczęto je nazywać notacją Bachmanna-Landaua lub po prostu notacją Landaua.

Przez sześć dekad notacja O żyła wyłącznie w matematyce. Żaden programista o niej nie myślał.

Donald Knuth, 1968 & 1976

Donald Knuth przeniósł notację do informatyki. W książce The Art of Computer Programming (t. 1, 1968) Knuth użył notacji O do opisu złożoności czasowej algorytmów — bezpośredniego przeniesienia narzędzia Bachmanna do nowego obszaru. Był pierwszym, który zastosował ją systematycznie w analizie algorytmów.

W 1976 roku Knuth opublikował krótki artykuł w SIGACT News zatytułowany „Big Omicron and Big Omega and Big Theta”. Wprowadził w nim Omega (Ω) dla dolnych ograniczeń oraz Theta (Θ) dla ścisłych ograniczeń, uzupełniając trójczłonowe słownictwo, z którego korzysta dziś informatyka. Argumentował również za standaryzacją użycia tych symboli w całej dziedzinie — celowe ujednolicenie, które przyspieszyło ich przyjęcie.

Na początku lat 80. Big O pojawiało się w każdym podręczniku algorytmów. W latach 90. stało się standardowym pojęciem na rozmowach kwalifikacyjnych.

74-letnia podróż

1894 — Bachmann wprowadza O w teorii liczb
1909 — Landau popularyzuje O, o oraz całą rodzinę notacji
1953 — Hamming zaczyna badania w Bell Labs (nigdy nie poznaje notacji Big O jako narzędzia CS)
1968 — Knuth stosuje O do analizy algorytmów w TAOCP Vol. 1
1976 — Knuth dodaje Omega i Theta; postuluje standaryzację
1980s — Big O wchodzi do wszystkich programów nauczania CS
1993 — Warstwa osadowa MOAD-0001 powstaje w kodzie produkcyjnym
1995 — Hamming prowadzi ostatnią wersję swojego kursu; nigdy nie omawia Big O
2026 — MOAD-0001 znaleziony w ponad 1 000 projektach open-source

Bachmann's tool spent 74 years in pure mathematics, visible to every mathematician but invisible to every programmer. Knuth saw the transplant. Hamming — working in the same era, collaborating with the same computing community — never made it part of his course.

Dlaczego standaryzacja Knutha miała znaczenie

Artykuł Knutha z 1976 roku zrobił coś więcej niż tylko wprowadzenie Omega i Theta. Argumentował, że dziedzina potrzebuje spójnej notacji, a niespójna notacja jest aktywnie szkodliwa. Różne podręczniki używały O do oznaczania różnych rzeczy — czasem jako ograniczenie górne, czasem jako przybliżenie, czasem bez określenia, czy stałe mają znaczenie. Knuth to uporządkował.

To jest dynamika nazywania wzorców Hamminga zastosowana do samej notacji. Zanim Knuth ustandaryzował symbole, inżynierowie nie mogli precyzyjnie komunikować twierdzeń o złożoności między podręcznikami, artykułami czy zespołami. Po standaryzacji „to działa w O(N log N)” miało dokładnie jedno znaczenie, niezależnie od tego, kto to powiedział.

Knuth dodał też nieformalną interpretację: „O(f(n)) oznacza, że czas działania wynosi co najwyżej stałą razy f(n), dla wszystkich wystarczająco dużych n”. Ta interpretacja — ograniczenie górne, z dokładnością do stałej, dla dużych danych wejściowych — stała się standardową intuicją, której uczy się każdy programista.