\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
