slides/growth.tex

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