\input /home/pasky/school/fastex/lib.tex

\chapter{Složitost}{

	Složitostí míníme závislost na ``velikosti'' vstupních dat.

	Časová složitost nechť je funkce $f(|D|)$ udávající
	počet kroků algoritmu. Intuitivně: nejsou podstatné
	multiplikativní a aditivní konstanty, podstatná je
	``kategorie'', kam algoritmus patří.

	Krokem algoritmu myslíme operaci stroje, kterou zvládneme
	v konstantním čase. Pro nás:
	\list{
	\olistItem{aritmetické operace}
	\olistItem{porovnání dvou hodnot}
	\olistItem{přiřazení (ovšem pouze jednoduchých typů --- skalárů)}
	}

	Třídy složitosti:
	\list{
	\olistItem{$f(n) = cn$ (lineární): hledání maxima posloupnosti}
	\olistItem{$f(n) = cn\log n$: vytvoření binární haldy z $n$ prvků}
	\olistItem{$f(n) = cn^2$ (kvadratický): bubble sort}
	\olistItem{$f(n) = cn^3$ (kubický): vytisknout všechny trojice z $n$ vstupních čísel}
	\olistItem{$f(n) = 2^n$ (exponenciální): vytisknout všechny podmnožiny z množiny $n$ prvků}
	\olistItem{$f(n) = n!$: problém obchodního cestujícího}
	}

	\scpart{Asymptotická složitosti}{
		\shortdef{Intuitivně}{zkoumá chování algoritmu na ``velkých datech'', t.j.
		nebere v úvahu multiplikativní a aditivní konstanty, a zařazuje algoritmy
		do ``kategorií'''.

		\scpart{Rigorózně:}{
			$f(n)$ je asymptoticky menší nebo rovno $g(n)$:
			$$ f(n) = O(g(n)) \Longleftrightarrow \existss c > 0,\ \existss n_0 > 0,\ \forall n \ge n_0:
				0 \le f(n) \le cg(n) $$
			(Znaménko ``='' nelze brát ve výrazu $f(n) = O(g(n))$ doslova, spíše je zde
			ve významu $f(n) \in O(g(n))$.)

			$f(n)$ je asymptoticky větší nebo rovno $g(n)$:
			$$ f(n) = \Omega(g(n)) \Longleftrightarrow \existss c > 0,\ \existss n_0 > 0,\ \forall n \ge n_0:
				0 \le cg(n) \le f(n) $$

			$f(n)$ je asymptoticky stejné jako $g(n)$:
			$$ f(n) = \Theta(g(n)) \Longleftrightarrow \existss c > 0,\ \existss n_0 > 0,\ \forall n \ge n_0:
				0 \le c_1g(n) \le f(n) \le c_2g(n) $$
			$$ f(n) = \Theta(g(n)) \Longleftrightarrow f(n) = O(g(n)) \et f(n) = \Omega(g(n)) $$
			(Asymptotická rovnost je vyhrazena pro \M{\lim_{n\to\infty} {f(n)/ g(n)} = 1}.)

			\bigskip

			Pro úplnost:

			$f(n)$ je asymptoticky ostře menší $g(n)$:
			$$ f(n) = o(g(n)) \Longleftrightarrow \forall c > 0,\ \existss n_0 > 0,\ \forall n \ge n_0:
				0 \le f(n) < cg(n) $$
			(Zásadní rozdíl je v kvantifikátoru konstanty! Jinak bychom ostrou nerovnost získali
			pouhým snížením konstanty.)

			$f(n)$ je asymptoticky ostře větší $g(n)$:
			$$ f(n) = \omega(g(n)) \Longleftrightarrow \forall c > 0,\ \existss n_0 > 0,\ \forall n \ge n_0:
				0 \le cg(n) < f(n) $$
			
		}
	}

}

\bend