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ť: $t=a\cdot n+b$
2. logaritmicko-lineárna: $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:

Funkcia počtu operácií	20	40	60	80	100	200	500	1000
n	20 µs	40 µs	60 µs	80 µs	100 µs	200 µs	500 µs	1000 µs
n.log n	86 µs	0,2 ms	0,35 ms	0,5 ms	0,7 ms	1,5 ms	4,5 ms	10ms
n2	0,4 ms	1,6 ms	3,6 ms	6,4 ms	10 ms	40 ms	0,25s	1 s
n3	8 ms	64 ms	0,22 ms	0,5 ms	1 s	8 s	125 s	17 min
n4	0,16 s	2,56s	13 s	41 s	100 s	27 min	17 h	11,6 dní
2n	1 s	11,7 dní	36 600 r	3,6.109 r
n!	77 000 r

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 $n\cdot log(n)$.