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.