diff options
author | Ayexor <9105454+Ayexor@users.noreply.github.com> | 2021-08-27 18:09:54 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-08-27 18:09:54 +0200 |
commit | 2b2c5daa139aec08d091b658ad6191d6e57024ef (patch) | |
tree | 2c8f3fc7017394746d8e4f92a358e2a11015e072 /buch/papers/multiplikation/presentation/slides/bigO.tex | |
parent | Anpassungen nach Mail (diff) | |
parent | new image: tetraeder (diff) | |
download | SeminarMatrizen-2b2c5daa139aec08d091b658ad6191d6e57024ef.tar.gz SeminarMatrizen-2b2c5daa139aec08d091b658ad6191d6e57024ef.zip |
Merge branch 'master' into master
Diffstat (limited to '')
-rw-r--r-- | buch/papers/multiplikation/presentation/slides/bigO.tex | 251 |
1 files changed, 251 insertions, 0 deletions
diff --git a/buch/papers/multiplikation/presentation/slides/bigO.tex b/buch/papers/multiplikation/presentation/slides/bigO.tex new file mode 100644 index 0000000..d425da8 --- /dev/null +++ b/buch/papers/multiplikation/presentation/slides/bigO.tex @@ -0,0 +1,251 @@ + +\begin{frame} + \frametitle{Big $\mathcal{O}$ notation} +\begin{itemize} + \item <1-> Time complexity of an algorithm + \item <2-> How many multiplications in a function + \item <3-> Drop Constants +\end{itemize} +\end{frame} + + +\begin{frame} + \frametitle{Big $\mathcal{O}$ notation} + \onslide<1->{ + + \begin{algorithm}[H]\caption{Foo 1} + \setlength{\lineskip}{7pt} + \begin{algorithmic}[1] + \Function{foo}{$a, b$} + \State \textbf{return} $a+b$ + \EndFunction + \end{algorithmic} + \end{algorithm} +} +\onslide<2->{ +$\mathcal{O}(1)$ + } +\end{frame} + +\begin{frame} + \frametitle{Big $\mathcal{O}$ notation} + \onslide<1->{ + + \begin{algorithm}[H]\caption{Foo 2} + \setlength{\lineskip}{7pt} + \begin{algorithmic}[1] + \Function{foo}{$a, b$} + \State $ x \gets a+b $ + \State $ y \gets a \cdot b $ + \State \textbf{return} $x+y$ + \EndFunction + \end{algorithmic} + \end{algorithm} +} +\onslide<2->{ +$\mathcal{O}(1) + \mathcal{O}(1) = 2\mathcal{O}(1) = \mathcal{O}(1) $ + } +\end{frame} + +\begin{frame} + \frametitle{Big $\mathcal{O}$ notation} + \onslide<1->{ + + \begin{algorithm}[H]\caption{Foo 3} + \setlength{\lineskip}{7pt} + \begin{algorithmic}[1] + \Function{foo}{$\mathbf{A}, \mathbf{B}$,n} + \State $ sum \gets 0$ + \For{$i = 0,1,2 \dots,n$} + \State $ sum \gets sum + A[i] \cdot B[i] $ + \EndFor + + \State \textbf{return} $sum$ + + \EndFunction + \end{algorithmic} + \end{algorithm} +} +\onslide<2->{ +$\mathcal{O}(n)$ + } +\end{frame} + +\begin{frame} + \frametitle{Big $\mathcal{O}$ notation} + \onslide<1->{ + + \begin{algorithm}[H]\caption{Foo 4} + \setlength{\lineskip}{7pt} + \begin{algorithmic}[1] + \Function{foo}{$\mathbf{A}, \mathbf{B}$,n} + \State $ sum \gets 0$ + \For{$i = 0,1,2 \dots,n$} + \For{$j = 0,1,2 \dots,n$} + \State $ sum \gets sum + A[i] \cdot B[j] $ + \EndFor + \EndFor + \State \textbf{return} $sum$ + \EndFunction + \end{algorithmic} + \end{algorithm} +} +\onslide<2->{ +$\mathcal{O}(n^2)$ + } +\end{frame} + +% \begin{frame} +% \frametitle{Big $\mathcal{O}$ notation} +% \onslide<1->{ +% +% \begin{algorithm}[H]\caption{Fibonacci} +% \setlength{\lineskip}{7pt} +% \begin{algorithmic}[1] +% \Function{fib}{$n$} +% \If{$n <= 1$} +% \State \textbf{return} $1$ +% \Else +% \State \textbf{return} fib($n-1$) + fib($n-2$) +% \EndIf +% +% \EndFunction +% \end{algorithmic} +% \end{algorithm} +% } +% \onslide<2->{ +% \[ +% \langle x,y \rangle = +% \begin{cases} +% \displaystyle $\mathcal{O}(1)$ & \text{if $n \leq 2$}\\ +% \displaystyle $ 2 \mathcal{T}(\frac{n}{2})$ & \text{if $n > 2$} +% \end{cases} +% \] } +% \end{frame} + + +\begin{frame} + \frametitle{Big $\mathcal{O}$ notation} +\begin{tikzpicture} +\begin{axis}[ + axis lines = left, + xlabel = $n$ (Data Input), + ylabel = {$t$ (time)}, + legend pos=north east, + very thick, + ymax = 20, + yticklabels=\empty, + xticklabels=\empty, + scale only axis=true, + width=12cm, height=6cm, + ] +%Below the red parabola is defined +\addplot [ + domain= 1:6, + samples=100, + color=red, +] +{1}; +\addlegendentry{$\mathcal{O}(1)$} +%Here the blue parabloa is defined +\addplot [ + domain= 1:6, + samples=100, + color=green, +] +{x}; +\addlegendentry{$\mathcal{O}(n)$} +\addplot [ + domain= 1:6, + samples=100, + color=blue, +] +{x^2}; +\addlegendentry{$\mathcal{O}(n^2)$} +\addplot [ + domain= 1:6, + samples=100, + color=purple, +] +{x^3}; +\addlegendentry{$\mathcal{O}(n^3)$} +\addplot [ + domain= 1:3, + samples=100, + color=black, +] +{exp(x)}; +\addlegendentry{$\mathcal{O}(e^n)$} +\addplot [ + domain= 1:6, + samples=100, + color=orange, +] +{log2(x)}; +\addlegendentry{$\mathcal{O}(\log n)$} +\end{axis} +\end{tikzpicture} + +\end{frame} + +\begin{frame} + \frametitle{Big $\mathcal{O}$ notation} +\begin{tikzpicture} +\begin{axis}[ + axis lines = left, + xlabel = $n$ (Data Input), + ylabel = {$t$ (time)}, + legend pos=north east, + very thick, + ymax = 500, + yticklabels=\empty, + xticklabels=\empty, + scale only axis=true, + width=12cm, height=6cm, + ] +\addplot [ + domain= 1:20, + samples=100, + color=red, +] +{1}; +\addlegendentry{$\mathcal{O}(1)$} +\addplot [ + domain= 1:20, + samples=100, + color=green, +] +{x}; +\addlegendentry{$\mathcal{O}(n)$} +\addplot [ + domain= 1:20, + samples=100, + color=blue, +] +{x^2}; +\addlegendentry{$\mathcal{O}(n^2)$} +\addplot [ + domain= 1:10, + samples=100, + color=purple, +] +{x^3}; +\addlegendentry{$\mathcal{O}(n^3)$} +\addplot [ + domain= 1:10, + samples=100, + color=black, +] +{exp(x)}; +\addlegendentry{$\mathcal{O}(e^n)$} +\addplot [ + domain= 1:20, + samples=100, + color=orange, +] +{log2(x)}; +\addlegendentry{$\mathcal{O}(\log n)$} +\end{axis} +\end{tikzpicture} + +\end{frame} |