Čo je to časová zložitosť?

Občas sa možno stretneš s názorom, že programovanie je vlastne len zamaskovaná matematika. Sčasti je to pravda, ale je tu jeden dôležitý rozdiel. V matematike neexistuje "lepší dôkaz" a "horší dôkaz". Každý korektný postup, ktorým sa dostaneme k výsledku, je rovnako dobrý. V programovaní je to ináč.

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: Pozrime sa na tieto dva programy, ktoré počítajú súčet prvých $N$ prirodzených čísel. Ktorý by si skôr použil? A prečo?

var i, N, sum : longint;                                             

begin                                                                
   readln(N);                                                        
   sum := 0;                                                         
   for i:=1 to N do sum := sum + i;                                  
   writeln(sum);                                                     
end.                                                                 

var i, N, sum : longint;                                             

begin                                                                
   readln(N);                                                        
   sum := (N * (N+1)) div 2;                                         
   writeln(sum);                                                     
end.                                                                 

V tomto prípade je odpoveď jasná – ten druhý, lebo je rýchlejší. Kým prvý potrebuje na vypočítanie výsledku rádovo $N$ krokov, druhý ich potrebuje stále rovnako veľa, bez ohľadu na to, aké veľké je $N$. (Aj ty by si určite na súčet prvých $10\,000$ čísel použil ten druhý spôsob...)

V praxi sa s potrebou rýchlych algoritmov stretneš úplne na každom kroku. Ked si otvoríš schránku s e-mailami, nechce sa ti asi hodinu čakať, kým ich počítač usporiada a vypíše. Pri vyhľadávaní slova v texte by si tiež chcel od počítača okamžitú odozvu. A aj "vo svete biznisu" je to tak. Napríklad také banky si denne posielajú toľko rôznych správ (napríklad platobných príkazov), že keby ich spracúvanie bolo príliš pomalé, jednoducho by sa im začali hromadiť.

A práve preto sa vymyslela teória, ktorej sa začalo hovoriť časová zložitosť algoritmov. O čo v nej ide? To, čo chceme dosiahnuť, je vedieť o danom algoritme povedať, ako veľa údajov dokáže v rozumnom čase spracovať. A úplne najradšej by sme boli, keby sme to vedeli povedať len tak, z pohľadu na algoritmus, bez toho, aby sme ho museli programovať a spúšťať.

Ako na to? Na algoritmus sa budeme dívať ako na postupnosť krokov. Budeme sa snažiť odhadnúť, koľko krokov algoritmus potrebuje v závislosti od veľkosti vstupu, ktorý mu dáme.

Všimnime si napríklad program, ktorý vypočíta kombinačné číslo $n \choose k$ (počet spôsobov, ktorými sa dá vybrať $k$-členná skupina spomedzi $n$ ľudí) tak, že postupne počíta riadky Pascalovho trojuholníka:

var trojuholnik : array[0..100,0..100] of longint;                   
    n, k : longint;                                                  
    i, j : longint;                                                  

begin                                                                
   readln(n,k);                                                      
   for i:=0 to n do begin     {cyklus 1}                             
      for j:=0 to i do begin  {cyklus 2}                             
         {vypocet}                                                   
         if (j=0) or (j=i) then                                      
            trojuholnik[i][j] := 1                                   
         else                                                        
            trojuholnik[i][j] :=                                     
               trojuholnik[i-1][j-1] + trojuholnik[i-1][j];          
      end;                                                           
   end;                                                              
   writeln(trojuholnik[n][k]);                                       
end.                                                                 

(Ak potrebuješ vysvetlenie, čo že vlastne ten program ráta: trojuholnik[i][j] bude počet spôsobov, ktorými môžeme vybrať $j$ spomedzi $i$ ľudí. "Vybrať všetkých" aj "nevybrať nikoho" sa dá práve jedným spôsobom. Vo všeobecnom prípade, ak máme spomedzi $i$ ľudí vybrať $j$, rozlíšime dva prípady: Ak vyberieme $i$-teho, musíme spomedzi ostatných $i-1$ ľudí vybrať $j-1$, na to máme trojuholnik[i-1][j-1] možností. Ak $i$-teho nevyberieme, musíme spomedzi ostatných $i-1$ ľudí vybrať všetkých $j$, na to máme trojuholnik[i-1][j] možností.)

Skúsme nejako odhadnúť, koľko krokov by sme spravili, keby sme (pre nejaké konkrétne $n$, $k$) simulovali tento program ručne. Vidíme, že hlavnú časť programu tvoria dva cykly v sebe, v ktorých niečo počítame. Premenná $i$ ide postupne od $0$ po $n$, pričom zakaždým, keď zväčšíme $i$, vykoná sa celý vnútorný cyklus. Namiesto toho, aby sme teraz pracne počítali, ktorý príkaz sa koľkokrát vykoná, skúsime to len zhora odhadnúť. V najhoršom možnom prípade (pre $i=n$) sa príkaz vo vnútornom cykle vykoná ($n+1$)-krát. Môžeme teda vysloviť nasledovné pozorovanie:

Premennú i zväčšíme rádovo $n$-krát. Zakaždým sa vykoná celý vnútorný cyklus, v ktorom premmenú j zväčšíme nanajvýš rádovo $n$-krát, a zakaždým vykonáme výpočet vo vnútri cyklu. Samotný výpočet vo vnútri cyklu sa teda vykoná nanajvýš rádovo $\left(n^2\right)$-krát. A teda aj na odsimulovanie celého programu nám stačí spraviť nanajvýš rádovo $n^2$ krokov.

A presne takýto odhad (samozrejme čím tesnejší, tým lepšie) je to, čomu sa začalo hovoriť časová zložitosť algoritmu. Nie je to presné, ale dáva nám to dostatočne veľa informácií o ňom. Napríklad vieme povedať, že ak pre $n=200$ pobeží na našom počítači tento program $0.1$ sekundy, tak pre $n=400$ (teda dvakrát také veľké) pobeží náš program rádovo $0.4$ sekundy (teda $2^2$-krát tak dlho).

Matematicky sa zložitosť zapisuje použitím veľkého $O$. Napríklad výrok časová zložitosť programu je $O\left(n^2\right)$ znamená to isté, ako náš vyššie uvedený záver, že program vykoná nanajvýš rádovo $n^2$ krokov.

Podobne môžeme hovoriť o pamäti potrebnej na beh programu. Napríklad na to, aby náš starý známy program počítajúci Pascalov trojuholník fungoval, musí mať pole trojuholnik rozmery aspoň $(n+1)$ krát $(n+1)$. Veľkosť potrebnej pamäte je teda nejaká kvadratická funkcia od $n$. Opäť, nezaujíma nás, ako presne táto funkcia vyzerá, stačí nám vedieť, rádovo ako rýchlo rastie. Môžeme teda povedať, že aj pamäťová náročnosť (zložitosť) nášho programu je $O\left(n^2\right)$.

(Poznámka. Na vypočítanie nasledujúceho riadku trojuholníka nám stačí pamätať si len ten predchádzajúci. Náš program by sa teda mal dať upraviť na taký, ktorý bude mať pamäťovú zložitosť len $O(n)$. Skús takýto program napísať. Aká bude časová zložitosť tohto nového programu?)

Na záver: Značenie $O(f(n))$, ktoré sme si tu predstavili, sa dá formálne definovať, počítanie zložitosti je predsa len o niečo exaktnejšia oblasť, ako by sa mohlo zdať. Pre jednoduché programy si však vystačíme s takýmto intuitívnym chápaním "veľkého $O$". Viac na túto tému nájdete v nasledujúcom článku Úvod do teórie časovej zložitosti.