Úvod do výpočtovej zložitosti

Čo je výpočtová zložitosť a prečo je dôležitá?

Každý program alebo algoritmus potrebuje určité množstvo výpočtových zdrojov – hlavne čas a pamäť. Keď riešime nejaký problém, často existuje viacero algoritmov, ktoré vedú k rovnakému výsledku, ale niektoré sú výrazne rýchlejšie ako iné. Ak chceme, aby náš program bežal efektívne aj pre veľké vstupy, potrebujeme pochopiť, ako sa jeho výkon mení so zväčšujúcim sa množstvom dát. A pretože objem dát sa v programovaní dá najľahšie vysvetliť pomocou množín, vyučovanie výpočtovej zložitosti obsahuje skoro vždy iba množiny a cykly.

Predtým ako sa pustíme do konkrétneho algoritmu, si najskôr musíme stanoviť niekoľko základných pojmov:

• Časová zložitosť – hovorí nám, koľko operácií vykoná algoritmus v závislosti od veľkosti vstupu (označujeme ju často ako $O(f(n))$).
• Pamäťová zložitosť – koľko pamäte algoritmus potrebuje počas behu.
• Najhorší, priemerný a najlepší prípad – hodnotíme algoritmus nielen pre optimálne podmienky, ale aj pre tie najhoršie možné situácie.

Medzi ďalšie dva dôležité pojmy patria:

1. Asymptotická notácia: používa sa označenie $O(f(n))$ (tzv. „Big-O“ notácia), ktoré vyjadruje ako sa výkon algoritmu mení pri zväčšujúcom sa vstupe $n$;
2. Triedy zložitosti: napríklad, existuje trieda P (predstavuje všetky problémy, ktoré vieme riešiť efektívne) a NP (problémy, ktoré vieme overiť rýchlo, ale ich riešenie môže byť veľmi pomalé);