Po co rozumieć kompromisy time vs space
Algorytmy mają dwa osobne koszty: time complexity (ile operacji) i space complexity (ile dodatkowej pamięci). W rozmowach technicznych odpowiedź "to jest O(n)" bez pokazania kompromisu zdradza powierzchowne myślenie.
Ten artykuł to 6 typowych kompromisów w Pythonie z działającym kodem: kiedy poświęcić pamięć dla szybkości (hash table, memoizacja), kiedy odwrotnie (generator zamiast listy, sortowanie in-place).
Wszystkie przykłady zakładają Python 3.12+.
Time complexity vs space complexity — dwa osobne koszty
Time complexity opisuje jak rośnie liczba operacji względem rozmiaru wejścia n. Space complexity opisuje dodatkową pamięć potrzebną poza wejściem. W Pythonie oba koszty obejmują obiekty pomocnicze, kontenery, stos wywołań i cache.
Ten sam algorytm może być szybki, ale pamięciożerny, albo oszczędny pamięciowo, lecz wolniejszy. Złożoność trzeba oceniać razem z modelem danych: list, set, dict, iterator i rekurencja mają różne profile.
numbers = [4, 1, 3, 2]
print(len(numbers)) # 4
print(numbers[0]) # 4
Pułapka rekrutacyjna: Big O ukrywa stałe, alokacje i implementację CPython. O(1) nie znaczy "darmowe", tylko "nie rośnie liniowo z n". Przy dużych danych dodatkowa pamięć może być ważniejsza niż asymptotycznie szybszy czas.
Hash table vs liniowa lista — szybciej kosztem pamięci
Detekcja duplikatów przez porównywanie każdego z każdym ma O(n²) time i O(1) extra space. Wersja z set używa hash table: typowo O(n) time, ale wymaga O(n) extra space.
Python Wiki: x in list jest liniowe, a x in set i k in dict mają średnio O(1). To klasyczny kompromis: dokładamy strukturę pomocniczą, żeby zmniejszyć liczbę porównań.
def has_duplicate(items: list[int]) -> bool:
seen: set[int] = set()
for item in items:
if item in seen:
return True
seen.add(item)
return False
print(has_duplicate([3, 1, 4, 1])) # True
print(sorted({3, 1, 4, 1})) # [1, 3, 4]
Pułapka rekrutacyjna: hash table nie zawsze wygrywa. Potrzebuje pamięci na buckets i obiekty, a worst case lookup może spaść do O(n). Dla małych wejść prostsza lista bywa wystarczająca i czytelniejsza.
Memoizacja — recursion zamienia czas na cache
Naiwne Fibonacci liczy te same podproblemy wielokrotnie: O(2^n) time + O(n) stack. Memoizacja zapamiętuje wyniki — dla Fibonacci redukuje time do O(n) kosztem O(n) cache.
W dynamic programming rozmiar cache zależy od liczby stanów. Jednowymiarowy stan zwykle daje O(n) space, a stan parowy (i, j) często daje O(n²) time i O(n²) space.
from functools import cache
@cache
def fibonacci(index: int) -> int:
if index < 2:
return index
return fibonacci(index - 1) + fibonacci(index - 2)
print(fibonacci(10)) # 55
print(fibonacci.cache_info().currsize) # 11 — cache trzyma fib(0)..fib(10)
Pułapka rekrutacyjna: memoizacja może wybuchnąć pamięciowo — cache rośnie z liczbą unikalnych stanów. functools.cache nie ma limitu — dla długiego procesu lepsze bywa lru_cache(maxsize=...) albo iteracyjne DP.
Sortowanie in-place vs out-of-place
list.sort() modyfikuje istniejącą listę i zwraca None — nie tworzy drugiej listy wynikowej. sorted() przyjmuje dowolny iterable i buduje nową listę: O(n) extra space na wynik.
Obie operacje używają Timsort i mają O(n log n) time w typowym zapisie złożoności porównawczej. Wybór dotyczy głównie własności danych: czy wolno zmienić wejście, czy potrzebna jest kopia.
values = [5, 2, 4, 1]
ordered = sorted(values)
print(values) # [5, 2, 4, 1] — niezmieniona
print(ordered) # [1, 2, 4, 5] — nowa lista
values.sort()
print(values) # [1, 2, 4, 5] — wejście ZOSTAŁO zmodyfikowane
Pułapka rekrutacyjna: "in-place" nie zawsze oznacza O(1) całkowitej pamięci. Pythonowy Timsort może używać buforów pomocniczych w worst case, a slice'y, recursion i biblioteki potrafią ukrycie tworzyć kopie.
Generator vs list — pamięć kontra dostęp
Generator produkuje wartości leniwie — utrzymuje O(1) extra space dla strumienia danych. Lista materializuje wszystkie elementy: O(n) space, ale daje len(), indeksowanie i wielokrotne przejścia.
To kompromis throughput vs ergonomia. Generator pasuje do pipeline, plików, dużych zakresów. Lista pasuje gdy potrzebujesz random access, sortowania, wielokrotnej agregacji albo przekazania danych do API oczekującego sekwencji.
def squares(limit: int):
for number in range(limit):
yield number * number
stream = squares(5)
print(next(stream)) # 0
print(next(stream)) # 1
items = list(squares(5))
print(items[3]) # 9 — random access
print(len(items)) # 5 — len() wymaga materializacji
Pułapka rekrutacyjna: generator jest single-pass. Nie ma len() ani indeksowania, a po zużyciu nie odtwarza wartości. Jeśli kod potrzebuje dwóch przebiegów, materializacja listy może być prostsza i mniej podatna na błędy.
Praktyczna decyzja na rozmowie — kiedy czas, kiedy RAM
Na rozmowie zacznij od baseline: time, space, założenia o n, mutowalności danych, typach operacji. Potem pokaż tradeoff: dodatkowy set, cache albo kopia sortowania poprawia czas, ale zwiększa memory footprint.
Preferuj szybkość gdy: n jest duże, lookupów jest wiele, latency krytyczne, pamięć mieści się w budżecie. Oszczędzaj RAM gdy: dane strumieniowe, środowisko ograniczone, cache może rosnąć bez kontroli.
def explain_choice(item_count: int, memory_is_tight: bool) -> str:
if memory_is_tight:
return "prefer streaming or in-place processing"
if item_count > 1_000:
return "prefer auxiliary structures for faster lookups"
return "prefer simple code first"
print(explain_choice(10_000, False)) # prefer auxiliary structures for faster lookups
print(explain_choice(10_000, True)) # prefer streaming or in-place processing
Pułapka rekrutacyjna: nie sprzedawaj jednego Big O jako pełnej odpowiedzi. Dobra decyzja uwzględnia CPython containers, koszt alokacji, mutowanie wejścia, worst case hash table, cache eviction i to, czy wynik musi być ponownie użyty.
Sygnały rozpoznawcze: kiedy time, kiedy space
Sygnał → wybór kompromisu:
"wiele lookupów / repeat queries" → space (set/dict cache)
"streaming / nie mieści się w RAM" → time (single-pass, generator)
"top K / partial sort" → balanced (heap zamiast pełnego sort)
"DP z parowym stanem (i, j)" → time (memoization O(n²) space)
"hot loop, latency krytyczne" → space (precompute, cache)
"single-shot computation, n=10⁶" → time (no need to cache)
"recursive z duplikatami podproblemów" → space (memoization usuwa O(2^n))
Sygnał odwrotny — kiedy NIE memoization: cache rośnie bez kontroli (brak maxsize), mutable arguments (klucze niehashowalne), efekty uboczne (memoization daje stałą odpowiedź dla zmiennego stanu). Szczegóły hashable: Haszowanie w Zadaniach.
Najczęstsze błędy
x in list traktowane jako O(1). Lista to liniowy skan — O(n) per lookup. Mechanizm błędu: pętla for x in big_list: if x in small_list daje O(n*m) zamiast O(n). Naprawa: small_set = set(small_list) raz przed pętlą — O(m) setup + O(1) lookup × n = O(n + m).
Memoization bez maxsize na nieskończonej dziedzinie. @lru_cache bez limitu cache rośnie wraz z liczbą unikalnych argumentów — może zająć całą pamięć dla long-running process. Mechanizm: każde unikalne wywołanie dodaje wpis. Naprawa: @lru_cache(maxsize=128) lub @lru_cache(maxsize=None) świadomie tylko dla bounded domain.
„In-place" ≠ O(1) total space. list.sort() jest in-place, ale Timsort wewnętrznie może użyć O(n) buffer dla scalania. Mechanizm błędu: kandydat ogłasza „in-place więc O(1) pamięci" — w rzeczywistości recursion stack i pomocnicze tablice się liczą. Naprawa: zawsze rozróżniaj „input mutated in place" vs „auxiliary memory used".
Generator single-pass jako zamiennik listy. Generator po wyczerpaniu nie iteruje drugi raz, brak len(), brak indeksowania. Mechanizm błędu: gen = (x*2 for x in items); print(len(gen)) rzuca TypeError; pierwsza pętla iteruje, druga widzi pusty generator. Naprawa: list(gen) materialize gdy potrzebujesz wielokrotnego dostępu.
Mutowanie wejścia bez ostrzeżenia. list.sort() modyfikuje listę w miejscu, sorted() zwraca nową — łatwo pomylić. Mechanizm błędu: funkcja oczekiwała kopii, dostała zmodyfikowany oryginał, dalsza logika dostaje błędny stan. Naprawa: jasna konwencja w API — modyfikujące funkcje zwracają None, czyste zwracają nową strukturę.
Najczęściej zadawane pytania
Czym różni się time complexity od space complexity?
Time opisuje liczbę operacji jako funkcja n (ile pracy). Space opisuje dodatkową pamięć potrzebną poza wejściem. Algorytm może być szybki ale pamięciożerny (memoizacja, hash table) albo odwrotnie (generator, in-place sort).
Kiedy warto zamienić listę na set dla detekcji duplikatów?
Gdy n jest duże i lookupów jest wiele. set wymaga O(n) extra space, ale lookup spada z O(n) do średnio O(1). Dla małych list (< 100 elementów) prostsza lista jest wystarczająca i czytelniejsza.
Czy memoizacja zawsze jest dobrym pomysłem?
Nie. Memoizacja zamienia time za space. Cache rośnie z liczbą unikalnych stanów. Dla Fibonacci to OK (liniowo), ale dla DP z parowym stanem (i, j) cache to O(n²) pamięci. Używaj lru_cache(maxsize=...) żeby ograniczyć rozmiar.
Co znaczy "in-place" i czy to zawsze oznacza O(1) pamięci?
"In-place" = algorytm modyfikuje wejście zamiast tworzyć kopię. ALE nie zawsze oznacza O(1) total space. list.sort() jest in-place, ale Timsort wewnętrznie może użyć O(n) buffer w worst case. Recursion i biblioteki mogą ukrycie tworzyć kopie.
Kiedy generator zamiast listy?
Generator gdy: dane strumieniowe (linie pliku), pipeline transformacji, zużywasz wartości raz, n duże i RAM krytyczny. Lista gdy: potrzebujesz len(), indeksowania, sortowania, wielokrotnej iteracji albo API oczekuje sekwencji.
Jak odpowiedzieć na rozmowie "co wybierzesz: pamięć czy czas?"
Najpierw pytaj o kontekst: rozmiar n, latency requirements, środowisko (RAM constrained?), czy wynik użyty raz czy wiele razy. Potem zaproponuj baseline i pokaż jeden tradeoff w obie strony — to demonstruje rozumienie kompromisów, nie tylko znajomość algorytmu.
Powiązane tematy
- Big O w 10 Minut — Notacja Złożoności — kontekst dla
O(n)time/space; sześć klas złożoności i sygnały rozpoznawcze. - Haszowanie w Zadaniach — Wzorzec na Rozmowie — najczęstszy przykład trade-offu „pamięć za czas": hash set/map dla
O(1)lookup kosztemO(n)extra space. - Algorytmy Sortowania — quicksort
O(log n)stack vs merge sortO(n)buffer; wybór zależy od priorytetu time vs space.
Sprawdź swoją wiedzę quizem
Najlepszy sposób na utrwalenie intuicji o kompromisach time/space to przerobienie 15 pytań w formie quizu. Sprawdź gdzie masz luki przed rozmową.
Rozwiąż quiz: Czas i pamięć w Pythonie
Możesz też wgrać własny PDF z notatkami (do 20 MB) na odpytywarka.pl — w 30-60 sekund wygenerujemy quiz z 15 pytaniami jednokrotnego wyboru z pierwszych 3 stron dokumentu, za darmo i bez rejestracji do rozwiązania.