1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
%
% teil1.tex -- Beispiel-File für das Paper
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\section{Laufzeiten von Algorithmen}
\rhead{Laufzeiten von Algorithmen}
Wegen der breiten Anwendung der Matrizenmultiplikation ist eine effiziente Ausführung dieser Operation von grosser Bedeutung.
Das Ziel dieses Papers ist, verschiedenen Algorithmen der Matrizenmultiplikation vorzustellen.
Gezielt wird auf Algorithmen eingegangen, welche das Problem schneller als der Standardalgorithmus l\"osen.
\label{muliplikation:sec:bigo}
Die Big-$\mathcal{O}$-Notation beschreibt die Laufzeitkomplexit\"at eines Algorithmus in Relation zur Inputgrösse \cite{multiplikation:bigo}.
\index{BigOnotation@Big-$\mathcal{O}$-Notation}%
\index{Laufzeitkomplexität}%
$f(n) \in \mathcal{O}(g(n))$ besagt, dass die Funktion $f$ nicht wesentlich schneller w\"achst als $g$, wenn $n \rightarrow \infty$.
%Dies ist gegeben, falls es für $f \in \mathcal{O}(n^k)$ eine Konstante $C$ gibt, mit $f(n) \leq Cn^k$.
Dies ist gegeben, falls es für $f(n) \in \mathcal{O}(g(n))$ eine Konstante $C$ gibt, mit $f(n) \leq Cg(n)$.
% Es gibt eine Konstante $K$ derart, dass $f(x) \le K g(x)$ für $x\to\infty$.
Vereinfacht werden f\"ur Algorithmen die folgenden Sprechweisen 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}(\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 usw.
\end{itemize}
Konstanten werden nicht beachtet, eine Laufzeit von $4n^2$ führt, für $n \rightarrow \infty$ zu $\mathcal{O}(n^2)$.
In der Abbildung \ref{multiplikation:fig:bigo} k\"onnen die verschiedenen Laufzeiten miteinander verglichen werden.
Bei einer doppelt logarithmischen Darstellung werden Polynome der Form $f(n) = n^k$ als Geraden und Exponentialfunktionen der Form $f(n) = a^n$ als nach oben gekr\"ummte Kurven abgebildet.
\subsubsection{Beispielalgorithmen}
Es folgen einige Beispiele von Algorithmen, welche einer bestimmten Zeitkomplexit\"atsklasse zugeteilt werden k\"onnen.
\begin{table}[t]
\begin{tabular}{ll}
\begin{minipage}{0.48\textwidth}
\begin{algorithm}[H]\footnotesize\caption{}
\label{multiplikation:alg:b1}
\setlength{\lineskip}{7pt}
\begin{algorithmic}
\Function{B1}{$a, b$}
\State \textbf{return} $a+b$
\EndFunction
\State
\State
\end{algorithmic}
\end{algorithm}
\end{minipage}
&
\begin{minipage}{0.48\textwidth}
\begin{algorithm}[H]\footnotesize\caption{}
\label{multiplikation:alg:b2}
\setlength{\lineskip}{7pt}
\begin{algorithmic}
\Function{B2}{$a, b$}
\State $ x \gets a+b $
\State $ y \gets a \cdot b $
\State \textbf{return} $x+y$
\EndFunction
\end{algorithmic}
\end{algorithm}
\end{minipage} \\
\begin{minipage}{0.48\textwidth}
\begin{algorithm}[H]\footnotesize\caption{}
\setlength{\lineskip}{7pt}
\begin{algorithmic}
\label{multiplikation:alg:linear}
\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] $
\EndFor
\State \textbf{return} $sum$
\EndFunction
\State
\State
\end{algorithmic}
\end{algorithm}
\end{minipage}
&
\begin{minipage}{0.48\textwidth}
\begin{algorithm}[H]\footnotesize\caption{}
\label{multiplikation:alg:q1}
\setlength{\lineskip}{7pt}
\begin{algorithmic}
\Function{Q}{$\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}
\end{minipage}
\end{tabular}
\end{table}
%\begin{table}
% \begin{tabular}[t]{ll}
% \end{tabular}
%\end{table}
\paragraph{Beschr\"ankter Algorithmus}
\index{beschränkter Algorithmus}%
\index{Algorithmus, beschränkt}%
Algorithmus~\ref{multiplikation:alg:b1} ist ein Beispiel mit beschränkter Laufzeit $\mathcal{O}(1)$.
Da $a$ und $b$ Skalare sind, hat keine Gr\"osse $n$ einen Einfluss auf die Laufzeit.
Wie erwähnt werden Konstanten nicht beachtet, der Algorithmus \ref{multiplikation:alg:b2} f\"uhrt ebenso zu $\mathcal{O}(1)$ und nicht zu $\mathcal{O}(2)$.
\paragraph{Linearer Algorithmus}
\index{linearer Algorithmus}%
\index{Algorithmus, linear}%
Der
%Algorithmus~\ref{multiplikation:alg:linear}
Algorithmus~3
hat ein lineares Verhalten.
Die \texttt{for}-Schleife wird $n$-mal durchlaufen und f\"uhrt deshalb zu $\mathcal{O}(n)$.
\paragraph{Quadratischer Algorithmus}
\index{quadratischer Algorithmus}%
\index{Algorithmus, quadratisch}%
Der Algorithmus~\ref{multiplikation:alg:q1} hat ein quadratisches Verhalten.
Die beiden \texttt{for}-Schleifen werden jeweils $n$-mal durchlaufen und f\"uhren deshalb zu $\mathcal{O} (n^2 )$.
\begin{figure}
\center
\includegraphics[]{papers/multiplikation/images/bigo}
\caption{Laufzeiten von verschiedenen Zeitkomplexitäten. Bei einer doppelt logarithmischen Darstellung werden Polynome der Form $f(n) = n^k$ als Geraden und Exponentialfunktionen der Form $f(n) = a^n$ als nach oben gekr\"ummte Kurven dargestellt.}
\label{multiplikation:fig:bigo}
\end{figure}
|
