Big O to język rozmów technicznych o algorytmach. Bez niego nie odpowiesz precyzyjnie na "jak to działa dla 1 mln wpisów", "która struktura tu pasuje" albo "czemu twoje rozwiązanie jest gorsze niż referencyjne".
Ten artykuł to 10-minutowa intuicja: 6 najczęstszych klas złożoności z growth chart, sygnałami rozpoznawczymi w kodzie i pułapkami z mechanizmem. Implementacje są w Pythonie dla zwięzłości — sama notacja Big O jest language-agnostic.
Wszystkie przykłady zakładają Python 3.12+.
Co to Big O — definicja i intuicja
Big O opisuje jak rośnie koszt algorytmu względem rozmiaru wejścia n. W rozmowach technicznych chodzi o trend wzrostu, nie o pomiar czasu konkretnego uruchomienia.
Standardem jest analiza pesymistyczna: pytanie brzmi jak źle może być dla dużego wejścia. Notacja ignoruje stałe i niższe rzędy — O(2n + 5) zapisuje się jako O(n). Asymptotyka to podstawowy język analizy algorytmów w literaturze (np. Introduction to Algorithms — Cormen et al.).
Growth chart — koszt operacji dla różnych n:
n O(1) O(log n) O(n) O(n log n) O(n²)
10 1 ~3 10 ~33 100
100 1 ~7 100 ~664 10 000
1 000 1 ~10 1 000 ~9 966 1 000 000
1 000 000 1 ~20 1 000 000 ~19 931 569 10¹²
Pamiętaj — to są liczby kroków, nie sekundy. Sekunda zależy od stałych ukrytych w notacji, języka, hardware'u.
def first_item(items):
return items[0]
print(first_item([10, 20, 30])) # expected_output: 10
Pułapka: mylenie notacji z czasem. O(100n) == O(n) w notacji, ale stałe nadal mają znaczenie w praktyce — dwa algorytmy O(n) mogą różnić się 100× przez implementację, alokacje albo cache misses. Mechanizm błędu: na rozmowie mówisz "to jest O(n)" sugerując równoważność z innym O(n), a w realnych pomiarach jest 100× wolniejszy.
O(1) — czas stały
O(1) oznacza koszt niezależny od liczby elementów. W Pythonie typowe przykłady to len(list), dostęp list[i] oraz średni przypadek odczytu z dict lub sprawdzenia elementu w set.
Intuicja: lista trzyma długość w polu metadanych, więc len() nie zlicza elementów — tylko odczytuje. Indeksowanie używa pointer arithmetic na ciągłej tablicy. dict i set używają hashowania ze stałą liczbą porównań (przy dobrym rozkładzie hashy). Szczegóły hashowania: Haszowanie w Zadaniach.
Python Wiki TimeComplexity podaje Get Item dla listy jako O(1) oraz Get Length jako O(1).
items = [3, 5, 8, 13]
lookup = {"answer": 42}
print(len(items)) # expected_output: 4
print(items[2]) # expected_output: 8
print(lookup["answer"]) # expected_output: 42
Pułapka: O(1) nie znaczy "natychmiast". Operacja może mieć kosztowną stałą, alokację albo rzadki przypadek amortyzowany — ale jej klasa wzrostu nie zależy od n. Mechanizm: kandydat mówi "O(1) więc szybko" o operacji dict[key] która przy zerwaniu hash table powoduje rehash całej struktury. Stała wykonania potrafi być duża; klasa pozostaje O(1).
O(log n) — dziel-i-zwyciężaj
O(log n) pojawia się gdy każdy krok istotnie zmniejsza problem, zwykle o połowę. Klasyczny przykład to wyszukiwanie binarne w posortowanej tablicy — szczegóły wzorca: Wyszukiwanie Binarne.
W kontekście algorytmów dziel-i-zwyciężaj logarytm w Big O zwykle traktuje się jako log₂ — pytamy ile razy można podzielić wejście przez dwa, zanim zostanie jeden element. Dla 1 mln elementów to ~20 kroków, dla 1 mld — ~30.
from bisect import bisect_left
def binary_contains(sorted_items, target):
index = bisect_left(sorted_items, target)
return index < len(sorted_items) and sorted_items[index] == target
print(binary_contains([1, 3, 5, 7, 9], 7)) # expected_output: True
Trace dla binary_contains([1, 3, 5, 7, 9], 7):
Krok 1: tablica ma 5 elementów, środkowy index 2, wartość 5.
Krok 2: 7 > 5, odrzucamy lewą połowę → szukamy w [7, 9].
Krok 3: środkowy index 0 (w sub-tablicy), wartość 7.
Krok 4: trafiliśmy → return True.
Ścieżka: 3 porównania dla n=5, czyli ~log₂(5) ≈ 2.3.
Pułapka: O(log n) wymaga struktury, która pozwala odrzucać duże części danych (posortowana tablica, BST, heap). Mechanizm błędu: kandydat pisze pętlę z warunkiem if na nieposortowanej liście i mówi "to jest O(log n)" — ale każdy element może być odrzucony lub nie, więc w pesymistycznym przypadku patrzymy na wszystkie → faktyczne O(n).
O(n) — pojedynczy przebieg
O(n) oznacza koszt proporcjonalny do liczby elementów. Jedno przejście po kolekcji wystarcza dla operacji takich jak sum, max, liczenie wystąpień albo in dla listy.
Intuicja: każdy element jest dotykany dokładnie raz (lub stałą liczbę razy). Dla n=1000 algorytm wykonuje ~1000 podstawowych operacji. Skalowanie liniowe oznacza, że podwojenie wejścia podwaja czas.
Python Wiki podaje x in s dla listy jako O(n) (lista musi sprawdzić element po elemencie). Dla min(s) i max(s) też widnieje O(n).
def count_even(numbers):
count = 0
for number in numbers:
if number % 2 == 0:
count += 1
return count
print(count_even([1, 2, 4, 7, 10])) # expected_output: 3
Pułapka: dwa OSOBNE przebiegi nadal są O(n). for x in items: ... po którym for y in items: ... to O(2n) = O(n), nie O(n²). Mechanizm błędu: kandydat widzi dwie pętle pod sobą, ogłasza O(n²) — ale ta klasa wymaga zagnieżdżenia. Dopiero gdy wewnętrzna pętla zaczyna się od indeksu zewnętrznej (każdy element porównany z każdym), dostajemy O(n²).
O(n log n) — sortowanie
O(n log n) często pojawia się przy sortowaniu porównawczym: merge sort, heap sort, dobre warianty quicksort oraz Pythonowy Timsort. Python Wiki podaje sortowanie listy jako O(n log n).
Intuicja: dolne ograniczenie sortowania porównawczego to Ω(n log n) — szczegóły wzorca: Algorytmy sortowania. Klasa jest praktycznie wystarczająca dla większości zadań, rośnie znacznie wolniej niż O(n²) i pozwala stosować wzorzec "posortuj, potem przejdź liniowo" do problemów typu count duplicates albo find median.
def sorted_unique(items):
return sorted(set(items))
print(sorted_unique([4, 2, 4, 1, 2])) # expected_output: [1, 2, 4]
Pułapka: mylenie O(log n) i O(n log n). Sortowanie kolekcji nie jest logarytmiczne, nawet jeśli pojedyncze wyszukiwania PO sortowaniu mogą być O(log n). Mechanizm błędu: kandydat liczy sort() jako O(log n) w analizie złożoności całego algorytmu, otrzymuje błędną sumaryczną klasę. Dla 1 mln elementów: log₂(10⁶) ≈ 20 vs n × log₂(n) ≈ 20 mln — różnica 6 rzędów wielkości.
O(n²) — wszystkie pary
O(n²) zwykle oznacza zagnieżdżoną pętlę sprawdzającą wszystkie pary elementów. Przykłady: bubble sort, naive duplicate check, porównywanie każdego elementu z każdym innym.
Intuicja: dla n=1000 algorytm wykonuje ~1 mln operacji, dla n=10 000 — ~100 mln. Klasa zaczyna boleć już przy n rzędu kilku tysięcy. W rozmowie warto od razu pytać czy istnieje wariant z haszowaniem (set/dict), sortowaniem albo dwoma wskaźnikami.
def has_duplicate_slow(items):
for left in range(len(items)):
for right in range(left + 1, len(items)):
if items[left] == items[right]:
return True
return False
print(has_duplicate_slow([1, 3, 5, 3])) # expected_output: True
Pułapka: nie każda zagnieżdżona pętla jest O(n²). Jeśli wewnętrzna pętla ma stały limit (np. for j in range(10)) albo pracuje na niezależnym m, poprawny zapis to O(n) lub O(n*m). Mechanizm błędu: kandydat widzi for ... for ... i automatycznie pisze O(n²) bez sprawdzenia czy pętle iterują tę samą zmienną wejściową.
Sygnały rozpoznawcze klas Big O
Rozpoznawanie klasy w cudzym kodzie jest na rozmowie ważniejsze niż liczenie kroków od zera. Sygnały do klasy:
O(1) len(), [i], dict[k], set membership average, append
O(log n) bisect, BST search, halve-the-space loop, integer log loop
O(n) single for over input, sum, max, in list
O(n log n) sort(), sorted(), priority queue with n inserts
O(n²) nested for over same input, all-pairs check
O(2^n) naive recursion bez memoization (Fibonacci, subset)
Dodatkowy sygnał: call stack rekurencji. Funkcja rekurencyjna wywołująca samą siebie dwa razy bez memoization daje wykładniczy wzrost — szczegóły: Rekurencja vs Iteracja. Funkcja schodząca w głąb jednej gałęzi (binary search, drzewo) daje O(log n).
def has_duplicate_fast(items):
seen = set()
for item in items:
if item in seen:
return True
seen.add(item)
return False
print(has_duplicate_fast([1, 3, 5, 3])) # expected_output: True
Pułapka: ten sam problem może mieć różne klasy w zależności od użytej struktury danych. has_duplicate jako zagnieżdżona pętla = O(n²). Z set = O(n). Mechanizm błędu: kandydat widzi pierwszą wersję, ogłasza Big O bez analizy alternatyw. Na rozmowie często chodzi o pokazanie ścieżki O(n²) → O(n), nie o uznanie pierwszej klasy.
Praktyczna rola Big O na rozmowie
Big O pomaga odróżniać rozwiązania o różnych klasach wzrostu zanim zacznie się mikrooptymalizacja. Zmiana z O(n²) na O(n) jest zwykle ważniejsza niż skracanie pojedynczych instrukcji.
Dobry tok myślenia w zadaniu rekrutacyjnym: najpierw poprawność, potem koszt, potem alternatywa. Często przejście z dwóch pętli do set albo dict jest sednem rozwiązania — z O(n²) do O(n).
Na rozmowie trzymaj się trzech reguł: nazwij klasę, wskaż gdzie jest dominujący koszt (sort × n operacji vs jedno set lookup), powiedz pesymistyczny przypadek dla struktur ze średnim O(1) (np. dict przy hash collision).
Pułapka: obiecywanie konkretnych czasów ("1 sekunda → 100 ms") bez pomiaru i kontekstu. Mechanizm błędu: rozmówca pyta "ile razy szybsze" o przejście z O(n²) do O(n), kandydat mówi "100×" — ale faktycznie zależy to od n, hardware'u i stałych. Poprawnie: "niższa klasa wzrostu zmienia skalowanie" + przykład rzędu wielkości dla konkretnego n.
Najczęstsze błędy
O(1) ≠ "natychmiast". To klasa wzrostu, nie gwarancja czasu — operacja O(1) z dużą stałą może być wolniejsza niż O(n) z małą dla małych n. Stałe znikają w notacji, ale nie w pomiarach.
Mylenie O(log n) z O(n log n). Sortowanie kolekcji nie jest logarytmiczne — to O(n log n). Wyszukiwanie po sortowaniu może być O(log n). Dla n=10⁶: ~20 vs ~20 mln — różnica 6 rzędów.
Dwa osobne przebiegi to O(n), nie O(n²). Zagnieżdżenie po tym samym wejściu daje O(n²). Sekwencyjne pętle = O(2n) = O(n). Na rozmowie warto wprost powiedzieć "każdy element odwiedzony stałą liczbę razy".
O(log n) wymaga struktury pozwalającej odrzucać dane. Posortowana tablica, BST, heap. Sam if w pętli po nieposortowanej liście nie staje się logarytmiczny — w pesymistyce każdy element musi zostać sprawdzony.
Big O = upper bound, NIE średnia. dict.get() jest O(1) average, ale O(n) worst case przy złym hash. Na rozmowie zawsze precyzuj który przypadek analizujesz: average / worst / amortized.
FAQ
Czy zawsze trzeba dążyć do najniższej klasy?
Nie. O(n²) jest OK dla małych danych (n < 1000) lub kodu wykonywanego rzadko. Optymalizacja do O(n) często wprowadza większą złożoność strukturalną (dodatkowy set, dodatkowa pamięć). Reguła: najpierw poprawność, potem koszt — optymalizuj gdy faktycznie boli, nie z zasady.
Co z amortyzowanym kosztem?
Niektóre operacje mają zmienny koszt per-call, ale stały koszt amortyzowany. list.append jest O(1) amortyzowany — większość wywołań jest stała, ale rzadko cała lista jest realokowana (O(n)). Suma kosztów po n wywołaniach to nadal O(n), więc średni koszt na wywołanie to O(1).
Jak Big O odnosi się do złożoności pamięciowej?
Big O opisuje nie tylko czas, ale też pamięć (space complexity). O(1) space = stała dodatkowa pamięć poza wejściem. O(n) space = struktura rosnąca z wejściem (np. set z duplikatami). Stos rekurencji też się liczy — rekurencja głębokości n używa O(n) pamięci niezależnie od czasu pracy.
Co to Θ (Theta) i Ω (Omega) — czemu Big O wystarczy?
Big O to upper bound (asymptotyczny limit górny). Ω to lower bound (limit dolny), Θ to ścisłe ograniczenie (gdy upper i lower są tej samej klasy). W rozmowach technicznych mówi się prawie wyłącznie o Big O, bo oczekiwana odpowiedź dotyczy worst case. Akademicka analiza używa wszystkich trzech.
Czemu hash table jest "średnio O(1)" a nie O(1)?
Bo zakładamy "good hash" — równomierny rozkład kluczy w bucketach. W skrajnym przypadku wszystkie klucze trafiają w ten sam bucket (kolizje), operacja staje się O(n). Python randomizuje hashe (PEP 456) żeby utrudnić HashDoS, ale gwarancja pozostaje "average O(1), worst O(n)". Szczegóły: Haszowanie w Zadaniach.
Czy mogę pisać O(N) zamiast O(n)?
Konwencja: n małą literą oznacza rozmiar wejścia. Wielkie litery (N, M) używa się gdy są dwa różne rozmiary wejścia (O(N + M) — np. iteracja po dwóch listach o niepowiązanych długościach). Pisownia mała/wielka jest stylistyczna, nie matematyczna — czytelnik zrozumie obie. Konsystencja w jednym artykule lub odpowiedzi jest ważniejsza niż konkretny styl.
Powiązane tematy
- Wyszukiwanie Binarne — Dziel-i-Zwyciężaj na Rozmowie — kanoniczny przykład
O(log n)z konkretną implementacją i pułapkami granicznymi. - Algorytmy Sortowania —
O(n log n)w praktyce; merge sort, quicksort, Timsort i kiedy która klasa wystarczy. - Czas vs Pamięć — Kompromisy — Big O odpowiada na "jak szybko"; ten artykuł na "jakim kosztem pamięciowym".
Sprawdź swoją wiedzę quizem
Przerób ten artykuł w 15-pytaniowy quiz testujący 6 klas Big O, sygnały rozpoznawcze i pułapki — gdzie masz luki przed rozmową techniczną: https://odpytywarka.pl/q/EpDtAa.
Masz własne notatki? Wgraj PDF lub wklej tekst na stworz-quiz-z-pdf — pierwsze 3 strony PDF i 15 pytań jednokrotnego wyboru za darmo, generowanie 30-60 sekund.