Výpočtová zložitosť

Z Wikipédie

Výpočtová zložitosť alebo tiež 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:

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.n+b
  2. logaritmicko lineárna: t=a.n.log n+b.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ácii 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 n.log n.