Tento článok je stručný trochu formálnejší úvod do časovej zložitosti algoritmov. Povieme si, čo to je, načo to je dobré a ako sa to počíta. Niekedy časom sa dostaneme aj k formálnym definíciám, ale začneme tým, že sa zamyslíme, ako niektoré veci fungujú. Totiž dôležitejšie, ako poznať definície je rozumieť motivácii, ktorá sa za nimi skrýva.
Zjavne nie všetky programy, ktoré riešia ten istý problém, sú rovnako dobré. Máme napríklad viacero operačných systémov a rozdiely medzi nimi sú priam priepastné, všakže? Alebo len taký jednoduchší príklad: dva programy, ktoré počítajú súčet prvých $N$ prirodzených čísel. Ktorý by ste skôr použili – taký, čo ich v cykle od $1$ do $N$ sčíta, alebo taký, ktorý len dosadí $N$ do vzorca súčet $= \frac{N\left( N+1 \right)}{2} $? A prečo?
Pozrime sa teraz podrobnejšie na trochu zložitejší príklad.
Príklad 1. V práci ste dostali za úlohu napísať program, ktorý bude spracúvať záznamy o klientoch. Naprogramovali ste dva rôzne algoritmy a vyskúšali ste ich na niekoľkých "testovacích" sadách údajov. Pre každú ste si zapísali čas, ktorý tvoje programy potrebovali na jej spracovanie. Dostali ste nasledujúcu tabuľku:
| počet záznamov | 10 | 20 | 50 | 100 | 1000 | 5000 |
|---|---|---|---|---|---|---|
| algoritmus 1 | 0.00s | 0.01s | 0.05s | 0.47s | 23.92s | 47min |
| algoritmus 2 | 0.05s | 0.05s | 0.06s | 0.11s | 0.78s | 14.22s |
Tabuľka 1. Rýchlosť dvoch fiktívnych algoritmov.
V praxi väčšinou vieme vopred odhadnúť veľkosť spracúvaných údajov. Vedeli by sme teda povedať, ktorý z týchto dvoch algoritmov je pre tvoje potreby lepší. Takéto riešenie sa síce môže páčiť firme, ktorá ťa zamestnala, ty si ale zbytočne napísal/a jeden z tých programov. Bolo by lepšie, keby si vedela/a hodnoty v tabuľke aspoň približne odhadnúť bez toho, aby si algoritmy musel/a implementovať a spustiť.
S rovnakou situáciou sa stretáme aj v programátorských súťažiach. Máme zadanú (maximálnu) veľkosť vstupných údajov. Ak vymyslíme algoritmus, ktorý zadanú úlohu rieši, stojíme pred otázkou: Bude dostatočne rýchly? Oplatí sa mi ho implementovať, alebo sa mám snažiť vymyslieť niečo lepšie? Ak nebodaj viem viac algoritmov, ktoré tento problém riešia, ktorý z nich je lepší?
Tu sa dostávame k otázke: Ako porovnávať algoritmy? Skôr, ako ju zodpovieme vo všeobecnosti, vráťme sa k Tabuľke 1. Pri pohľade na ňu sa zdá byť takmer isté, že pre viac ako $1000$ záznamov už bude algoritmus 2 podstatne rýchlejší od algoritmu 1. Inými slovami, algoritmus 1 je rýchlejší len na zanedbateľne malej množine vstupov, pre skoro všetky možné veľkosti vstupu je rýchlejší algoritmus 2.
Neskôr ukážeme, že takáto situácia nastane skoro vždy – dva zadané algoritmy sú buď približne rovnako rýchle, alebo jeden je pre skoro všetky veľkosti vstupu od toho druhého rýchlejší. Toto sa budeme neskôr snažiť formálne definovať.
Ak sa na chvíľu zamyslíte nad Príkladom 1, malo by byť jasné, že pre daný problém existuje aj algoritmus, ktorého rýchlosť je v nasledujúcej tabuľke:
| počet záznamov | 10 | 20 | 50 | 100 | 1000 | 5000 |
|---|---|---|---|---|---|---|
| algoritmus 3 | 0.00s | 0.01s | 0.05s | 0.11s | 0.78s | 14.22s |
Tabuľka 2. Rýchlosť nového fiktívneho algoritmu.
Myšlienka: Začni tým, že sa pozrieš na počet záznamov. Ak je malý, použi algoritmus 1, inak algoritmus 2.
Môže to znieť až prekvapivo, ale podobné finty sa v praxi naozaj
používajú. Napríklad väčšina implementácií rôznych triediacich funkcií
(ako napr. sort() v STL) používa vylepšenie: ak už triedim málo prvkov,
použije sa InsertSort. Ten síce potrebuje až kvadraticky veľa porovnaní,
ale je natoľko jednoduchý, že pre malé vstupy je rýchlejší.