Keď hodnotíme kvalitu algoritmu, nestačí sa pozrieť len na rýchlosť. Algoritmus môže byť rýchly, ale zároveň spotrebovávať obrovské množstvo pamäte. Priestorová zložitosť meria pamäťové nároky algoritmu.
Čo je priestorová zložitosť?
Priestorová zložitosť vyjadruje, koľko extra pamäte algoritmus potrebuje v závislosti od veľkosti vstupu N. Rovnako ako časová, používa Big O notáciu.
Pozor: zvyčajne hovoríme o extra pamäti (auxiliary space) — teda pamäti nad rámec vstupných dát.
O(1) — Konštantná priestorová zložitosť
Algoritmus používa rovnaké množstvo extra pamäte bez ohľadu na veľkosť vstupu:
def nájdi_maximum(zoznam):
maximum = zoznam[0] # jedna premenná — O(1) extra pamäte
for prvok in zoznam:
if prvok > maximum:
maximum = prvok
return maximum
Bez ohľadu na to, či má zoznam 10 alebo 10 000 prvkov, algoritmus používa len niekoľko premenných (maximum, prvok) — konštantné množstvo pamäte.
Algoritmy s priestorovou zložitosťou O(1) sa nazývajú in-place (na mieste). Triediace algoritmy ako bubble sort, selection sort a insertion sort sú in-place — triedia priamo v pôvodnom zozname.
O(N) — Lineárna priestorová zložitosť
Pamäťové nároky rastú lineárne s N:
def zdvojnasob_zoznam(zoznam):
novy = [] # nový zoznam — O(N) extra pamäte
for prvok in zoznam:
novy.append(prvok * 2)
return novy
Ak má vstupný zoznam N prvkov, výstupný zoznam tiež N prvkov → O(N) extra pamäte.
def reverz_retazca(retazec):
znaky = list(retazec) # O(N) — kópia znakov
znaky.reverse()
return ''.join(znaky)
O(N²) a vyššie
Dvojrozmerné štruktúry (matice, tabuľky) majú O(N²) priestorovú zložitosť:
def vytvor_maticu(n):
matica = []
for i in range(n):
riadok = [0] * n # N prvkov na riadok
matica.append(riadok) # N riadkov
return matica
# Celkovo N × N = N² prvkov → O(N²)
Rekurzia a zásobník volaní
Rekurzívne funkcie spotrebovávajú pamäť pre každé volanie (zásobník volaní):
def faktorial(n):
if n <= 1:
return 1
return n * faktorial(n - 1) # každé volanie zaberie miesto v pamäti
Pre faktorial(100) sa vytvorí 100 vrstiev zásobníka → O(N) priestorová zložitosť, hoci kód vyzerá úsporne.
Hlboká rekurzia môže spôsobiť Stack Overflow — pretečenie zásobníka. Python má predvolený limit ~1000 rekurzívnych volaní. Pre veľké N je bezpečnejší iteratívny prístup (s cyklom).
Kompromis medzi časom a pamäťou
Často existuje kompromis: môžeš algoritmus urýchliť za cenu väčšej pamäte, alebo ušetriť pamäť za cenu pomalšieho behu.
Príklad — memoizácia:
# Bez memoizácie — O(2ᴺ) čas, O(N) pamäť (zásobník)
def fib_pomalé(n):
if n <= 1:
return n
return fib_pomalé(n - 1) + fib_pomalé(n - 2)
# S memoizáciou — O(N) čas, O(N) pamäť
pamat = {}
def fib_rýchle(n):
if n in pamat:
return pamat[n] # vráti z pamäte
if n <= 1:
return n
pamat[n] = fib_rýchle(n - 1) + fib_rýchle(n - 2)
return pamat[n]
Memoizácia ukladá výsledky výpočtov — vyžaduje viac pamäte (O(N)), ale dramaticky znižuje čas (z O(2ᴺ) na O(N)).
V praxi sa zvyčajne uprednostňuje rýchlosť pred pamäťou, pretože pamäť je dnes relatívne lacná. Ale pri mobilných zariadeniach alebo vstavaných systémoch (IoT) môže byť pamäť kriticky obmedzená.
Prehľad zložitostí bežných algoritmov
| Algoritmus | Časová zložitosť | Priestorová zložitosť |
|---|---|---|
| Lineárne vyhľadávanie | O(N) | O(1) |
| Binárne vyhľadávanie | O(log N) | O(1) |
| Bublinkové triedenie | O(N²) | O(1) — in-place |
| Merge sort | O(N log N) | O(N) — potrebuje kópiu |
| Python sorted() | O(N log N) | O(N) |
Analýza skutočného programu
def duplikáty(zoznam):
videne = set() # O(N) pamäte v najhoršom prípade
for prvok in zoznam:
if prvok in videne: # O(1) vyhľadávanie v množine
return True
videne.add(prvok)
return False
# Čas: O(N), Pamäť: O(N)
Cvičné príklady
Prečo sa triedenie vkladaním (insertion sort) považuje za in-place algoritmus a aká je jeho priestorová zložitosť?
Zobraziť odpoveď
Algoritmus A má časovú zložitosť O(N log N) a priestorovú O(N). Algoritmus B má časovú O(N²) a priestorovú O(1). Kedy by si uprednostnil A a kedy B?