diff options
Diffstat (limited to '')
| -rwxr-xr-x | buch/papers/multiplikation/einlteung.tex | 20 | ||||
| -rw-r--r-- | buch/papers/multiplikation/images/bigo.pdf | bin | 24288 -> 26821 bytes | |||
| -rw-r--r-- | buch/papers/multiplikation/images/bigo.tex | 36 | ||||
| -rw-r--r-- | buch/papers/multiplikation/images/strassen.pdf | bin | 15850 -> 19970 bytes | |||
| -rw-r--r-- | buch/papers/multiplikation/images/strassen.tex | 14 | ||||
| -rwxr-xr-x | buch/papers/multiplikation/loesungsmethoden.tex | 80 | ||||
| -rwxr-xr-x | buch/papers/multiplikation/problemstellung.tex | 27 | ||||
| -rwxr-xr-x | buch/papers/multiplikation/references.bib | 20 |
8 files changed, 113 insertions, 84 deletions
diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex index bc4bfcf..ea71d91 100755 --- a/buch/papers/multiplikation/einlteung.tex +++ b/buch/papers/multiplikation/einlteung.tex @@ -17,14 +17,8 @@ Koeffizienten c_{ij} = \sum_{k=1}^n a_{ik} b_{kj}. \label{multiplikation:eq:MM} \end{equation} -Grafisch kann die Matrizenmultiplikation $AB=C$ wie in \ref{multiplikation:fig:mm_viz} visualisiert werden. -\begin{figure} - \center - \includegraphics[]{papers/multiplikation/images/mm_visualisation} - \caption{Matrizen Multiplikation} - \label{multiplikation:fig:mm_viz} -\end{figure} -Im Fall einer Matrizengr\"osse von $2\times 2$ +Grafisch kann die Matrizenmultiplikation $\mathbf{AB}=\mathbf{C}$ wie in \ref{multiplikation:fig:mm_viz} visualisiert werden. +Im Fall einer Matrizengr\"osse von $2\times 2$ kann die Matrixgleichung \begin{equation} \begin{bmatrix} A_{11} & A_{12}\\ @@ -40,7 +34,7 @@ C_{11} & C_{12}\\ C_{21} & C_{22} \end{bmatrix} \end{equation} -kann die Gleichung der einzelnen Terme +explizt als Gleichung \begin{equation} \label{multiplikation:eq:MM_exp} \begin{split} C_{11} &= A_{11} \cdot B_{11} + A_{12} \cdot B_{21}\\ @@ -49,4 +43,10 @@ C_{21} &= A_{21} \cdot B_{11} + A_{22} \cdot B_{21}\\ C_{22} &= A_{21} \cdot B_{12} + A_{22} \cdot B_{22} \end{split} \end{equation} -explizit geschrieben werden. +der einzelnen Terme geschrieben werden. +\begin{figure} + \center + \includegraphics[]{papers/multiplikation/images/mm_visualisation} + \caption{Matrizen Multiplikation} + \label{multiplikation:fig:mm_viz} +\end{figure}
\ No newline at end of file diff --git a/buch/papers/multiplikation/images/bigo.pdf b/buch/papers/multiplikation/images/bigo.pdf Binary files differindex dfa2ba4..a2599fa 100644 --- a/buch/papers/multiplikation/images/bigo.pdf +++ b/buch/papers/multiplikation/images/bigo.pdf diff --git a/buch/papers/multiplikation/images/bigo.tex b/buch/papers/multiplikation/images/bigo.tex index e3293e4..71826f5 100644 --- a/buch/papers/multiplikation/images/bigo.tex +++ b/buch/papers/multiplikation/images/bigo.tex @@ -39,67 +39,73 @@ \begin{document} \begin{tikzpicture} + \begin{axis}[ - axis lines = left, + xmode=log, + ymode=log, + log ticks with fixed point, xlabel = $n$ (Data Input), ylabel = {$t$ (time)}, legend pos=north east, very thick, - ymax = 500, + grid=minor, + ymax = 100000, + ymin = 0.5, + xmin = 1, yticklabels=\empty, xticklabels=\empty, scale only axis=true, width=12cm, height=6cm, ] \addplot [ - domain= 1:20, + domain= 1:50, samples=100, color=red, ] {1}; \addlegendentry{$\mathcal{O}(1)$} \addplot [ - domain= 1:20, + domain= 1:50, samples=100, color=green, ] {x}; \addlegendentry{$\mathcal{O}(n)$} \addplot [ - domain= 1:20, + domain= 1:50, samples=100, color=blue, ] {x^2}; -\addlegendentry{$\mathcal{O}(n^2)$} +\addlegendentry{$\mathcal{O}\left(n^2\right)$} \addplot [ - domain= 1:10, + domain= 1:50, samples=100, color=purple, ] {x^3}; -\addlegendentry{$\mathcal{O}(n^3)$} +\addlegendentry{$\mathcal{O}\left(n^3\right)$} \addplot [ - domain= 1:10, + domain= 1:50, samples=100, color=black, ] -{exp(x)}; -\addlegendentry{$\mathcal{O}(e^n)$} +{exp(x) - 1.7}; +\addlegendentry{$\mathcal{O}\left(e^n\right)$} \addplot [ - domain= 1:20, + domain= 1:50, samples=100, color=orange, ] -{log2(x)}; +{log2(x)+1}; \addlegendentry{$\mathcal{O}(\log n)$} \addplot [ - domain= 1:20, + domain= 1:50, samples=100, color=gray, ] -{x*log2(x)}; +{x*log2(x)+1}; \addlegendentry{$\mathcal{O}(n \log n)$} \end{axis} \end{tikzpicture} diff --git a/buch/papers/multiplikation/images/strassen.pdf b/buch/papers/multiplikation/images/strassen.pdf Binary files differindex 9899dcb..a30fdaa 100644 --- a/buch/papers/multiplikation/images/strassen.pdf +++ b/buch/papers/multiplikation/images/strassen.pdf diff --git a/buch/papers/multiplikation/images/strassen.tex b/buch/papers/multiplikation/images/strassen.tex index 797772b..5cf39b4 100644 --- a/buch/papers/multiplikation/images/strassen.tex +++ b/buch/papers/multiplikation/images/strassen.tex @@ -81,13 +81,13 @@ \node at (-3,-10) {$C_{12}=$} ; \node at (-3,-5) {$C_{11}=$} ; - \node at (5,-2) {I}; - \node at (10,-2) {II}; - \node at (15,-2) {III}; - \node at (20,-2) {IV}; - \node at (25,-2) {V}; - \node at (30,-2) {VI}; - \node at (35,-2) {VII}; + \node at (5,-2) {P}; + \node at (10,-2) {Q}; + \node at (15,-2) {R}; + \node at (20,-2) {S}; + \node at (25,-2) {T}; + \node at (30,-2) {U}; + \node at (35,-2) {V}; } diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 83be814..8bdbf2c 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -4,16 +4,16 @@ % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{L\"osungsmethoden} -\rhead{L\"osungsmethoden} +\section{Algorithmen} +\rhead{Algorithmen} In diesem Abschnitt werden mehrere Algorithmen zur Berechnung der Matrizenmultiplikation vorgestellt, auch werden Libraries zur automatisierten Verwendung von vordefinierten Algorithmen gezeigt. \subsection{Standard Algorithmus} -Der Standard Methode kann im Algorithmus \ref{multiplikation:alg:smm} entnommen werden. +Die Standardmethode kann im Algorithmus \ref{multiplikation:alg:smm} entnommen werden. Hierf\"ur wurde die Gleichung \eqref{multiplikation:eq:MM} direkt implementiert. -Die \texttt{For i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix, die \texttt{For j} Schleife iteriert \"uber alle Spalten der $\mathbf{B}$ Matrix und die \texttt{For k} Schleife iteriert \"uber alle Eintr\"age dieser Zeilen bzw. Spalten. +Die \texttt{for i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix, die \texttt{for j} Schleife iteriert \"uber alle Spalten der $\mathbf{B}$ Matrix und die \texttt{for k} Schleife iteriert \"uber alle Eintr\"age dieser Zeilen bzw. Spalten. \begin{algorithm}\caption{Matrix Multiplication} \label{multiplikation:alg:smm} @@ -39,16 +39,18 @@ Die \texttt{For i} Schleife iteriert \"uber alle Zeilen der $\mathbf{A}$ Matrix, \end{algorithmic} \end{algorithm} -Die Laufzeit dieser Struktur mit drei \texttt{For} Schleifen ist $\mathcal{O}(n^3)$ +Die Laufzeit dieser Struktur mit drei \texttt{For} Schleifen ist $\mathcal{O}\left(n^3\right)$ \subsubsection{Divide and Conquer Methode} -F\"ur gewisse Algorithmen f\"uhren \textit{Divide and Conquer} Ans\"atze zu markant besseren Laufzeiten. -Das bekannteste Beispiel ist wohl die \textit{Fast Fourier Transform} wobei die Laufzeit von $\mathcal{O}(n^2)$ zu $\mathcal{O}(n \log n)$ verbessert werden kann. +F\"ur gewisse Algorithmen f\"uhren \textit{Divide and Conquer} Ans\"atze \cite{multiplikation:DAC} zu markant besseren Laufzeiten. +Die Grundidee ist, dass ein Problem in mehrere, meist simplere und kleinere Teilprobleme aufgeteilt wird. +Das bekannteste Beispiel ist wohl die \textit{Fast Fourier Transform} wobei die Laufzeit von $\mathcal{O}\left(n^2\right)$ zu $\mathcal{O}(n \log n)$ verbessert werden kann. Die Matrizenmultiplikation kann ebenfalls mit solch einem Ansatz berechnet werden. -Zur vereinfachten Veranschaulichung kann die Situation, mit $\mathbf{A}$ und $\mathbf{B}$ der gr\"osse $2^n \times 2^n$ verwendet werden. -Die Matrizen $\mathbf{A}$ und $\mathbf{B}$ werden in jeweils vier Blockmatrizen der gr\"osse $2^{n-1} \times 2^{n-1}$ +Zur vereinfachten Veranschaulichung kann die Situation mit $\mathbf{A}$ und $\mathbf{B}$ der Gr\"osse $2^n \times 2^n$ verwendet werden. +Die Matrizen $\mathbf{A}$ und $\mathbf{B}$ werden in jeweils vier Blockmatrizen der Gr\"osse $2^{n-1} \times 2^{n-1}$ aufgeteilt. +Das Matrizen produklt \begin{equation} \mathbf{A}\mathbf{B}= \begin{bmatrix} @@ -64,11 +66,9 @@ Die Matrizen $\mathbf{A}$ und $\mathbf{B}$ werden in jeweils vier Blockmatrizen \mathbf{C}_{11} & \mathbf{C}_{12}\\ \mathbf{C}_{21} & \mathbf{C}_{22} \end{bmatrix} -\end{equation} -aufgeteilt. -Die Berechnung +\end{equation}, \begin{equation} -\mathbf{C}_{ij} = \sum_{k=1}^n \mathbf{A}_{ik} \mathbf{B}_{kj} +\mathbf{C}_{ij} = \sum_{k=1}^n \mathbf{A}_{ik} \mathbf{B}_{kj}. \label{multiplikation:eq:MM_block} \end{equation} ist identisch zu der Gleichung \eqref{multiplikation:eq:MM}, wobei hier f\"ur die Multiplikation die Matrizenmultiplikation verwendet wird. @@ -105,15 +105,11 @@ Der rekursive Aufruf wird bis zu der Gr\"osse der Matrizen von $N = 2 \times 2$ \end{algorithmic} \end{algorithm} -Die Laufzeit dieser rekursiven Funktion kann mit dem \textit{Master Theorem} berechnet werden. -Ohne auf diesen vertieft einzugehen, bestimmt die Anzahl rekursiver Aufrufe der Funktion die Laufzeit. +Die Laufzeit dieser rekursiven Funktion kann mit dem \textit{Master Theorem} \cite{multiplikation:master_theorem} berechnet werden. Das \textit{Master Theorem} bestimmt die Zeitkomplexit\"at von rekursiven Algortihmen. +Ohne auf dieses vertieft einzugehen, bestimmt die Anzahl rekursiver Aufrufe der Funktion die Laufzeit. In diesem Fall wird die Funktion pro Durchlauf acht mal rekursiv aufgerufen, dies f\"uhrt \begin{equation} \label{multiplikation:eq:laufzeitdac} - \mathcal{T}(n) = - \begin{cases} - 1 & \text{if } n \leq 2\\ - 8 \cdot \mathcal{T}(\frac{n}{2}) + n^2 & \text{if } n > 2 - \end{cases} = \mathcal{O}(n^{\log_2 8}) = \mathcal{O}(n^{3}) + \mathcal{T}(n) = 8 \cdot \mathcal{T}\left (\frac{n}{2}\right ) + n^2 = \mathcal{O}(n^{\log_2 8}) = \mathcal{O}\left (n^{3} \right ) \end{equation} zu einer kubischen Laufzeit. Die Addition zweier Matrizen $\mathbf{A} + \mathbf{B} = \mathbf{C}$ hat eine Laufzeit von $\mathcal{O}(n^{2})$ und kann neben dem dominierendem Anteil von $\mathcal{O}(n^{3})$ ignoriert werden. @@ -122,20 +118,20 @@ In diesem Fall hat der \textit{Divide and Conquer} Ansatz zu keiner Verbesserung \subsection{Strassen's Algorithmus} -Strassen's Algorithmus \cite{multiplikation:strassen_1969} beschreibt die Matrizenmultiplikation mit einer Vielzahl von Additionen, Subtraktionen und Multiplikationen. -Die Grundlegenden Terme +Strassen's Algorithmus \cite{multiplikation:strassen_1969} beschreibt die Matrizenmultiplikation mit einer Vielzahl von Additionen, Subtraktionen und Multiplikationen von Blockmatrizen. +Die grundlegenden Terme \begin{equation} \label{multiplikation:eq:strassen} \begin{split} -\text{\textbf{P}} &= (\mathbf{A}_{11} + \mathbf{A}_{22}) \cdot (\mathbf{B}_{11} + \mathbf{B}_{22}) \\ -\text{\textbf{Q}} &= (\mathbf{A}_{21} + \mathbf{A}_{22}) \cdot \mathbf{B}_{11} \\ -\text{\textbf{R}} &= \mathbf{A}_{11} \cdot (\mathbf{B}_{12}-\mathbf{B}_{22}) \\ -\text{\textbf{S}} &= \mathbf{A}_{22} \cdot (-\mathbf{B}_{11}+\mathbf{B}_{21}) \\ -\text{\textbf{T}} &= (\mathbf{A}_{11} + \mathbf{A}_{12}) \cdot \mathbf{B}_{22} \\ -\text{\textbf{U}} &= (-\mathbf{A}_{11} + \mathbf{A}_{21}) \cdot (\mathbf{B}_{11} + \mathbf{B}_{12}) \\ -\text{\textbf{V}} &= (\mathbf{A}_{12} - \mathbf{A}_{22}) \cdot (\mathbf{B}_{21} + \mathbf{B}_{22}) +\text{\textbf{P}} &= \left(\mathbf{A}_{11} + \mathbf{A}_{22}\right ) \cdot \left(\mathbf{B}_{11} + \mathbf{B}_{22}\right ) \\ +\text{\textbf{Q}} &= \left(\mathbf{A}_{21} + \mathbf{A}_{22}\right ) \cdot \mathbf{B}_{11} \\ +\text{\textbf{R}} &= \mathbf{A}_{11} \cdot \left(\mathbf{B}_{12}-\mathbf{B}_{22}\right ) \\ +\text{\textbf{S}} &= \mathbf{A}_{22} \cdot \left(-\mathbf{B}_{11}+\mathbf{B}_{21}\right ) \\ +\text{\textbf{T}} &= \left(\mathbf{A}_{11} + \mathbf{A}_{12}\right ) \cdot \mathbf{B}_{22} \\ +\text{\textbf{U}} &= \left(-\mathbf{A}_{11} + \mathbf{A}_{21}\right ) \cdot \left(\mathbf{B}_{11} + \mathbf{B}_{12}\right ) \\ +\text{\textbf{V}} &= \left(\mathbf{A}_{12} - \mathbf{A}_{22}\right ) \cdot \left(\mathbf{B}_{21} + \mathbf{B}_{22}\right ) \end{split} \end{equation} -aus $\mathbf{A}$ und $\mathbf{B}$, werden f\"ur die Berechnung der Matrix $\mathbf{C}$ +aus $\mathbf{A}$ und $\mathbf{B}$, werden f\"ur die Berechnung der Bl\"ocke \begin{equation} \label{multiplikation:eq:strassen2} \begin{split} \mathbf{C}_{11} &= \text{\textbf{P}} + \text{\textbf{S}} - \text{\textbf{T}} + \text{\textbf{V}} \\ @@ -144,7 +140,7 @@ aus $\mathbf{A}$ und $\mathbf{B}$, werden f\"ur die Berechnung der Matrix $\math \mathbf{C}_{22} &= \text{\textbf{P}} + \text{\textbf{R}} - \text{\textbf{Q}} + \text{\textbf{U}} \end{split} \end{equation} -gebraucht. +der Matrix $\mathbf{C}$ gebraucht. \begin{algorithm}\caption{Strassen Matrix Multiplication} \label{multiplikation:alg:strassen} \setlength{\lineskip}{7pt} @@ -190,7 +186,11 @@ gebraucht. \EndFunction \end{algorithmic} \end{algorithm} -Strassens's Methode wird in der Abbildung \ref{multiplikation:fig:strassen} grafisch dargestellt. +Strassen's Methode wird in der Abbildung \ref{multiplikation:fig:strassen} grafisch dargestellt. +Jedes Feld steht f\"ur eine Multiplikation zweier Matrizenelementen von $\mathbf{A}$ oder $\mathbf{B}$ . +Die gr\"unen Felder auf der linken Seite, zeigen die addition welche f\"ur den dazugeh\"origen Term ben\"otigt wird. +Die sieben Spalten beschreiben die Matrizen $\mathbf{P,Q,R, \dotsb, V}$. +Rote Felder stehen f\"ur eine Subtraktion und die gr\"unen f\"ur eine Addition. \begin{figure} \center \includegraphics[width=\linewidth]{papers/multiplikation/images/strassen.pdf} @@ -202,17 +202,14 @@ Die Funktion wird sieben mal rekursiv aufgerufen. Dies f\"uhrt zu einer Laufzeit von \begin{equation} \label{multiplikation:eq:laufzeitstrassen} \mathcal{T}(n) = -\begin{cases} -1 & \text{if } n \leq 2\\ -7 \cdot \mathcal{T}(\frac{n}{2}) + n^2 & \text{if } n > 2 -\end{cases} = \mathcal{O}(n^{\log_2 7}) = \mathcal{O}(n^{2.8074}) +7 \cdot \mathcal{T}(\frac{n}{2}) + n^2 = \mathcal{O}\left(n^{\log_2 7}\right ) = \mathcal{O}\left(n^{2.8074} \right ) \end{equation} -und ist somit schneller als die Standard Methode. +und ist somit schneller als die Standardmethode. \subsection{Winograd's Algorithmus} -Ein weiterer Ansatz lieferte Shmuel Winograd im Jahre 1968 \cite{multiplikation:winograd_1968}. -Er zeigte einen neuen Algorithmus f\"ur das +Einen weiteren Ansatz lieferte Shmuel Winograd im Jahre 1968 \cite{multiplikation:winograd_1968}. +Er beschrieb einen neuen Algorithmus f\"ur das \begin{equation} \langle x,y \rangle = \sum_{i=1}^{n}x_i y_i \end{equation} @@ -236,6 +233,7 @@ Das Skalarprodukt ist nun geben mit Angenommen man hat $N$ Vektoren mit welchen man $T$ Skalarprodukte berechnen m\"ochte. Daf\"ur werden $N\lfloor n/2 \rfloor + T\lfloor (n+1)/2 \rfloor $ Multiplikationen ben\"otigt. + Eine Matrizenmultiplikation mit $\mathbf{A}$ einer $m \times n$ und $\mathbf{B}$ einer $n \times p$ Matrix, entspricht $N=m+p$ Vektoren mit welchen man $T=mp$ Skalarprodukte berechnet. Dies f\"uhrt zu \begin{equation} @@ -243,8 +241,8 @@ Dies f\"uhrt zu \end{equation} Multiplikationen. Wenn $m,p,n$ gross werden, dominiert der Term $\frac{mpn}{2}$ und es werden $\frac{mpn}{2}$ Multiplikationen ben\"otigt. -Was im Vergleich zu den $mpn$ Multiplikation der Standard Methode nur die H\"alfte ist. -Die Implementation kann im Algorithmus \ref{multiplikation:alg:winograd} entnommen werden. +Was im Vergleich zu den $mpn$ Multiplikation der Standardmethode nur die H\"alfte ist. +Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen werden. \begin{algorithm}\caption{Winograd Matrix Multiplication} \setlength{\lineskip}{7pt} diff --git a/buch/papers/multiplikation/problemstellung.tex b/buch/papers/multiplikation/problemstellung.tex index b20a791..fed6a9f 100755 --- a/buch/papers/multiplikation/problemstellung.tex +++ b/buch/papers/multiplikation/problemstellung.tex @@ -6,24 +6,24 @@ \section{Problemstellung} \rhead{Problemstellung} Dank 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. -Wobei gezielt auf Algorithmen, welche das Problem schneller als der Standard Algorithmus L\"osen eingegangen wird. +Das Ziel dieses Papers ist, verschiedenen Algorithmen der Matrizenmultiplikation vorzustellen. +Gezielt werden auf Algorithmen, welche das Problem schneller als der Standard Algorithmus L\"osen eingegangen. \subsection{Big $\mathcal{O}$ Notation} Die Big $\mathcal{O}$ Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus \cite{multiplikation:bigo}. -$f(x) \in \mathcal{O}(g(x))$ besagt das die Funktion $f$ nicht wesentlich schneller w\"achst als $g$ wenn $x \rightarrow \infty$. +$f(x) \in \mathcal{O}(g(x))$ besagt, dass die Funktion $f$ nicht wesentlich schneller w\"achst als $g$ wenn $x \rightarrow \infty$. Vereinfacht werden f\"ur Algorithmen die folgende Notation verwendet: \begin{itemize} \item $f \in \mathcal{O}(1) \rightarrow f$ ist beschr\"ankt \item $f \in \mathcal{O}(n) \rightarrow f$ w\"achst linear - \item $f \in \mathcal{O}(n^2) \rightarrow f$ w\"achst quadratisch + \item $f \in \mathcal{O}\left (n^2 \right ) \rightarrow f$ w\"achst quadratisch \item $f \in \mathcal{O}(\log n) \rightarrow f$ w\"achst logarithmisch \item $f \in \mathcal{O}(n \log n) \rightarrow f$ hat super-lineares Wachstum - \item $f \in \mathcal{O}(e^n) \rightarrow f$ w\"achst exponentiell + \item $f \in \mathcal{O}\left (e^n \right ) \rightarrow f$ w\"achst exponentiell \item usw. \end{itemize} -In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die Verschiedenen Laufzeiten miteinander verglichen werden. +In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufzeiten miteinander verglichen werden. \begin{figure} \center @@ -33,9 +33,11 @@ In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die Verschiedenen Laufze \end{figure} \subsubsection{Beispiel Algorithmen} + +Folgend einige Beispiele von Algorithmen welche zu einer bestimmten Zeitkomplexit\"atsklassen geh\"oren. \paragraph{Beschr\"ankter Algorithmus} -Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmus \ref{multiplikation:alg:b1} entnommen werden. +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. \begin{algorithm}\caption{} \label{multiplikation:alg:b1} @@ -47,7 +49,7 @@ Ein Beispiel eines Beschr\"ankter Verhalten $\mathcal{O}(1)$, kann im Algorithmu \end{algorithmic} \end{algorithm} -Wobei Konstanten nicht beachtet werden, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$. +Konstanten werden nicht beachtet, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$. \begin{algorithm}\caption{} \label{multiplikation:alg:b2} @@ -63,13 +65,14 @@ Wobei Konstanten nicht beachtet werden, der Algorithmus \ref{multiplikation:alg: \paragraph{Linearer Algorithmus} -Folgender Algorithmus \ref{multiplikation:alg:l1} hat ein lineares $\mathcal{O}(n)$ Verhalten. +Folgender Algorithmus \ref{multiplikation:alg:l1} hat ein lineares Verhalten. +Die \texttt{for}-Schleife wird $n$-mal durchgef\"hrt und f\"uhrt deshalb zu $\mathcal{O}(n)$. \begin{algorithm}\caption{} \setlength{\lineskip}{7pt} \begin{algorithmic} \label{multiplikation:alg:l1} - \Function{L}{$\mathbf{A}, \mathbf{B}$,n} + \Function{L}{$\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] $ @@ -83,7 +86,9 @@ Folgender Algorithmus \ref{multiplikation:alg:l1} hat ein lineares $\mathcal{O}( \paragraph{Quadratischer Algorithmus} -Folgender Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches $\mathcal{O}(n^2)$ Verhalten. +Folgender Algorithmus \ref{multiplikation:alg:q1} hat ein quadratisches Verhalten. +Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchgef\"hrt und f\"uhrt deshalb zu $\mathcal{O}\left(n^2\right)$. + \begin{algorithm}[H]\caption{} \label{multiplikation:alg:q1} diff --git a/buch/papers/multiplikation/references.bib b/buch/papers/multiplikation/references.bib index 9d76e8e..63cb976 100755 --- a/buch/papers/multiplikation/references.bib +++ b/buch/papers/multiplikation/references.bib @@ -63,3 +63,23 @@ month = {7}, day = {27} } + +@online{multiplikation:master_theorem, + title = {Master theorem (analysis of algorithms)}, + url = {https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)}, + date = {2021-07-28}, + year = {2021}, + month = {7}, + day = {28} +} + + +@online{multiplikation:DAC, + title = {Divide-and-conquer algorithm}, + url = {https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm}, + date = {2021-07-28}, + year = {2021}, + month = {7}, + day = {28} +} + |