Spočítat časovou složitost přesně je docela těžké. Protože jsme si ukázali, že na multiplikativních konstantách tolik nezáleží, budeme časovou složitost jenom odhadovat ze shora.

Některé úlohy příjímají více různých vstupů stejné velikosti (například když chceme setřídit $n$ čísel). Doba výpočtu může být závislá na konkrétním vstupu. Potřebujeme odhadnout čas, za jak dlouho program určitě doběhne ve všech případech. K tomu nám stačí odhadnout dobu výpočtu v nejhorším případě. Té budeme říkat časová složitost v nejhorším případě.

Například pokud program počítá navádění letadel a snaží se zabránit srážkám, tak musíme vždycky dostat odpověď do pár vteřin. Nemůžeme říkat, že to normálně funguje rychle a bez problémů. Že došlo k nehodě jen proto, že tam ta letadla letěla blbě, nastala vyjímečná situace a my jsme to nestihli spočítat.

Uvedeme si několik příkladů, na kterých si ukážeme, jak počítat časovou složitost v nejhorším případě.

Hledání minima v poli

V poli $\ARRAY{A}{\cdot}$ dostaneme $n$ čísel. Máme vrátit hodnotu nejmenšího z nich.

$min := \ARRAY{A}{1}$
for $i=2$  to $n$ do
	if $\ARRAY{A}{i} < min$   then
		$min := \ARRAY{A}{i}$
return min

Řádky 3 a 4, tj. podmínka a případné zapamatování si nového minima, zaberou nejvýše konstantní čas. Označíme je za krok algoritmu. Spolu s testem uvnitř for-cyklu proběhnou $(n-1)$-krát. Ostatní řádky proběhnou jen jednou. Proto je celková časová složitost algoritmu $\OO(n)$.

Umíte ukázat dolní odhad na časovou složitost hledání minima? Tím myslíme dokázali byste ukázat, kolik nejméně porovnání dvou čísel je potřeba k nalezení minima? Podívejme se na hledání minima jako na turnaj. Při utkání dvou prvků vyhrává ten menší. Chceme najít vítěze. Prvek, který je absolutním vítězem, musel porazit každý další prvek přímo a nebo nepřímo (porazit někoho, kdo ten prvek porazil — ať už přímo nebo nepřímo). Každý z $n-1$ prvků, které nevyhrály, musel být aspoň jednou poražen. Jinak o sobě může prohlašovat, že je také vítězem. Proto je potřeba alespoň $n-1$ porovnání (zápasů).

Sečtení prvků v matici

Dostaneme matici přirozených čísel o rozměrech $n\times n$ a chceme všechna čísla sečíst. Pomocí dvou for-cyklů projdeme celou matici a všechna čísla sečteme. Proto je časová složitost algoritmu $\OO(n^2)$. Rychleji to nejde, protože musíme projít všech $n^2$ čísel.

Přesto můžeme o algoritmu říci, že je lineární ve velikosti vstupu. Musíme si uvědomit, že vstupem algoritmu je matice, která obsahuje $n^2$ čísel.

Vypisování $n$ čísel

Dostaneme číslo $n$ a úkolem je vypsat všechna čísla $1$ až $n$. Jakou to bude mít časovou složitost? Pokud ji chceme vyjádřit v závislosti na čísle $n$, tak jednoduše $\OO(n)$. Ovšem co když ji chceme vyjádřit vzhledem k velikosti vstupu? Velikost vstupu je $m:=\log n$ bitů. Na výstup vypíšeme $n$ čísel, každé o velikosti maximálně $\log n$. Časová složitost odpovídá počtu vypsaných bitů a to je $\OO(n\log n) = \OO(m2^m)$.

Vždy je potřeba si ujasnit, vzhledem k čemu budeme časovou složitost vyjadřovat.

Binární vyhledávání v setříděném poli

Máme pole $\ARRAY{A}{\cdot}$ obsahující $n$ čísel setříděných od nejmenšího po největší. Chceme zjistit, jestli pole obsahuje číslo $x$.

$dolni := 1$
$horni := n$
while $horni \geq dolni$    do
	 $stred := \lfloor (dolni + horni)/2 \rfloor$
	 if $x = \ARRAY{A}{stred}$    then
	 	 return TRUE
	 else if $x<\ARRAY{A}{stred}$    then
	 	 $horni:=stred-1$
	 else
	 	 $dolni:=stred+1$
return FALSE

Invariant je vlastnost, která se v průběhu algoritmu nemění. Vhodných invariantů často využíváme v důkazech správnosti algoritmu, i při výpočtu časové složitosti.

Invariantem binárního vyhledávání je, že číslo $x$ může být v poli $\ARRAY{A}{\cdot}$ pouze v úseku mezi indexy $dolni$ a $horni$. Na začátku tento úsek obsahuje celé pole a v každé iteraci ho zmenšíme na polovinu. Pokud už je úsek tak malý, že neobsahuje žádný prvek, tak skončíme.

Díky půlení úseku proběhne while-cyklus nejvýše $\log n$ krát. To můžeme nahlédnout analýzou pozpátku. Průběh algoritmu sledujeme jako film, který si pustíme pozpátku. Nejprve má úsek jeden prvek, pak dvakrát tolik, to je dva prvky. A tak dále, až po $h=\lceil \log n \rceil$ krocích bude mít $2^h\geq n$ prvků.

Proto je časová složitost vyhledávání $\OO(\log n)$.

Bublinkové třídění

V poli $\ARRAY{A}{\cdot}$ dostaneme $n$ čísel. Čísla chceme setřídit pomocí porovnávání dvojic a prohazování prvků pole. Použijeme bublinkový algoritmus.

for $j=1$  to $n$  do
for $i=1$  to $n-j$  do
		 if $\ARRAY{A}{i} > \ARRAY{A}{i+1}$    then
			 prohoď($i$, $i+1$ )

Prohoď($x$,$y$) prohodí prvky v poli $\ARRAY{A}{\cdot}$ na pozicích $x$ a $y$. Algoritmus obsahuje dva for-cykly a každý z nich proběhne nejvýše $n$-krát. Řádky $3$, $4$ budou trvat konstantní čas a proto odhadneme časovou složitost jako $\OO(n^2)$.

Mohli byste namítat, že jsme časovou složitost počítali příliš hrubě. Druhý for-cyklus přeci neproběhne vždycky $n$-krát, ale poprvé jen $(n-1)$-krát, pak $(n-2)$-krát,$\dots$ až dvakrát a naposledy jen jednou. Přesný počet provedení řádek $3$ a $4$ je součtem aritmetické řady $(n-1)+(n-2)+\dots+2+1 = (n-1) \frac{(n-1)+1}{2} = \onehalf (n^2-n) = \OO(n^2)$. I po přesnějším výpočtu nám vyšla stejná asymptotická časová složitost. Z toho vidíme, že si v určitých případech můžeme dovolit počítat hrubě.1

Dolní odhad pro třídění

A co dolní odhad? Kolik nejméně porovnání (a případných prohození) je potřeba k setřídění $n$ čísel $a_1$, $a_2$,\dots, $a_n$? Průběh každého deterministického algoritmu2 lze zachytit rozhodovacím stromem.

Na následujícím obrázku je příklad rozhodovacího stromu pro setřídění $a_1$, $a_2$, $a_3$. Každý vnitřní vrchol odpovídá porovnávání dvou čísel $a_i$ a $a_j$ (a jejich případnému prohození). Toto porovnání můžeme vyjádřit otázkou “Je $a_i \leq a_j$ ?” Listy stromu jsou označeny permutací, podle které musíme přerovnat vstup, abychom dostali setříděnou posloupnost. Tedy například listu označenému permutací “$1$ $3$ $2$” odpovídá pořadí prvků $a_1 \leq a_3 \leq a_2$.

Jak funguje algoritmus odpovídající rozhodovacímu stromu? Algoritmus začne v kořenu stromu, kde se zeptá na první otázku. Odpověď mu určí větev stromu, kterou bude pokračovat. Po hraně dorazí k další otázce. Zeptá se na tuto otázku a podle odpovědi bude pokračovat dále. Postupně se ptá na otázky, které potká, a odpovědi mu určují cestu, kudy bude pokračovat. Nakonec dorazí do listu, kde si už musí být jist, jaké je uspořádání prvků ze vstupu podle velikosti.

Kontrolní otázka: Jakou permutaci setříděné posloupnosti musíme dát na vstup, aby algoritmus došel do listu s permutací $\pi$? Permutaci inverzní k $\pi$, to je $\pi^{-1}$.

Listy stromu musí obsahovat všechny možné permutace. Jinak by existovaly dvě permutace setříděné posloupnosti, které když dáme na vstup, tak povedou do stejného listu.3 Algoritmus by nebyl schopen je rozlišit. Proto má rozhodovací strom alespoň $n!$ listů.

Rozhodovací strom je binární strom s alespoň $n!$ listy. Časová složitost v nejhorším případě je délka nejdelší cesty od kořene do listu. Ta je nejkratší, pokud je strom vyvážený a jeho listy obsahují každou permutaci jen jednou. Protože strom má $n!$ listů, tak je jeho výška alespoň $$\log(n!)=\log n + \log (n-1) + \dots +\log 1 \geq \frac{n}{2} \cdot \log (n/2) \geq \frac{1}{2} n\log n – \frac{n}{2} \log 2$$ (v první nerovnosti jsme si nechali jen první polovinu členů součtu a odhadli je zdola velikostí nejmenšího ze zbylých členů). Tím jsme ukázali, že každý algoritmus založený na porovnávání dvojic musí udělat $\Omega( n\log n)$ porovnání. Poznamenejme, že odhad je asymptoticky nejlepší možný, protože třídící algoritmy s časovou složitostí $\OO(n\log n)$ v nejhorším případě existují (například heapsort nebo mergesort).

Pozor, jsou i algoritmy, které nejsou založené na porovnávání dvou čísel, ale využívají znalostí o tom, jak čísla vypadají. Například pokud na vstupu dostaneme $n$ různých čísel z rozsahu $1$ až $N$, tak si můžeme vytvořit pole $\ARRAY{x}{\cdot}$ o velikosti $N$ znázorňující charakteristický vektor množiny ze vstupu. Hodnota $\ARRAY{x}{i}$ je $1$, pokud je číslo $i$ součástí vstupu a $0$ jinak. Pole $\ARRAY{x}{\cdot}$ vyplníme jedním průchodem vstupu. Jedním průchodem pole $\ARRAY{x}{\cdot}$ jsme schopni vypsat setříděnou posloupnost čísel. Časová složitost tohoto algoritmu je tedy $\OO(n+N)$. Drobným vylepšením dostaneme například BucketSort, RadixSort, kterým se česky říká přihrádkové třídění. Nevýhodou těchto algoritmů jsou vyšší paměťové nároky a časová složitost závislá na velikosti čísel $N$. Záleží, co víme o datech, které chceme třídit.