Notacja Big O Wyjaśniona na Przykładach Kodu

Odczyt ze słownika w Pythonie trwa około 100 nanosekund, niezależnie od tego, czy słownik ma 1000 kluczy, czy 1 000 000. Podwójna pętla szukająca duplikatów w liście trwa pół milisekundy przy 200 elementach i 136 milisekund przy 3200. Szesnaście razy więcej danych wejściowych, prawie 280 razy dłuższe oczekiwanie. Ta sama maszyna, ten sam Python. Notacja Big O to nazwa tej różnicy.

Co mierzy notacja Big O

Big O opisuje, jak rośnie czas działania (albo zużycie pamięci) fragmentu kodu wraz ze wzrostem danych wejściowych. To nie jest pomiar stoperem i nie ma znaczenia, czy twój laptop jest szybki, czy wolny. Liczy się kształt krzywej wzrostu: gdy podwoisz dane wejściowe, czas się podwaja, rośnie czterokrotnie, czy prawie się nie zmienia?

Notacja odrzuca wszystko, co nie zmienia tego kształtu, od stałych czynników po sprzęt, na którym działa kod. O(n) oznacza “proporcjonalne do n”, niezależnie od tego, czy rzeczywisty koszt to 3n + 7, czy 0.001n + 1000000. Zrób n wystarczająco duże, a zostanie tylko kształt.

Przykłady Big O w Pythonie, mierzone przy rosnących rozmiarach danych

Każda z poniższych funkcji została zmierzona modułem timeit w Pythonie 3.11, przy rozmiarach danych wejściowych różniących się o rząd wielkości (lub o dwukrotność).

Czas stały: odczyt ze słownika

1
2

def dict_lookup(d, key):
    return d[key]

Dane wejściowe rosną tysiąckrotnie. Czas na wywołanie pozostaje płaski, w granicach szumu pomiarowego. Słownik to tablica haszująca: Python liczy hash klucza i skacze prosto do odpowiedniego kubełka, niezależnie od tego, ile innych wpisów istnieje. To jest O(1), czas stały.

Czas liniowy: sumowanie listy

1
2
3
4
5

def sum_loop(nums):
    total = 0
    for n in nums:
        total += n
    return total

Każdy dziesięciokrotny wzrost n przynosi mniej więcej dziesięciokrotny wzrost czasu. Pętla dotyka każdego elementu dokładnie raz, więc praca skaluje się wprost proporcjonalnie do danych wejściowych. To jest O(n), czas liniowy, i to tam żyje większość kodu, który piszesz na co dzień.

Czas kwadratowy: szukanie duplikatów w naiwny sposób

1
2
3
4
5
6

def has_duplicate_naive(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Podwojenie n mniej więcej czterokrotnie wydłuża czas na każdym kroku. Pętla zewnętrzna wykonuje się n razy, a wewnętrzna niemal n razy na każdą iterację zewnętrzną, więc całkowita praca jest proporcjonalna do n * n. To jest O(n^2), czas kwadratowy. To ta klasa rujnuje kod na produkcji, bo w teście na 50 wierszach wygląda nieszkodliwie, a przy 50 000 kończy się przekroczeniem limitu czasu.

Czas logarytmiczny: wyszukiwanie binarne

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def binary_search(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        elif sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Tysiąckrotny wzrost n ledwie podwaja czas. Każdy krok pętli odrzuca połowę pozostałego zakresu, więc liczba potrzebnych kroków rośnie z log2(n), a nie z n: około 10 kroków dla tysiąca elementów, około 20 dla miliona. To jest O(log n). Git bisect wykonuje ten sam algorytm na historii commitów zamiast na posortowanej tablicy: znajduje uszkodzony commit wśród setek kandydatów w kilku krokach, bo każdy test odrzuca połowę pozostałego zakresu.

Czas liniowo-logarytmiczny: sortowanie

1

sorted_nums = sorted(nums)

Każdy dziesięciokrotny krok n kosztuje więcej niż dziesięciokrotny wzrost czasu, ale daleko od stukrotnego, jaki pokazałby algorytm kwadratowy. sorted() w Pythonie używa Timsortu, który wykonuje O(n log n) porównań: scalanie przebiega w około log n rundach, a każda runda dotyka każdego z n elementów raz, żeby scalić sąsiednie ciągi. Każdy uniwersalny algorytm sortujący, którego używasz na co dzień (Timsort, sortowanie przez scalanie, przeciętny przypadek quicksortu), ląduje właśnie tutaj, dlatego O(n log n) traktuje się jako “najlepsze, co sortowanie może dać”, zamiast porównywać je z O(n).

Najczęstsze klasy złożoności Big O, od najszybszej do najwolniejszej

Spójrz na dwa ostatnie wiersze. Przejście z O(n log n) do O(n^2) przy milionie elementów to różnica między raportem, który liczy się sekundę, a takim, który wciąż działa, gdy ktoś zabija proces.

Czego notacja Big O nie mówi

Big O opisuje wzrost asymptotyczny, czyli to, co dzieje się, gdy n staje się dowolnie duże. W tej luce gubią się trzy rzeczy.

Stałe są niewidoczne. O(n) ze stałym współczynnikiem 1000 może w praktyce działać wolniej niż O(n^2) z maleńką stałą, dla każdego n, jakie kiedykolwiek zobaczysz. Big O mówi, która krzywa w końcu wygrywa, a nie która funkcja jest szybsza na twoich danych. Dlatego sortowanie przez wstawianie, które jest O(n^2), wciąż jest lepszym wyborem dla bardzo małych tablic, i dlatego Timsort używa binarnego sortowania przez wstawianie, żeby zbudować każdy mały ciąg (run) do minimalnej długości (minrun, zwykle 32-64 elementy), zanim zacznie scalać ciągi ze sobą.

Małe n nie pokazuje krzywej. Powyższe czasy kwadratowe stały się wyraźnie kwadratowe dopiero, gdy n przekroczyło kilkaset. Przy n = 10 prawie wszystko kończy się, zanim to zauważysz, dlatego funkcja może przejść każdy test napisany lokalnie, a potem polec przy wolumenach danych na produkcji.

Złożoność pamięciowa to osobna oś. dict_lookup, sum_loop, has_duplicate_naive i binary_search działają na niemal stałej dodatkowej pamięci: żadna z nich nie alokuje drugiej struktury danych proporcjonalnej do wejścia. sorted() owszem: zwraca nową listę tej samej wielkości co wejście, O(n) pamięci, bo nigdy nie sortuje w miejscu. Niektóre algorytmy celowo wymieniają pamięć na szybkość: funkcja Fibonacciego z memoizacją zapamiętuje każdy policzony już wynik, wydając O(n) pamięci, żeby zamienić O(2^n) czasu na O(n). Podając złożoność funkcji, powiedz, o którą oś ci chodzi: szybsza wersja to często ta, która zużywa więcej pamięci.

Jak wyłapać ukryte O(n^2) w swoim kodzie

Podwójna pętla z wcześniejszego przykładu to oczywisty przypadek. Ten, który trafia na produkcję, zwykle nie ma żadnej zagnieżdżonej pętli w zasięgu wzroku.

Testy przynależności wewnątrz pętli. x in jakas_lista to O(n) na liście, bo Python musi przeskanować ją w całości. Wykonanie tego sprawdzenia wewnątrz pętli, która i tak działa n razy, daje O(n^2) bez drugiego for w zasięgu wzroku:

1
2
3
4
5
6

# O(n^2): "in" przeszukuje całą listę przy każdej iteracji
seen = []
for item in items:
    if item in seen:
        continue
    seen.append(item)

Zamień listę na set, gdzie przynależność to O(1), a pętla spada do O(n):

1
2
3
4
5
6

# O(n): "in" to wyszukiwanie przez hash
seen = set()
for item in items:
    if item in seen:
        continue
    seen.add(item)

Odbudowywanie listy zamiast dopisywania do niej. result + [item] alokuje nową listę i kopiuje do niej każdy już istniejący element; result.append(item) powiększa istniejącą listę w miejscu.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def build_with_plus(n):
    result = []
    for i in range(n):
        result = result + [i]   # za każdym razem kopiuje wszystko, co zbudowano do tej pory
    return result

def build_with_append(n):
    result = []
    for i in range(n):
        result.append(i)        # O(1) zamortyzowane
    return result

Zbudowanie listy 8000 elementów za pomocą + zajęło 65 ms. Ta sama lista z .append() zajęła 0,15 ms. Różnica rośnie wraz z n, bo jedno jest kwadratowe, a drugie liniowe.

Zapytanie N+1. Pobierasz listę wierszy, a potem przechodzisz przez nią pętlą, która wysyła kolejne zapytanie na wiersz po powiązane dane. Jedno zapytanie zmienia się w n + 1: O(n) podróży w obie strony do bazy danych zamiast jednej. Indeks, opisany w jak działają indeksy w bazie danych, zmienia pojedyncze wyszukanie z przeszukania tabeli O(n) na O(log n). Nie pomaga to jednak w pętli wysyłającej tysiąc osobnych zapytań. Naprawa ma tę samą postać co naprawa z setem powyżej: zastąp operację na wiersz operacją wykonaną raz. Tutaj oznacza to jedno zapytanie z joinem, które opisują typy JOIN w SQL wyjaśnione na przykładach.

Jak zmierzyć złożoność własnego kodu

Wybierz podejrzaną funkcję, zwykle taką z pętlą, której liczba iteracji zależy od rozmiaru danych. Zmierz ją timeit przy trzech lub czterech rozmiarach wejścia, każdy dziesięć razy większy od poprzedniego, i podziel każdy czas przez poprzedni. Współczynnik bliski 1 to O(1) albo O(log n). Bliski 10 to liniowa. Między 10 a 100 to O(n log n), jak 17-21 w tabeli sorted(). Bliski 100 oznacza, że masz O(n^2) do wytropienia; jeśli to sprawia, że duże rozmiary są zbyt wolne, by na nie czekać, podwajaj n zamiast mnożyć je przez dziesięć i szukaj współczynnika bliskiego 4. Zacznij od testów przynależności na listach i odbudowań za pomocą + wewnątrz tej pętli, potem od każdego zapytania wysyłanego raz na wiersz.

Powiązane artykuły

• Git Bisect: Jak Znaleźć Commit, który Wprowadził Buga
• Jak Działają Indeksy w Bazie Danych i Kiedy Je Dodawać
• Typy JOIN w SQL Wyjaśnione na Przykładach