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):
- lineárna zložitosť: t=a.n+b
- logaritmicko lineárna: t=a.n.log n+b.n+c
- 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 µ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.
 |
Tento článok o počítačoch a súvisiacich veciach je zatiaľ príliš krátky (tzv. "výhonok"). Môžeš pomôcť Wikipédii rozšíriť ho tak, že hore klikneš na záložku "úprava" (alebo alternatívne sem) a dopíšeš alebo zmeníš text. |
