Algorytmy, które kończą się na czas: Sprawdzenie złożoności

Piszesz funkcję, uruchamiasz ją na danych testowych i działa dobrze. Potem trafia do produkcji — 500 000 wierszy zamiast 500 — i żądanie się kończy limitem czasu. To dzieje się stale i prawie zawsze chodzi o problem złożoności ukryty za kodem, który wyglądał rozsądnie na małej skali.

Dlaczego twój laptop cię okłamał

Algorytm O(n²) działający na 100 elementach wykonuje 10 000 operacji. To natychmiastowe na każdej maszynie. Uruchom ten sam algorytm na 100 000 elementach i masz 10 miliardów operacji — minuty lub godziny zamiast milisekund. Skok z n do n² nie wydaje się niebezpieczny, dopóki n nie rośnie, co dokładnie wyjaśnia, dlaczego przechodzi przez code review i testy lokalne.

Klasyczny przykład: sprawdzanie duplikatów zagnieżdżoną pętlą.

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

To jest O(n²). Zamień na set:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Teraz to O(n). Wyszukiwania w set mają średnio O(1), więc cała funkcja skaluje się liniowo zamiast kwadratowo. Na 10 000 elementach to różnica między około 100 milionami a 10 000 porównaniami.

Mierz zanim zoptymalizujesz

Nie zgaduj. Użyj timeit do mikrobenchmarków:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

Do większych funkcji profiluj za pomocą cProfile:

python -m cProfile -s cumulative myscript.py

Spójrz na kolumnę cumtime. Jeśli jedna funkcja pochłania 90% czasu wykonania, to jest twój cel. Optymalizowanie kodu, który nie jest wąskim gardłem, marnuje twój czas i dodaje złożoność bez zysku.

Typowe wzorce, które cicho stają się powolne

Powtarzające się sprawdzenia przynależności do listy. if x in my_list to O(n) dla listy, ale O(1) średnio dla set lub dict. Jeśli sprawdzasz przynależność wewnątrz pętli, to O(n) sprawdzenie wewnątrz pętli O(n) daje ci O(n²) ogółem. Zamień listę na set i wracasz do O(n).

Łączenie stringów w pętli. W Python result += chunk wewnątrz pętli nad stringami to O(n²) w najgorszym wypadku, bo stringi są niezmienne i każde łączenie kopiuje całość. Użyj ''.join(chunks) zamiast tego — buduje string raz.

Sortowanie, gdy nie musisz. sorted() to O(n log n). Jeśli wzywasz to wewnątrz pętli tylko aby znaleźć max lub min w każdej iteracji, użyj max()/min() (O(n)) lub lepiej, heapa (heapq) jeśli potrzebujesz bieżącej ekstremum wielokrotnie. heapq.nlargest(k, data) to O(n log k), znacznie tańsze niż sortowanie całej listy, gdy k jest małe.

Funkcje rekurencyjne bez memoizacji. Naiwne rekurencyjne Fibonacci to O(2ⁿ), bo ponownie oblicza te same podproblemy. Dodaj functools.lru_cache i spada do O(n):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Czytanie Big O z prawdziwego kodu, szybko

Liczaj zagnieżdżone pętle nad tym samym wejściem — to zwykle twój wykładnik. Pojedyncza pętla to O(n). Pętla wewnątrz pętli to O(n²), chyba że zakres pętli wewnętrznej się zmniejsza (jak w zoptymalizowanej formie bubble sort, wciąż O(n²) w najgorszym wypadku, ale mniej porównań). Wywołania rekurencyjne, które dzielą problem na pół, jak wyszukiwanie binarne lub merge sort, wskazują na O(log n) lub O(n log n). Wywołania rekurencyjne, które rozgałęziają się w wiele wywołań na poziomie, jak naiwne Fibonacci, wskazują na czas wykładniczy — silny sygnał, że potrzebujesz memoizacji lub iteracyjnego przepisania.

Dobry nawyk: zanim napiszesz zagnieżdżone pętle lub rekursję na danych zwróconych użytkownikowi, zapytaj co n mogłoby realistycznie być w produkcji, nie w twoim pliku testowym. Jeśli n mogłoby osiągnąć sześć cyfr, rozwiązanie O(n²) potrzebuje drugiego spojrzenia zanim trafi do wysyłki.

Więcej na temat analizy złożoności, algorytmów sortowania i narzędzi profilowania znajdziesz w segmentach Python i Computer Science na Korra Studio.