sheet.tex (13242B)
1 \documentclass[11pt, a4paper, twoside]{article} 2 \usepackage[ 3 a4paper, 4 headsep=5mm, 5 footskip=0mm, 6 top=12mm, 7 left=10mm, 8 right=10mm, 9 bottom=10mm 10 ]{geometry} 11 \usepackage{amsmath} 12 \usepackage{amsfonts} 13 \usepackage{multicol} 14 \usepackage[noend]{algorithm2e} 15 \usepackage[utf8]{inputenc} 16 \usepackage{fancyhdr} 17 \usepackage{hyperref} 18 \hypersetup{ 19 colorlinks=true, 20 linkcolor=blue, 21 filecolor=magenta, 22 urlcolor=cyan, 23 pdftitle={Overleaf Example}, 24 pdfpagemode=FullScreen, 25 } 26 27 \setlength{\algomargin}{0pt} 28 29 \begin{document} 30 \pagestyle{fancy} 31 \fancyhead{} 32 \fancyhead[L]{Algorithmen 1} 33 \fancyhead[R]{Gero Beckmann - \url{https://github.com/Geronymos/algo-cheatsheet}} 34 \fancyfoot{} 35 \fancyfoot[R]{\thepage} 36 \section{Laufzeit} 37 \hspace*{-.5cm} 38 \begin{tabular}{ l l l l } 39 Notations & Asymptotischer Vergleich & Formale Definition & Grenzen \\ 40 $f(n) \in \omega(g(n))$& 41 $f(n)$ wächst schneller als $g(n)$ & 42 $\forall c \exists n_0 \forall n > n_0 f(n) > c \cdot g(n)$ & 43 $$$\lim\sup\limits_{n \rightarrow \infty}\frac{f}{g} = \infty$$$ \\ 44 45 $f(n) \in \Omega(g(n))$ & 46 $f(n)$ wächst min. so schnell wie $g(n)$ & 47 $\exists c \exists n_0 \forall n > n_0 c \cdot f(n) \leq g(n)$ & 48 $$$0 < \liminf\limits_{n \rightarrow \infty}\frac{f}{g} \leq \infty$$$ \\ 49 50 \( f(n) \in \Theta(g(n)) \) & 51 $f(n)$ und $g(n)$ wachsen gleich schnell & 52 $f(n) \in \mathcal{O}(g(n)) \wedge f(n) \in \Omega(g(n))$ & 53 $$$0 < \lim\limits_{n \rightarrow \infty}\frac{f}{g} < \infty$$$ \\ 54 55 \( f(n) \in \mathcal{O}(g(n)) \) & 56 $f(n)$ wächst max. so schnell wie $g(n)$ & 57 $\exists c \exists n_0 \forall n > n_0 f(n) \leq c \cdot g(n)$ & 58 $$$0 \leq \limsup\limits_{n \rightarrow \infty}\frac{f}{g} < \infty$$$ \\ 59 60 \( f(n) \in o(g(n)) \) & 61 $f(n)$ wächst langsamer als $g(n)$ & 62 $\forall c \exists n_0 \forall n > n_0 c \cdot f(n) < g(n)$ & 63 $$$\lim\limits_{n \rightarrow \infty} \frac{f}{g} = \infty$$$ \\ 64 65 \end{tabular} 66 67 \subsection{Vergleich} 68 \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} 69 $1$ & $\log^*n$ & $\log n$ & $\log^2n$ & $\sqrt[3]{n}$ & 70 $\sqrt{n}$ & $n$ & $n^2$ & $n^3$ & $n^{\log n}$ & 71 $2^{\sqrt{n}}$ & $2^n$ & $3^n$ & $4^n$ & $n!$ & $2^{n^2}$ 72 \end{tabular} 73 74 \begin{multicols}{3} 75 76 \subsubsection*{Transitivität} 77 78 $f_1(n) \in \mathcal{O}(f_2(n)) \wedge f_2(n) \in\mathcal{O}(f_3(n))$ \\ 79 $\Rightarrow f_1(n) \in \mathcal{O}(f_3(n))$ 80 81 \subsubsection*{Summen} 82 83 $f_1(n) \in \mathcal{O}f_3(n)) \wedge f_2(n) \in \mathcal{O}(f_3(n))$ \\ 84 $\Rightarrow f_1(n) + f_2(n) \in \mathcal{O}(f_3(n))$ 85 86 \subsubsection*{Produkte} 87 88 $f_1(n) \in \mathcal{O}(g_1(n)) \wedge f_2(n) \in \mathcal{O}(g_2(n))$ \\ 89 $\Rightarrow f_1(n) \cdot f_2(n) \in \mathcal{O}(g_1(n) \cdot g_2(n))$ 90 91 92 \columnbreak 93 94 \subsection{Master-Theorem} 95 96 Sei $T(n) = a \cdot T(\frac{n}{b}) + f(n)$ mit $f(n) \in \Theta(n^c)$ und i 97 $T(1) \in \Theta(1)$. Dann gilt 98 $ 99 T(n) \in \begin{cases} 100 \Theta(n^c) &\text{wenn } a < b^c, \\ 101 \Theta(n^c \log n) &\text{wenn } a = b^c, \\ 102 \Theta(n^{\log_b(a)}) &\text{wenn } a > b^c. 103 \end{cases} 104 $ 105 106 \subsubsection{Monome} 107 108 \begin{itemize} 109 \item $a \leq b \Rightarrow n^a \in \mathcal{O}(n^b)$ 110 \item $n^a \in \Theta(n^b) \Leftrightarrow a = b$ 111 \item $\sum_{v \in V}deg(v) = \Theta(m)$ 112 \item $\forall n \in \mathbb{N}: \sum^n_{k=0}k = \frac{n(n+1)}{2}$ 113 \item $ 114 \sum^b_{i=a}c^i \in \begin{cases} 115 \Theta(c^a) &\text{wenn } c < 1, \\ 116 \Theta(c^b) &\text{wenn } c > 1, \\ 117 \Theta(b-a) &\text{wenn } c = 1. 118 \end{cases} 119 $ 120 \item $\log(ab) = \log(a) + \log(b)$ 121 \item $\log(\frac{a}{b}) = \log(a) - \log(b)$ 122 \item $a^{\log_a(b)} = b$ 123 \item $a^x = e^{ln(a) \cdot x}$ 124 \item $\log(a^b) = b \cdot \log(a)$ 125 \item $\log_b(n) = \frac{\log_a(n)}{\log_a(b)}$ 126 \end{itemize} 127 128 %\subsubsection{Konstante Faktoren} 129 % 130 %$a \cdot f(n) \in \Theta(f(n))$ 131 132 133 \end{multicols} 134 135 \begin{minipage}{0.7\textwidth} 136 137 \section{Sortieren} 138 139 \begin{tabular}[t]{c || c | c | c | c} 140 Algorithmus & best case & average & worst & Stabilität \\ 141 \hline 142 Insertion-Sort & 143 $\mathcal{O}(n)$ & $\mathcal{O}(n^2)$ & $\mathcal{O}(n^2)$ & stabil\\ 144 Bubble-Sort & 145 $\mathcal{O}(n)$ & $\mathcal{O}(n^2)$ & $\mathcal{O}(n^2)$ & stabil\\ 146 Merge-Sort & 147 $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & stabil\\ 148 Quick-Sort & 149 $\mathcal{O}(n \log n)$ & $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & i.A. nicht stabil\\ 150 Heap-Sort & 151 $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & nicht stabil\\ 152 \hline 153 Bucket-Sort & 154 $\Theta(n+m)$ & $\Theta(n+m)$ & $\Theta(n+m)$ & 155 stabil $e \in [0, m)$\\ 156 Radix-Sort & 157 $\Theta(c \cdot n)$ & $\Theta(c\cdot n)$ & $\Theta(c\cdot n)$ & 158 stabil $e \in [0, n^c)$\\ 159 \end{tabular} 160 \end{minipage} 161 \hfill 162 \begin{minipage}{0.3\textwidth} 163 \subsection{Heaps} 164 165 \begin{tabular}[t]{c || c} 166 Bin.-Heap & Laufzeit \\ 167 \hline 168 push(x) & $\mathcal{O}(\log n)$ \\ 169 popMin() & $\mathcal{O}(\log n)$ \\ 170 decPrio(x, x') & $\mathcal{O}(\log n)$ \\ 171 build([$\mathbb{N}$; n]) & $\mathcal{O}(n)$ 172 \end{tabular} 173 174 \begin{itemize} 175 \item linkes Kind: $2v + 1$ 176 \item rechts Kind: $2v + 2$ 177 \item Elternknoten: $ \lfloor \frac{v - 1}{2} \rfloor $ 178 \end{itemize} 179 180 \end{minipage} 181 182 183 \begin{multicols}{2} 184 185 \section{Datenstrukturen} 186 187 \subsection{Listen} 188 189 \begin{tabular}{c || c | c | c || c} 190 Operation & DLL & SLL & Array & Erklärung(*) \\ 191 \hline 192 first & 1 & 1 & 1 & \\ 193 last & 1 & 1 & 1 & \\ 194 insert & 1 & 1* & n & nur insertAfter \\ 195 remove & 1 & 1* & n & nur removeAfter \\ 196 pushBack & 1 & 1 & 1* & amortisiert \\ 197 pushFront & 1 & 1 & n & \\ 198 popBack & 1 & n & 1* & amortisiert \\ 199 popFront & 1 & 1 & n & \\ 200 concat & 1 & 1 & n & \\ 201 splice & 1 & 1 & n \\ 202 findNext & n & n & n 203 204 \end{tabular} 205 206 \subsection{Hash-Tabelle} 207 $\mathcal{H}$ heißt \textbf{universell}, wenn für ein zufälliges gewähltes 208 $h \in \mathcal{H}$ gilt: $U \rightarrow \{0, ..., m-1\}$ \\ 209 $\forall k, l \in U, k \neq l: Pr[h(k) = h(l)] = \frac{1}{m}$ \\ 210 $h_{a,b}(k) = ((a\cdot k + b) \mod p) \mod m$ 211 212 \subsection{Graphen} 213 214 \begin{tabular}{c || c} 215 Algorithmus & Laufzeit \\ 216 \hline 217 BFS/DFS & $\Theta(n+m)$\\ 218 topoSort & $\Theta(n)$\\ 219 Kruskal & $\Theta(m \log n)$\\ 220 Prim & $\Theta((n+m)\log n)$ \\ 221 Dijksta & $\Theta((n + m) \log n)$\\ 222 Bellmann-Ford & $\Theta(nm)$\\ 223 Floyd-Warshall & $\Theta(n^3)$ \\ 224 \end{tabular} 225 226 \end{multicols} 227 228 \newpage 229 230 \begin{multicols}{2} 231 232 \subsubsection{DFS} 233 234 \begin{tabular}{c || c | c} 235 Kante & DFS & FIN \\ 236 \hline 237 Vorkante & klein $\rightarrow$ groß & groß $\rightarrow$ klein \\ 238 Rückkante & groß $\rightarrow$ klein & klein $\rightarrow$ groß \\ 239 Querkante & groß $\rightarrow$ klein & groß $\rightarrow$ klein \\ 240 Baumkante & klein $\rightarrow$ groß & groß $\rightarrow$ klein \\ 241 \end{tabular} 242 \subsection{Bäume} 243 \subsubsection{Heap} 244 Priorität eines Knotens $\geq (\leq)$ Priorität der Kinder. 245 \textbf{BubbleUp}, \textbf{SinkDown}. \textbf{Build} mit \textbf{sinkDown} 246 beginnend mit letztem Knoten der vorletzten Ebene weiter nach oben. 247 \textbf{decPrio} entweder updaten, Eigenschaft wiederherstellen; löschen, 248 mit neuer Prio einfügen oder Lazy Evaluation. 249 250 \subsubsection{(ab)-Baum} 251 Balanciert. \textbf{find}, \textbf{insert}, \textbf{remove} in 252 $\Theta(log n)$. Zu wenig Kinder: \textbf{rebalance} / \textbf{fuse}. 253 Zu viele Kinder: \textbf{split}. 254 255 Linker Teilbaum $\leq$ Schlüssel k $<$ rechter Teilbaum 256 257 Unendlich-Trick, für Invarianten. 258 259 \subsection{Union-Find} 260 Rang: höhe des Baums, damit ist die Höhe h mind. $2^h$ Knoten, h $\in 261 \mathcal{O}(\log n)$. 262 Union hängt niedrigen Baum an höherrängigen Baum. Pfadkompression hängt alle 263 Knoten bei einem \textbf{find} an die Wurzel. 264 265 266 \columnbreak 267 \section{Amortisierte Analyse} 268 269 \subsection{Aggregation} 270 Summiere die Kosten für alle Operationen. Teile Gesamtkkosten durch Anzahl 271 Operationen. 272 273 \subsection{Charging} 274 Verteile Kosten-Tokens von teuren zu günstigen Operationen (Charging). Zeige: 275 jede Operation hat am Ende nur wenige Tokens. 276 277 \subsection{Konto} 278 Günstige Operationen bezahlen mehr als sie tatsächlich kosten (ins Konto 279 einzahlen). Teure Operationen bezahlen tatsächliche Kosten zum Teil mit 280 Guthaben aus dem Konto. \textbf{Beachte: Konto darf nie negativ sein!} 281 282 \subsection{Potential (Umgekehrte Kontomethode)} 283 Definiere Kontostand abhängig vom Zustand der Datenstruktur 284 (Potentialfunktion) 285 286 amortisierten Kosten = tatsächliche Kosten 287 $+ \Phi(S_\text{nach}) -\Phi(S_\text{vor})$ 288 289 \end{multicols} 290 291 \section{Pseudocode} 292 \scriptsize 293 \begin{minipage}{.25\linewidth} 294 \begin{algorithm}[H] 295 DFS(Graph G, Node v) \\ 296 mark v \\ 297 dfs[v] := dfsCounter++ \\ 298 low[v] := dfs[v] \\ 299 \For{u $\in$ N(v)}{ 300 \eIf{not marked u}{ 301 dist[u] := dist[v] + 1 \\ 302 par[u] := v \\ 303 DFS(G, u) \\ 304 low[v] := min(low[v], low[u]) \\ 305 }{low[v] := min(low[v], dfs[u])} 306 } 307 fin[v] := fin++ \\ 308 \end{algorithm} 309 \end{minipage} 310 \begin{minipage}{.25\linewidth} 311 \begin{algorithm}[H] 312 topoSort(Graph G) \\ 313 fin := [$\infty$; n] \\ 314 curr := 0 \\ 315 \For{Node v in V}{ 316 \If{v is colored}{DFS(G,v)} 317 } 318 return V sorted by decreasing fin \\ 319 \end{algorithm} 320 \end{minipage} 321 \begin{minipage}{.25\linewidth} 322 \begin{algorithm}[H] 323 Kruskal(Graph G) \\ 324 U := Union-Find(G.v) \\ 325 PriorityQueue Q := empty \\ 326 \For{Edge e in E}{Q.push(e, len(e))} 327 \While{Q $\neq \emptyset$}{ 328 e := Q.popMin() \\ 329 \If{U.find(v) $\neq$ U.find(u)}{ 330 L.add(e) \\ 331 U.union(v, u) \\ 332 } 333 } 334 \end{algorithm} 335 \end{minipage} 336 \begin{minipage}{.25\linewidth} 337 \begin{algorithm}[H] 338 Prim(Graph G) \\ 339 Priority Queue Q := empty \\ 340 p := [0; n] \\ 341 \For{Node v in V}{ 342 Q.push(v, $\infty$) \\ 343 } 344 \While{Q $\neq \emptyset$}{ 345 u := Q.popMin() \\ 346 \For{Node v in N(u)}{ 347 \If{v $\in$ Q $\wedge$ (len(u, v) $<$ Q.prio(v))}{ 348 p[v] = u \\ 349 Q.decPrio(v, len(u, v) \\ 350 } 351 } 352 } 353 \end{algorithm} 354 \end{minipage} 355 \begin{minipage}{.25\linewidth} 356 \begin{algorithm}[H] 357 BFS(Graph G, Start s, Goal z) \\ 358 Queue Q := empty queue \\ 359 Q.push(s) \\ 360 s.layer = 0 \\ 361 \While{Q $\neq \emptyset$}{ 362 u := Q.pop() \\ 363 \For{Node v in N(u)}{ 364 \If{v.layer = $-\infty$}{ 365 Q.push(v) \\ 366 v.layer = u.layer + 1 367 } 368 \If{v = z}{ 369 return z.layer 370 } 371 } 372 } 373 \end{algorithm} 374 \end{minipage} 375 \begin{minipage}{.25\linewidth} 376 \begin{algorithm}[H] 377 Dijkstra(Graph G, Node s) \\ 378 d := [$\infty$; n] \\ 379 d[s] := 0 \\ 380 PriorityQueue Q := empty priority queue \\ 381 \For{Node v in V}{ 382 Q.push(v, d[v]) 383 } 384 \While{Q $\neq \emptyset$}{ 385 u := Q.popMin() \\ 386 \For{Node v in N(u)}{ 387 \If{d[v] $>$ d[u] + len(u, v)}{ 388 d[v] := d[u] + len(u, v) \\ 389 Q.decPrio(v, d[v]) \\ 390 } 391 } 392 } 393 \end{algorithm} 394 \end{minipage} 395 \begin{minipage}{.25\linewidth} 396 \begin{algorithm}[H] 397 BellManFord(Graph G, Node s) \\ 398 d := [$\infty$, n] \\ 399 d[s] := 0 \\ 400 \For{n-1 iterations}{ 401 \For{(u, v) $\in$ E}{ 402 \If{d[v] $>$ d[u] + len(u, v)}{ 403 d[v] := d[u] + len(u, v) 404 } 405 } 406 } 407 \For{(u, v) $\in$ E}{ 408 \If{d[v] $>$ d[u] + len(u, v)}{ 409 return negative cycle 410 } 411 } 412 return d 413 \end{algorithm} 414 \end{minipage} 415 \begin{minipage}{.25\linewidth} 416 \begin{algorithm}[H] 417 FloydWarshall(Graph G) \\ 418 D := [$\infty$, n $\times$ n] \\ 419 \For{(u, v) $\in$ E}{D[u][v] := len(u, v)} 420 \For{v $\in$ V}{D[v][v] := 0} 421 \For{i $\in 1,...,n$}{ 422 \For{(u,v) $\in V \times V$}{ 423 D[u][v] := min(D[u][v], D[u][$v_i$] + D[$v_i$][v]) \\ 424 } 425 } 426 return D 427 \end{algorithm} 428 \end{minipage} 429 \end{document}