\input slidemac.tex
\input epsf.tex

\language=\czech
\chyph

\slide{Srovnání rychlostí algoritmù (pøedpokládáme $10^9$ operací za sekundu)}

\def\[#1]{\,\hbox{#1}}
$$\vbox{
\halign{$#$ \hfil&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$\cr
\hbox{funkce / $n=$\hskip-2em}& 10		& 20 		& 30 		& 50 		& 100 		& 1\,000 	& 1\,000\,000 \cr
\noalign{\medskip\hrule\bigskip}
\log_2 n	& 3.3\[ns] 	& 4.3\[ns]	& 4.9\[ns]	& 5.6\[ns]	& 6.6\[ns]	& 10.0\[ns]	& 19.9\[ns]	\cr
n		& 10\[ns]	& 20\[ns]	& 30\[ns]	& 50\[ns]	& 100\[ns]	& 1\[$\mu$s]	& 1\[ms]	\cr
n\cdot\log_2 n\hskip-1em	& 33\[ns]	& 86\[ns]	& 147\[ns]	& 282\[ns]	& 664\[ns]	& 10\[$\mu$s]	& 20\[ms]	\cr
n^2		& 100\[ns]	& 400\[ns]	& 900\[ns]	& 2.5\[$\mu$s]	& 100\[$\mu$s]	& 1\[ms]	& 1\,000\[s]	\cr
n^3		& 1\[$\mu$s]	& 8\[$\mu$s]	& 27\[$\mu$s]	& 125\[$\mu$s]	& 1\[ms]	& 1\[s]		& 10^9\[s]	\cr
2^n		& 1\[$\mu$s]	& 1\[ms]	& 1\[s]		& 10^6\[s]	& 10^{21}\[s]	& 10^{292}\[s]	& \approx\infty	\cr
n!		& 3\[ms]	& 10^9\[s] 	& 10^{23}\[s]	& 10^{55}\[s]	& 10^{149}\[s]	& 10^{2558}\[s]	& \approx\infty	\cr
}}$$

\bigskip

\halign{#\hfil&\quad #\hfil\cr
Pro pøedstavu:	&$1\,000\[s]$ je asi tak ètvrt hodiny\cr
		&$1\,000\,000\[s]$ je necelých 12 dní\cr
		&$10^9\[s]$ je 31 let\cr
		&$10^{18}\[s]$ je asi tak stáøí Vesmíru. \cr}

\endslide

\slide{Asymptotický rùst funkcí}

\centerline{\epsfxsize=0.85\hsize\epsfbox{funcs.eps}}

\endslide

\slide{Asymptotický rùst funkcí: èleny ni¾¹ích øádù se schovají do konstant}

\centerline{\epsfxsize=0.85\hsize\epsfbox{funcs2.eps}}

\endslide

\slide{Poèítaèe se nám zrychlují aneb Mooreùv zákon}

\bigskip

\uv{Ka¾dých 18 mìsícù se výkon poèítaèù zdvojnásobí} -- Gordon Moore (prý)

\bigskip
\bigskip

\qquad \dots\ Není tedy lep¹í chvíli poèkat ne¾ vymý¹let lep¹í algoritmus? :-)

\bigskip
\bigskip

$$\vbox{\halign{\hfil$#$\quad&\hfil$#$\quad&\hfil$#$\qquad&#\hfil\cr
\hbox{funkce} & 10^6\;\hbox{op.} & 2\cdot10^6\;\hbox{op.} & zmìna \cr
\noalign{\medskip\hrule\bigskip}
n	&1\,000\,000	&2\,000\,000	&2-krát více		\cr
n^2	&1\,000		&1\,414		&$\sqrt{2}\approx 1.41$-krát více	\cr
n^3	&100		&126		&$\root3\of2\approx 1.26$-krát více	\cr
2^n	&20		&21		&o 1 více	\cr
}}$$

\endslide

\end
