Výpočtová zložitosť

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání

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:

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ť:
  2. logaritmicko lineárna:
  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.