aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/multiplikation/problemstellung.tex
diff options
context:
space:
mode:
authorNunigan <michael.schmid2@ost.ch>2021-08-06 17:37:58 +0200
committerNunigan <michael.schmid2@ost.ch>2021-08-06 17:37:58 +0200
commit872595e81de60c85b18408f8de5a49c535518edc (patch)
tree05f76c1e3a183286b938013b3683b47c7c4a77c2 /buch/papers/multiplikation/problemstellung.tex
parentMerge branch 'AndreasFMueller:master' into master (diff)
downloadSeminarMatrizen-872595e81de60c85b18408f8de5a49c535518edc.tar.gz
SeminarMatrizen-872595e81de60c85b18408f8de5a49c535518edc.zip
update multiplikation
Diffstat (limited to '')
-rwxr-xr-xbuch/papers/multiplikation/problemstellung.tex33
1 files changed, 16 insertions, 17 deletions
diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex
index c6fd10e..e53b0de 100755
--- a/buch/papers/multiplikation/problemstellung.tex
+++ b/buch/papers/multiplikation/problemstellung.tex
@@ -7,13 +7,14 @@
\rhead{Problemstellung}
Wegen der breiten Anwendung der Matrizenmultiplikation ist eine effiziente L\"osung dieser Operation von grosser Bedeutung.
Das Ziel dieses Papers ist, verschiedenen Algorithmen der Matrizenmultiplikation vorzustellen.
-Gezielt wird auf Algorithmen eingegange, welche das Problem schneller als der Standard Algorithmus l\"osen.
+Gezielt wird auf Algorithmen eingegangen, welche das Problem schneller als der Standard Algorithmus l\"osen.
\subsection{Big $\mathcal{O}$ Notation}
\label{muliplikation:sec:bigo}
-Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus in Abhänigkeit zur Inputgrösse \cite{multiplikation:bigo}.
+Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus in Abhängigkeit zur Inputgrösse \cite{multiplikation:bigo}.
$f(x) \in \mathcal{O}(g(x))$ besagt, dass die Funktion $f$ nicht wesentlich schneller w\"achst als $g$ wenn $x \rightarrow \infty$.
-Als Beispiel: benötigt eine Funktion $g$, $\mathcal{O}\left(n+n^2 \right)$ Multiplikationen so wächst $f$ mit $\mathcal{O}\left(n^2 \right)$ nicht wesentlich schneller als $g$.
+% Es gibt eine Konstante $K$ derart, dass $f(x) \le K g(x)$ für $x\to\infty$
+Als Beispiel: benötigt eine Funktion $g$ $\mathcal{O}\left(n^2 \right)$ Multiplikationen, so wächst $f$ mit $\mathcal{O}\left(n+ n^2 \right)$ nicht wesentlich schneller falls $x\to\infty$.
Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet:
\begin{itemize}
\item $f \in \mathcal{O}(1) \rightarrow f$ ist beschr\"ankt
@@ -26,13 +27,9 @@ Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet:
\end{itemize}
In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufzeiten miteinander verglichen werden.
+Bei einer logarithmischen Darstellung werden Polynome der Form $f(x) = x^k$ als Gerade und Exponentialfunktionen der Form $f(x) = a^x$ als nach oben gekr\"ummte Kurven dargestellt.
+Sch\"on zu erkennen ist, dass Logarithmische Kurven beschr\"ankt sind.
-\begin{figure}
- \center
- \includegraphics[]{papers/multiplikation/images/bigo}
- \caption{Verschiedene Laufzeiten}
- \label{multiplikation:fig:bigo}
-\end{figure}
\subsubsection{Beispiel Algorithmen}
@@ -101,23 +98,25 @@ Es folgen einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomple
\paragraph{Beschr\"ankter Algorithmus}
-Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmus \ref{multiplikation:alg:b1} entnommen werden. Da $a$ und $b$ Skalare sind, hat keine Gr\"osse $n$ einen einfluss auf die Laufzeit.
-
-
+Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmus \ref{multiplikation:alg:b1} entnommen werden. Da $a$ und $b$ Skalare sind, hat keine Gr\"osse $n$ einen Einfluss auf die Laufzeit.
Konstanten werden nicht beachtet, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$.
-
-
\paragraph{Linearer Algorithmus}
Der Algorithmus \ref{multiplikation:alg:linear} hat ein lineares Verhalten.
Die \texttt{for}-Schleife wird $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O}(n)$.
-
-
\paragraph{Quadratischer Algorithmus}
Der Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches Verhalten.
-Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchglaufen und f\"uhrt deshalb zu $\mathcal{O}\left(n^2\right)$.
+Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O}\left(n^2\right)$.
+
+
+\begin{figure}
+ \center
+ \includegraphics[]{papers/multiplikation/images/bigo}
+ \caption{Verschiedene Laufzeiten}
+ \label{multiplikation:fig:bigo}
+\end{figure}