Č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 príkladu si musíme stanoviť dva základné pojmy:
- Asymptotická notácia: používa sa označenie (tzv. „Big-O“ notácia), ktoré vyjadruje ako sa výkon algoritmu mení pri zväčšujúcom sa vstupe .
- 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é).