Časová náročnosť algoritmu
alebo
Načo hľadať algoritmus s lepšou triedou zložitosti a prečo nezáleží na multiplikatívnej konštante.
Predpokladajme, že počítač urobí 109 operácií
za sekundu. Aký bude čas výpočtu pre rôzne veľký vstup a triedu zložitosti?
Pre porovnanie: Vek vesmíru sa odhaduje rádovo na 1010 rokov,
počet elementárnych častíc vo vesmíre na 10100.
| n | O(log n) | O(n) | O(n log n) | O(n2) | O(n3) | O(n6) | O(2n) | O(n!) |
|---|---|---|---|---|---|---|---|---|
| 10 | 0 ms | 0 ms | 0 ms | 0 ms | 0 ms | 1 ms | 0 ms | 4 ms |
| 20 | 0 ms | 0 ms | 0 ms | 0 ms | 0 ms | 64 ms | 1 ms | 77 rokov |
| 100 | 0 ms | 0 ms | 0 ms | 0 ms | 1 ms | 17 minút | ≈1013 rokov | ≈10141 rokov |
| 1000 | 0 ms | 0 ms | 0 ms | 1 ms | 1 s | 32 rokov | ≈10284 rokov | |
| 106 | 0 ms | 1 ms | 14 ms | 17 minút | 32 rokov | ≈1019 rokov | ||
| 1012 | 0 ms | 17 minút | 8 hodín | ≈107 rokov | ≈1019 rokov | ≈1055 rokov |
A aký veľký problém stihneme na tom istom počítači vyriešiť v určenom čase?
| T(n) | O(log n) | O(n) | O(n log n) | O(n2) | O(n3) | O(n6) | O(2n) | O(n!) |
|---|---|---|---|---|---|---|---|---|
| sekunda | ≈e109 | ≈109 | ≈107 | 31622 | 1000 | 31 | 29 | 12 |
| hodina | ≈1012 | ≈1011 | ≈106 | 15326 | 123 | 41 | 15 | |
| deň | ≈1013 | ≈1012 | ≈107 | 44208 | 210 | 46 | 16 | |
| rok | ≈1016 | ≈1015 | ≈108 | 315938 | 562 | 54 | 18 | |
| vek vesmíru | ≈1026 | ≈1024 | ≈1013 | ≈109 | ≈28000 | 88 | 26 |