Výpočtová zložitosť

Výpočtová zložitosť alebo výpočtová náročnosť je pojem z teórie algoritmov, vyjadruje nakoľko je výpočet podľa zvoleného algoritmu zložitý. Výpočtovú zložitosť študuje teória zložitosti.

Výpočtová zložitosť má dve základné miery:

• časová zložitosť
• pamäťová zložitosť

Optimalizácia algoritmu sa týka minimalizácie jednej alebo obidvoch mier zložitosti.

Výpočtová zložitosť algoritmu priamo nesúvisí so zložitosťou samotného algoritmu z ľudského pohľadu. Algoritmus môže byť veľmi jednoduchý na pochopenie i implementáciu, napriek tomu môže byť jeho výpočtová zložitosť veľká a naopak.

Druhy výpočtovej zložitosti v závislosti od počtu vstupných prvkov n, (a, b, c sú konštanty, t je čas):

1. lineárna zložitosť: ${\displaystyle t=a\cdot n+b}$
2. logaritmicko-lineárna: ${\displaystyle t=a\cdot n\cdot log(n)+b\cdot n+c}$
3. polynomiálna: t je funkciou nejakého polynómu n
4. algoritmy so zložitosťou väčšou, než je polynomiálna.

Za rýchle algoritmy sa pokladajú prvé tri druhy.

Ilustráciou zložitosti je nasledujúca tabuľka, predpokladajme, že vykonanie jednej operácie trvá jednu mikrosekundu:

Z uvedenej tabuľky vidno, že aj keby sme rýchlosť operácií zväčšili 1000x, posledný algoritmus by bol tak či tak neriešiteľný v rozumnom čase a predposledný pre väčšie n tiež.

Tú istú úlohu možno väčšinou riešiť rôznymi algoritmami s rozličnou výpočtovou zložitosťou. Napríklad triedenie sa dá jednoducho implementovať s výpočtovou zložitosťou n², ale existujú aj algoritmy triedenia so zložitosťou ${\displaystyle n\cdot log(n)}$.

Tento článok týkajúci sa počítačov je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš.