Úvod do teórie časovej zložitosti

Tento článok je stručný ú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.

Načo je to dobré?

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 si dostal za úlohu napísať program, ktorý bude spracúvať záznamy o klientoch. Naprogramoval si dva rôzne algoritmy a vyskúšal ich na niekoľkých "testovacích" sadách údajov. Pre každú si si zapísal čas, ktorý tvoje programy potrebovali na jej spracovanie. Dostal si nasledujúcu tabuľku:

Tabuľka 1. Rýchlosť dvoch fiktívnych algoritmov.

V praxi väčšinou vieme vopred odhadnúť veľkosť spracúvaných údajov. Vedel by si 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 jeden z tých programov. Bolo by lepšie, keby si vedel hodnoty v tabuľke aspoň približne odhadnúť bez toho, aby si algoritmy musel 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ť.

Finta

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:

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ší.

Čo je to efektívnosť?

Príklad 2. Zoberme si konkrétny program – implementáciu jednoduchého triedenia MinSort.

for (int i=0; i<N; i++)
  for (int j=i+1; j<N; j++)
    if (A[i] > A[j])
      swap( A[i], A[j] );

Ak by nám niekto povedal konkrétny vstup, ktorý tento algoritmus dostane (v našom prípade teda hodnotu $N$ a obsah poľa A), vedeli by sme presne spočítať počet krokov, ktoré náš algoritmus spraví. Dokonca by sme vedeli presne povedať počet inštrukcii, ktoré vykoná procesor počas jeho behu. Takýto prístup však nie je veľmi praktický, keďže v praxi je možných vstupov priveľa a nemôžeme ich vyskúšať všetky.

Čo presne nás teda bude zaujímať? Sú nejaké "dôležité" vstupy, na ktoré sa stačí pozrieť, alebo ako? Väčšinou to, čo budeme chcieť zistiť, bude dĺžka behu programu v najhoršom možnom prípade. Hm, čo je to ale najhorší možný prípad? Veď určite môžeme program donútiť bežať aj dlhšie – jednoducho tak, že mu dáme väčší vstup...

Už zmysluplnejšie otázky sú nasledovné: Spomedzi všetkých vstupov so 700 prvkami, na ktorom pobeží náš program najdlhšie? Ako dlho to bude? Ako rýchlo rastie tento potrebný čas v závislosti od počtu prvkov, resp. od veľkosti vstupu?

Pár formálnych detailov o veľkosti vstupu

Začali sme tu spomínať "veľkosť vstupu". Čo to vlastne je? Formálne ju môžeme definovať ako počet znakov potrebných na jeho zapísanie. V našej situácii je teda totožná s veľkosťou vstupného súboru, uloženého na disku.

Často sa stretneme s tým, že súčasťou vstupu je jedno číslo, ktoré je úmerné jeho veľkosti. Napr. v Príklade 2 bude veľkosť vstupného súboru (ktorý obsahuje $N$ a čísla z poľa A ) rádovo $4N+4$. Presné číslo závisí od architektúry systému, ale vždy bude veľkosť vstupu lineárna od $N$.

V podobných prípadoch môžeme pre jednoduchosť za veľkosť vstupu považovať toto číslo. Preto napríklad v príkladoch o poliach či reťazcoch považujeme za veľkosť vstupu ich dĺžku. Všimnime si, že v grafových úlohách môže veľkosť vstupu závisieť od dvoch čísel: počtu vrcholov ($N$) a počtu hrán ($M$).

V podobnom duchu budeme vo zvyšku tohto textu používať na označenie veľkosti vstupu písmeno $N$.

Pozor ale na jeden nepríjemný špeciálny prípad. Na zapísanie jediného (veľkého) čísla nám stačí priestor logaritmický od jeho veľkosti. Totiž pripísaním ďalšej cifry na koniec sa číslo zdesaťnásobí, ale jeho dĺžka zväčší len o $1$. Teda napríklad na zapísanie čísla $123456$ nám stačí rádovo $\log_{10}\left( 123456 \right)$ cifier. Preto napríklad triviálny algoritmus na testovanie prvočíselnosti nepovažujeme za polynomiálny algoritmus – jeho dĺžka behu totiž nie je polynomiálna od veľkosti vstupu. (Ak si tomuto odseku nerozumel, nevadí, neskôr sa k tomu ešte vrátime.)

Ako "odmerať" efektívnosť?

Už sme si povedali, že pre zadaný konkrétny vstup vieme algoritmus odsimulovať a spočítať počet krokov, ktoré spraví. Predstavme si, že toto spravíme pre všetky možné vstupy, ktoré majú veľkosť nanavýš $N$. Následne nájdeme najhorší spomedzi nich, t. j. ten, ktorý donúti náš algoritmus urobiť najviac krokov. Označme tento počet krokov $f\left( N \right)$. Túto funkciu budeme volať časová zložitosť algoritmu.

Inými slovami, na spracovanie ľubovoľného vstupu veľkosti najviac $N$určite stačí spraviť $f\left( N \right)$ krokov.

Vráťme sa k algoritmu z Príkladu 2. Aký je najhorší vstup veľkosti najviac $N$? Inými slovami, ktoré najviac $N$-prvkové pole si vynúti najviac krokov výpočtu? Ľahko si všimneme, že:

• prvý krok sa vykoná práve $N$-krát,
• druhý a tretí krok sa vykonajú práve $\frac{N\left( N - 1 \right)}{2} $-krát,
• štvrtý krok sa vykoná najviac $\frac{N\left( N - 1 \right)}{2} $-krát.

Nuž a zjavne ak budú na začiatku prvky poľa A v klesajúcom poradí, štvrtý krok sa zakaždým vykoná. Toto je teda najhorší možný vstup. Náš algoritmus na ňom spraví $\frac{3 N\left( N - 1 \right)}{2} + N = 1.5 N^2 - 0.5N $krokov. Teda jeho časová zložitosť je $f\left( N \right)= 1.5 N^2 - 0.5N $.

Je pomerne očividné, že takto určiť presnú časovú zložitosť pre zložitejší algoritmus by bolo ťažké, ak nie nemožné. Ukazuje sa ale, že to nie je ani nutné. V našom príklade môžeme napríklad zanedbať člen $-0.5N$. V porovnaní s $1.5N^2$ je totiž zanedbateľný a takmer neovplyvní čas behu programu. Na to, aby sme vedeli posúdiť rýchlosť nášho programu, nám bohate stačí výsledok: "$f\left( N \right)$ je približne rovné $1.5N^2$". Ako ukážeme o chvíľu, ani na konkrétnej konštante $1.5$ príliš nezáleží.

Predstavme si dva algoritmy: jeden s časovou zložitosťou $N^2$, druhý $0.001N^3$. Ľahko vypočítame, že pre $N$ väčšie ako $1\,000$ je už prvý algoritmus rýchlejší – a s rastúcim $N$ sa tento rozdiel rýchlo zväčšuje. Kým prvý algoritmus vyrieši vstup veľkosti $N = 20\,000$ za niekoľko sekúnd, druhý už bude potrebovať minúty.

Zjavne podobná situácia nastane vždy, keď jedna z funkcii udávajúcich časovú zložitosť rastie asymptoticky rýchlejšie ako druhá. (T. j. keď pre $N$ idúce do nekonečna ide aj podiel týchto dvoch funkcií do nekonečna.) Bez ohľadu na konkrétne konštanty bude algoritmus s časovou zložitosťou $C\cdot N^2$ lepší od algoritmu s časovou zložitosťou $D \cdot N^3$na skoro všetkých možných vstupoch. A na tomto pozorovaní založíme naše...

Formálne definície

Nech $f$, $g$ sú kladné neklesajúce funkcie definované na množine prirodzených čísel. (Všimni si, že naše funkcie udávajúce presnú časovú zložitosť tieto vlastnosti majú.) Hovoríme, že $f\left( N \right)$ je $O\left( g\left( N \right)\right)$ (čítaj: $f$ je (veľké) $O$ (od) $g$) ak pre nejaké konštanty $c$ a $N_0$ platí nasledujúca podmienka:

$$\forall N > N_0: f\left( N \right)< c\cdot g\left( N \right)$$ Preložené do ľudskej reči, $f\left( N \right)$ je $O\left( g\left( N \right)\right)$, ak pre nejaké $c$skoro celý graf funkcie $f$ leží pod grafom funkcie $c \cdot g$. Všimni si, že toto znamená, že $f$ rastie nanajvýš tak rýchlo ako $c \cdot g$.

Namiesto "$f\left( N \right)$ je $O\left( g\left( N \right)\right)$" väčšinou píšeme $f(N) = O(g(N))$. Pozor, táto rovnosť nie je symetrická – zápis "$O\left( g\left( N \right)\right)= f\left( N \right)$" nemá zmysel a " $g\left( N \right)= O\left( f\left( N \right)\right)$" nie je ekvivalentné tvrdenie. (Ak ťa to pletie, predstav si, že $O\left( g\left( N \right)\right)$ je množina funkcií, ktoré rastú nanajvýš tak rýchlo ako $g$ a namiesto $=$ si predstav znak $\in$.)

To, čo sme práve definovali, sa volá $O$-notácia. Jedno jej bežné použitie je udávanie horných odhadov časovej zložitosti algoritmov.

Uvažujme napríklad funkciu $f(N) = \frac{3N(N - 1)}{2} + N = 1.5N^2 - 0.5N$ z Príkladu 2. Podľa našej definície je $f\left( N \right)= O\left( N^2 \right)$. (Jedna možnosť, ako zvoliť potrebné konštanty, je $c = 2$ a $N_0 = 0$.) Toto znamená, že $f$ rastie (asymptoticky) najviac tak rýchlo ako $N^2$.

A toto je práve to dôležité, čo o našej funkcii potrebujeme vedieť. Vieme totiž vyvodiť nasledujúci dôležitý záver: Keď zdvojnásobíme veľkosť vstupu, zväčší sa čas behu nášho programu najviac na rádovo štvornásobok. Bez ohľadu na to, aký rýchly počítač máme a aká je konkrétna funkcia $f$, takáto úvaha bude vždy fungovať.

Budeme teda $O$-notáciu používať na zápis časovej zložitosti algoritmov (a tiež na zápis ich pamäťovej zložitosti, t. j. veľkosti použitej pamäte v závislosti od veľkosti vstupu). Napr. pre algoritmus z Príkladu 2 môžeme povedať: "Časová zložitosť tohto algoritmu je $O\left( N^2 \right)$" alebo stručnejšie "Tento algoritmus je $O\left( N^2 \right)$".

Podobne ako sme definovali $O$ môžeme definovať aj $\Omega$ a $\Theta$.

Hovoríme, že $f\left( N \right)$ je $\Omega\left( g\left( N \right)\right)$ ak $g\left( N \right)= O\left( f\left( N \right)\right)$, inými slovami, ak $f$ rastie aspoň tak rýchlo ako $g$.

No a hovoríme, že $f\left( N \right)= \Theta\left( g\left( N \right)\right)$ ak $f(N) = O(g(N))$ a $g\left( N \right)= O\left( f\left( N \right)\right)$, inými slovami, ak obe funkcie rastú rádovo rovnako rýchlo.

Malo by byť jasné, že zatiaľ čo $O$ udávalo horný odhad funkcie, $\Omega$ udáva dolný odhad a $\Theta$ sa bude používať na udanie asymptoticky presného odhadu. Sú aj ďalšie podobné značenia (napr. pre ostré nerovnosti), ale s týmito tromi si nejakú dobu vystačíme.

Príklady použitia

• $1.5N^2 -0.5N = O\left( N^2 \right)$.
• $47N \log N = O\left( N^2 \right)$.
• $N \log N + 1\,000\,047N = \Theta\left( N \log N \right)$.
• Všetky polynómy stupňa $k$ sú $O\left( N^k \right)$.
• Časová zložitosť algoritmu z Príkladu 2 je $\Theta\left( N^2 \right)$.
• Ak nejaký algoritmus je $O\left( N^2 \right)$, tak je aj $O\left( N^5 \right)$.
• Každý triediaci algoritmus založený na porovnávaní triedených prvkov je $ \Omega\left( N \log N \right)$.
• MergeSort spustený na poli s $N$ prvkami spraví rádovo $N \log N$ porovnaní. Preto jeho časová zložitosť je $\Theta\left( N \log N \right)$. Ak uveríme aj predchádzajúcemu tvrdeniu, dostávame, že MergeSort je optimálny všeobecný triediaci algoritmus.
• Algoritmus z Príkladu 2 potrebuje $\Theta\left( N \right)$ bajtov pamäte.
• Funkcia udávajúca počet tvojich zubov v závislosti od času je $O\left( 1 \right)$.
• Algoritmus, ktorý hrá šach tak, že vyskúša úplne všetky možnosti, je $O\left( 1 \right)$, lebo strom možností, ktorý musí prezrieť, je konečný. (Samozrejme, v tomto prípade sa v našom $O\left( 1 \right)$ skrýva neuveriteľne veľká konštanta.)
• Tvrdenie "Časová zložitosť tohto algoritmu je aspoň $O\left( N^2 \right)$" nemá zmysel. (Vlastne hovorí: "Časová zložitosť tohto algoritmu je aspoň nanajvýš rádovo kvadratická." Huh?) Jeho autor pravdepodobne chcel povedať: "Časová zložitosť tohto algoritmu je $\Omega\left( N^2 \right)$".

Keď neformálne hovoríme o zložitosti algoritmu, namiesto formálneho zápisu $\Theta\left( f\left( n \right)\right)$ môžeme jednoducho povedať, do akej triedy funkcii $f$ patrí. Napr. ak $f(N) = \Theta(N)$, hovoríme, že algoritmus je lineárny. Ďalšie príklady:

• $f\left( N \right)= \Theta\left( \log N \right)$: logaritmický
• $f\left( N \right)= \Theta\left( N^2 \right)$: kvadratický
• $f\left( N \right)= \Theta\left( N^3 \right)$: kubický
• $f\left( N \right)= O\left( N^k \right)$ pre nejaké $k$: polynomiálny
• $f\left( N \right)= O\left( c^N \right)$ a $f\left( N \right)= \Omega\left( d^N \right)$ pre nejaké $c,d > 1$: exponenciálny

Pri úlohách o grafoch zložitosť $\Theta\left( N + M \right)$ voláme "lineárna od veľkosti grafu".

Určenie reálneho času behu programu z asymptotického odhadu

Pre skoro všetky algoritmy, ktoré v praxi stretneš, bude konštanta "skrytá za $O$, resp. $\Theta$" rozumne malá. Teda ak nejaký algoritmus je $\Theta\left( N^2 \right)$, môžeš čakať, že jeho presná časová zložitosť je napríklad $10N^2$, a nie $10^7 N^2$.

To isté pozorovanie z opačnej strany: Ak je tá konštanta náhodou veľká, je to väčšinou preto, že nejako súvisí s konštantami uvedenými v zadaní úlohy. V takomto prípade sa patrí tú konštantu nejako nazvať a uvádzať ju v asymptotickom odhade.

Napríklad majme problém: Zadaný je reťazec dĺžky $N$, spočítaj pre každé písmeno, koľkokrát sa v ňom vyskytuje. Jeden možný algoritmus je pre každé písmeno raz prejsť celý reťazec a spočítať jeho výskyty. Rôznych znakov je najviac $255$, takže tento algoritmus je lineárny od dĺžky reťazca. Ale napriek tomu je lepšie zapísať jeho zložitosť ako $\Theta\left( | S | \cdot N \right)$, kde $S$ je množina znakov, ktoré sa môžu v reťazci vyskytnúť. (Ľahko zistíme, že existuje aj lepší algoritmus, ktorý túto úlohu rieši v čase $\Theta\left( | S | + N \right)$.)

Na priemernom súčasnom počítači potrebuje program, ktorý počíta $1\,000\,000\,000$ násobení celých čísel, niekoľko sekúnd. Na základe tejto skúsenosti vieme odhadnúť, aký veľký vstup dokáže náš algoritmus v rozumnom čase vyriešiť, ak poznáme jeho časovú zložitosť. Približné odhady sú v nasledujúcej tabuľke:

Tabuľka 3. Približné maximálne veľkosti vstupu, ktorý sa dá vyriešiť za pár sekúnd.

Poznámka o analýze algoritmov

Najlepší spôsob, ako udávať zložitosť algoritmu, je samozrejme uviesť asymptoticky presný odhad, teda $\Theta$. Toto ale nemusí vždy byť možné. Existujú napríklad problémy, kde vieme dokázať nejaký horný odhad, ale nevieme, či je tesný. Navyše $O$ sa ľahšie píše a viac ľudí ho pozná. Preto sa veľmi často používa len $O$.

Nezabúdajme ale, že $O$ predstavuje len horný odhad a tých je vždy nekonečne veľa. Preto sa snažíme nájsť a udať čo najlepší z nich, t. j. čo najpomalšie rastúcu funkciu, ktorá zhora ohraničuje čas behu algoritmu.

Príklad 3. Máme utriedené pole $A$. Treba zistiť, či sa v ňom nachádzajú dva prvky s rozdielom $D$. Napísali sme na to nasledujúci program:

int j=0;
for (int i=0; i<N; i++) {
  while ( (j<N-1) && (A[i]-A[j] > D) ) 
    j++; 
  if (A[i]-A[j] == D) return 1;
}

Je ľahké ukázať, že tento program je $O\left(N^2\right)$ – vnútorný cyklus sa spustí $N$-krát a nikdy nespraví viac ako $N$ krokov. Ale poriadnejšia analýza ukáže, že v skutočnosti tento program nie je kvadratický, ale dokonca lineárny. Stačí si uvedomiť, že počas celého behu programu sa príkaz "j++;" nemôže vykonať viac ako $N$-krát, a teda všetky spustenia vnútorného cyklu dokopy spravia najviac $N$ krokov.

Keby sme teda o algoritme z Príkladu 3 povedali, že jeho časová zložitosť je $O\left(N^2\right)$, mali by sme pravdu. Ale viac informácie obsahuje presnejšie tvrdenie, že časová zložitosť tohto algoritmu je dokonca $O\left(N\right)$.

Záver

Ukázali sme si, ako sa zapisuje časová zložitosť algoritmov a prečo je tento spôsob zápisu vhodný. Logicky by teraz malo nasledovať, ako určiť časovú zložitosť konkrétneho algoritmu. Ako už naznačil Príklad 3, toto už nemusí byť také jednoduché. A naozaj nepríjemné to je od okamihu, kedy sa k slovu dostane rekurzia. Tomuto sa už radšej budeme venovať v samostatnom texte.