]> mj.ucw.cz Git - ads1.git/blob - slides/growth.tex
Initial commit.
[ads1.git] / slides / growth.tex
1 \input slidemac.tex
2 \input epsf.tex
3
4 \language=\czech
5 \chyph
6
7 \slide{Srovnání rychlostí algoritmù (pøedpokládáme $10^9$ operací za sekundu)}
8
9 \def\[#1]{\,\hbox{#1}}
10 $$\vbox{
11 \halign{$#$ \hfil&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$&\quad\hfil $#$\cr
12 \hbox{funkce / $n=$\hskip-2em}& 10              & 20            & 30            & 50            & 100           & 1\,000        & 1\,000\,000 \cr
13 \noalign{\medskip\hrule\bigskip}
14 \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
15 n               & 10\[ns]       & 20\[ns]       & 30\[ns]       & 50\[ns]       & 100\[ns]      & 1\[$\mu$s]    & 1\[ms]        \cr
16 n\cdot\log_2 n\hskip-1em        & 33\[ns]       & 86\[ns]       & 147\[ns]      & 282\[ns]      & 664\[ns]      & 10\[$\mu$s]   & 20\[ms]       \cr
17 n^2             & 100\[ns]      & 400\[ns]      & 900\[ns]      & 2.5\[$\mu$s]  & 100\[$\mu$s]  & 1\[ms]        & 1\,000\[s]    \cr
18 n^3             & 1\[$\mu$s]    & 8\[$\mu$s]    & 27\[$\mu$s]   & 125\[$\mu$s]  & 1\[ms]        & 1\[s]         & 10^9\[s]      \cr
19 2^n             & 1\[$\mu$s]    & 1\[ms]        & 1\[s]         & 10^6\[s]      & 10^{21}\[s]   & 10^{292}\[s]  & \approx\infty \cr
20 n!              & 10^6\[s]      & 10^{18}\[s]   & 10^{32}\[s]   & 10^{64}\[s]   & 10^{158}\[s]  & 10^{2567}\[s] & \approx\infty \cr
21 }}$$
22
23 \bigskip
24
25 \halign{#\hfil&\quad #\hfil\cr
26 Pro pøedstavu:  &$1\,000\[s]$ je asi tak ètvrt hodiny\cr
27                 &$1\,000\,000\[s]$ je necelých 12 dní\cr
28                 &$10^9\[s]$ je 31 let\cr
29                 &$10^{18}\[s]$ je asi tak stáøí Vesmíru. \cr}
30
31 \endslide
32
33 \slide{Poèítaèe se nám zrychlují aneb Mooreùv zákon}
34
35 \bigskip
36
37 \uv{Ka¾dé dva roky se výkon poèítaèù zdvojnásobí} -- Gordon Moore (prý)
38
39 \bigskip
40 \bigskip
41
42 \qquad \dots\ Není tedy lep¹í chvíli poèkat ne¾ vymý¹let lep¹í algoritmus? :-)
43
44 \bigskip
45 \bigskip
46
47 $$\vbox{\halign{\hfil$#$\quad&\hfil$#$\quad&\hfil$#$\qquad&#\hfil\cr
48 \hbox{funkce} & 10^6\;\hbox{op.} & 2\cdot10^6\;\hbox{op.} & zmìna \cr
49 \noalign{\medskip\hrule\bigskip}
50 n       &1\,000\,000    &2\,000\,000    &2-krát více            \cr
51 n^2     &1\,000         &1\,414         &$\sqrt{2}\approx 1.41$-krát více       \cr
52 n^3     &100            &126            &$\root3\of2\approx 1.26$-krát více     \cr
53 2^n     &20             &21             &o 1 více       \cr
54 }}$$
55
56 \endslide
57
58 \slide{Asymptotický rùst funkcí}
59
60 \centerline{\epsfxsize=0.85\hsize\epsfbox{funcs.eps}}
61
62 \endslide
63
64 \slide{Asymptotický rùst funkcí: èleny ni¾¹ích øádù se schovají do konstant}
65
66 \centerline{\epsfxsize=0.85\hsize\epsfbox{funcs2.eps}}
67
68 \endslide
69
70 \end