Pamäťová zložitosť

Hoci sa o O-notácii najčastejšie hovorí v súvislosti s časovou zložitosťou (ako rýchlo algoritmus beží), je rovnako užitočná aj na odhad pamäťovej zložitosti (koľko pamäte algoritmus spotrebuje).

Pamäťová zložitosť vyjadruje, aké množstvo dodatočnej pamäte (okrem vstupných dát) potrebuje algoritmus na svoje vykonanie ako funkcia veľkosti vstupu.

Pamäťová zložitosť nám pomáha identifikovať algoritmy, ktoré sú pamäťovo náročné a môžu spôsobiť problémy (napr. nedostatok pamäte), umožňuje nám predpovedať, ako sa bude spotreba pamäte meniť s rastúcou veľkosťou vstupu.

Jednoduchý príklad

Predstavte si, že máte zoznam $n$ čísel a chcete ich uložiť do poľa pre ďalšie spracovanie. Každý prvok v poli spotrebuje určité, konštantné množstvo pamäte. Ak máme $n$ prvkov, celková spotreba pamäte pre naše pole bude priamo úmerná $n$.

Preto hovoríme, že pamäťová zložitosť takéhoto algoritmu je $O(n)$. Čím viac čísel uložíme, tým lineárne viac pamäte potrebujeme.

Iné príklady:

• $O(1)$ (konštantná pamäť): Algoritmus, ktorý potrebuje stále rovnaké množstvo pamäte bez ohľadu na veľkosť vstupu. Napríklad, na sčítanie dvoch čísel si potrebuje pamätať len dve premenné a výsledok.
• $O(n^2)$ (kvadratická pamäť): Algoritmus, ktorý vytvorí napríklad maticu veľkosti $n \times n$. Každá bunka matice spotrebuje pamäť, takže celkovo $n^2$ pamäte.