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):
lineárna zložitosť: 
logaritmicko-lineárna: 
polynomiálna: t je funkciou nejakého polynómu n
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 µs1000 µ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 ms1,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 r3,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 n2, ale existujú aj algoritmy triedenia so zložitosťou .


Kategória:Matematika
Kategória:Informatika