$\dots$ aneb jak dlouho program poběží, než dostanu výsledek.

Velikost vstupu: Jak měřit velikost vstupních dat? Velikost vstupních dat je počet bitů, které jsou potřeba k zápisu vstupu do počítače. Často ale velikost vstupních dat měříme hrubě a uvádíme jen počet čísel na vstupu, počet vrcholů grafu, počet hran grafu apod. Zápis každého čísla, vrcholu či hrany, odpovídá jedné proměnné v počítači a obsahuje jenom konstantní počet bitů. Proto je skutečná velikosti vstupu (počet bitů) jen konstantě krát větší. Později si ukážeme, že nám při výpočtu časové složitosti na multiplikativních konstantách nezáleží.

Na binární zápis čísla $n$ je potřeba $\log n$ bitů. Proto musíme rozlišovat, jaká čísla dostaneme na vstupu. Čísla typu integer mají omezenou velikost $32$ bitů (konstantní počet bitů). Pokud na vstupu dostaneme dlouhé číslo $n$, například s miliónem cifer, tak ho nemůžeme uložit do jedné proměnné typu integer, ale budeme ho muset reprezentovat v poli. Proto bude jeho velikost na vstupu odpovídat počtu políček pole, nebo přesněji počtu bitů, což je $\log n$.

Časová složitost: Časová složitost algoritmu spuštěného na vstup $\cal D$ je počet kroků, které algoritmus provede. Časová složitost algoritmu je funkce $T:\NN\to \NN$, kde $T(n)$ je (maximální) počet kroků, které provede algoritmus běžící na datech o velikosti $n$ (pro všechny vstupy $\cal D$ velikosti $n$).

Co je to krok algoritmu? Krok algoritmu je jedna operace/instrukce daného stroje/počítače. Je to například přiřazení do proměnné, aritmetická operace $+$, $-$, $*$, $/$, vyhodnocení podmínky apod. Zjednodušeně budeme za krok algoritmu považovat libovolnou operaci proveditelnou v konstantním čase.

Označme velikost vstupu jako $n$ a nechť $c$ je nějaká konstanta. Časové složitosti $c \cdot n$ budeme říkat lineární, časové složitosti $c \cdot n^2$ kvadratická, $c \cdot n^3$ kubická a $c \cdot a^n$ pro $a>1$ exponenciální.

Jak můžeme jedno přiřazení považovat za krok algoritmu stejně jako padesát přiřazení? Proč můžeme zjednodušeně říci, že jedno číslo na vstupu má velikost jedna a ne $32$, i když zabere $32$ bitů? Copak na těchto konstantách v teoretických odhadech nezáleží? Ano je to tak. Na těchto konstantách moc nezáleží a ukážeme si proč (prakticky na nich záleží, ale to patří do praktického porovnávání algoritmů).1

Podívejme se do následující tabulky, která ukazuje, jak dlouho budou trvat výpočty algoritmů s různou časovou složitostí. Čísla v tabulce jsou přibližné hodnoty funkcí na vstupech o velikostech $10$, $100$, $1000$ a $1000000$.

$n=10$ $n=100$ $n=1000$ $n=1000000$
$\log n$ $3.3$ $6.7$ $10$ $20$
$\sqrt n$ $3.2$ $10$ $31.6$ $1000$
$n$ $10$ $100$ $1000$ $10^6$
$n\log n$ $33$ $664$ $9966$ $20\cdot10^6$
$n^2$ $100$ $10^4$ $10^6$ $10^{12}$
$n^3$ $1000$ $10^6$ $10^9$ $10^{18}$
$2^n$ $1024$ $13\cdot 10^{30}$ $11\cdot 10^{302}$ $\approx\infty$
$n!$ $36\cdot 10^5$ $93\cdot 10^{157}$ $40\cdot 10^{2567}$ $\approx\infty$

Běžný počítač zvládne spočítat $10^9$ operací za vteřinu. Následující tabulka udává, jak dlouho budou trvat výpočty algoritmů na běžném počítači.

$n=10$ $n=100$ $n=1000$ $n=1000000$
$\log n$ $3.3ns$ $6.7ns$ $10ns$ $20ns$
$\sqrt n$ $3.2ns$ $10ns$ $31.6ns$ $1\mu s$
$n$ $10ns$ $100ns$ $1\mu s$ $1ms$
$n\log n$ $33ns$ $664ns$ $9.9\mu s$ $20ms$
$n^2$ $100ns$ $10\mu s$ $1ms$ $16,5min$
$n^3$ $1\mu s$ $1ms$ $1s$ $31let$
$2^n$ $1\mu s$ $3\cdot 10^{14}let$ $3\cdot 10^{286}let$ $\approx\infty$
$n!$ $3ms$ $3\cdot 10^{142}let$ $\approx\infty$ $\approx\infty$

Co můžeme z tabulky vypozorovat? Z tabulky je vidět, že skoro všechny výpočty až na ty s časovou složitostí $2^n$ a $n!$, budou trvat rozumný čas. Proto budeme považovat algoritmy s polynomiální časovou složitostí za rozumné a těm s exponenciální časovou složitostí se budeme snažit vyhnout. Dále je vidět, že pro zpracování velkých dat jsou algoritmy s časovou složitostí menší než $c\cdot n\log n$ výrazně lepší než ostatní polynomiální algoritmy s vyšším stupněm.

To, jestli má program rozumnou časovou složitost, nerozhoduje jen o tom, jestli odpověď dostaneme hned a nebo jestli budeme muset chvilku čekat. Je otázkou, jestli se výsledku vůbec dožijeme. Vždyť i naše planeta Země existuje teprve $4,5$ miliardy let. To je $4,5\cdot10^9$ let což je zhruba jen $14\cdot 10^{16}$ vteřin.2

Z tabulky je také vidět, že například funkce $n^2$, $5n^2$ a $30n^2$ porostou skoro stejně rychle. Na dostatečně velkých vstupech je snadno odlišíme od lineárních funkcí, ale i od kubických až exponenciálních funkcí. Proto není důležitá ta konstanta před funkcí, ale řád $n^2$, se kterým funkce roste. Z toho důvodu nebudeme při posuzování algoritmů brát ohled na konstanty. To nás přivádí k pojmu asymptotická časová složitost. (Prakticky záleží i na těchto konstantách. Přeci jen je rozdíl, jestli bude algoritmus počítat rok a nebo $10$ let, případně $2$ hodiny a nebo $1$ den.)

Poznámka: Kdy se vyplatí koupit si nový počítač? O kolik větší data/vstupy budeme moci zpracovávat? Předpokládejme, že nový počítač bude dvakrát rychlejší než ten, co máme, a že používáme aplikaci, která musí nejpozději do minuty vydat odpověď. Pokud odpověď počítáme podle algoritmu s lineární časovou složitostí, tak stihneme spočítat dvakrát větší vstup. Naproti tomu pokud má algoritmus exponenciální časovou složitost, tak budeme rádi, když spočítáme výsledek pro o jedna větší vstup. A možná ani to ne.

Poznámka (Moorův zákon): Moorův zákon popisuje zajímavý trend v historii počítačového hardwaru. Říká, že se rychlost nových počítačů přibližně za každé dva roky zdvojnásobí.3 Mohli byste proto namítat, že můžeme výpočty zrychlovat tím, že si počkáme na výkonnější počítače. Jak jsme si ale ukázali v předchozí poznámce, tak nám některých případech dvojnásobné zrychlení výpočtu moc nepomůže. Proto je lepší se zaměřit na vývoj efektivnějších algoritmů.

Také se proslýchá, že se v brzké době Moorův zákon zastaví. Tranzistory na procesoru už jsou tak malé, že už se blíží k velikosti atomů.

Poznámka: Některé časové složitosti vůbec nemusí být rostoucí funkce. Klidně mohou oscilovat. Podívejme se například na algoritmus, který zjišťuje, zda je číslo $n$ prvočíslo. Postupně bude procházet čísla $2$ až $\sqrt n$ a testovat, zda dané číslo dělí $n$. Pokud uspěje, tak máme dělitele, můžeme skončit a odpovědět, že číslo $n$ není prvočíslo. Jinak projdeme všechny možné dělitele a nakonec odpovíme, že $n$ je prvočíslo.4 Pro každé sudé $n$ algoritmus skončí hned v prvním kroku. Na druhou stranu pro každé $n$ prvočíslo algoritmus projde všech $\sqrt n$ čísel. Proto časová složitost osciluje mezi funkcemi $1$ a $\sqrt n$.