Algorithmik
MC
MC
\(\log(n!)\in\boxed{\Omega,\mathcal{o},\Theta}(\log^2(n))\)
\(\log^6(n)\in\boxed{\Omega,\mathcal{o},\Theta}(\log^3(n))\)
\(\log(n)\in\boxed{\Omega,\mathcal{o},\Theta}(\sqrt{n})\)
\(e^3\in\boxed{\Omega,\mathcal{o},\Theta}(n^6)\)
Laufzeit in O-Notation bestimmen:
\(\Theta(1)\)
Laufzeit in O-Notation bestimmen:
\(\Theta(n)\)
Laufzeit in O-Notation bestimmen:
\(\Theta(n^2)\)
Laufzeit in O-Notation bestimmen:
\(\Theta(n \log(n))\)
Laufzeit in O-Notation bestimmen:
\(\Theta(n)\)
Laufzeit in O-Notation bestimmen:
\(\Theta(n)\)
Laufzeit in O-Notation bestimmen:
\(\Theta(3^n)\)
Laufzeit in O-Notation bestimmen:
\(\Theta(n)\)
Laufzeit in O-Notation bestimmen:
\(\Theta(n)\)
Laufzeit in O-Notation bestimmen:
\(\Theta(\log(n))\)
Laufzeit in O-Notation bestimmen:
\(\Theta(n)\)
Laufzeit in O-Notation bestimmen:
\(\Theta(n)\)
Laufzeit in O-Notation bestimmen:
\(\Theta(n\log(n))\)
Laufzeit in O-Notation bestimmen:
\(\Theta(\log(n))\)
??
Laufzeit in O-Notation bestimmen:
\(\Theta(n)\)
Laufzeit in O-Notation bestimmen:
\(\Theta(n)\) da \(\Theta(\sqrt{n})\cdot \Theta(\sqrt{n})=\Theta(\sqrt{n}\cdot\sqrt{n})=\Theta(n)\)
Dijkstras Algorithmus folgt dem Entwurfsprinzip "Divide and Conquer".
Ein Fibonacci-Heap mit n Knoten hat maximale Höhe \(\mathcal{O}(log(n))\).
Optimale Suchbäume lassen sich in quadratischer Zeit berechnen.
Der Median einer Menge ganzer Zahlen kann gleich ihrem Maximum sein.
Bubblesort benötigt auf allen Eingaben mehr Vergleiche als Heapsort.
Der Algorithmus von Schönhagen und Strassen zur schnellen Multiplikation ganzer Zahlen verwendet die schnelle Fouriertransformation.
Quickselect benötigt im Mittel mehr als 15n Vergleiche
Verwendet man Fibonacci-Heaps zur Implementierung von Heapsort, so erreicht man eine Worst-Case Laufzeit von \(\mathcal{O}(n (log (log (n))))\)
Es gibt einen Algorithmische mit Worst-Case-Laufzeit in \(\mathcal{o}(n^3)\) zur Berechnung des Produkts zweier Boolescher \(n\times n\) Matrizen
Es ist kein Algorithmus zur Multiplikation zweier n-Bit Zahlen bekannt, der Laufzeit \(\mathcal{o}(n^2)\) hat.
Sei \(k \in \mathbb{N}\) fest. Jeder Algorithmus der in einem Feld mit n Elementen das k-kleinste Element bestimmt, benötigt im Worst-Case \(\Omega(n \ log(n))\) Vergleiche.
Die mittlere Laufzeit von Bubblesort liegt in \(\Theta(n^2)\).
Quickselect benötigt im Worst-Case nicht mehr als 4n Vergleiche um den Median eines Feldes von n Elementen zu finden.
Quicksort mit Median-aus-3 benötigt im Mittel nicht mehr als 3n Vergleiche um ein Feld von n Elementen zu sortieren.
Mergesort benötigt im Worst-Case \(\Theta(n^2)\) Vergleiche um ein Feld von n Elementen zu sortieren.
Durch Verwendung von Fibonacci-Heaps hat Prims Algorithmus eine Laufzeit von \(\mathcal{O}(m + n \ log(n))\) um den minimalen Spannbaum eines Graphen mit m Kanten und n Knoten zu berechnen.
Jede Insert Operation in ein Fibonacci Heap kann im Worst-Case in \(\mathcal{O}(1)\) Schritten durchgeführt werden.
Sei L eine kontext-freie Sprache. Das Wortproblem (gegeben ein Wort w, entscheide ob w in L) für L kann mit Hilfe des CYK-Algorithmus in kubischer Zeit entschieden werden.
Die Ausgabe des Algorithmus von Karger und Stein ist immer ein korrekter minimaler Schnitt
Der Algorithmus von Stoer und Wagner hat eine Laufzeit von \(\mathcal{O}(n\ log(n))\) auf einem Graphen mit n Knoten.
-
- 1 / 103
-
Cartes-fiches
Wie viele Vergleiche benötigt ein Sortieralgorithmus, der ausschließlich auf Schlüsselvergleiche basiert? (im Mittel und im schlechtesten Fall)
\(\Theta(n \log(n))\)
Welche Größe müssen Hashtabellen haben, damit nicht mit Kollisionen zu rechnen sind?
Quadratische
Welche Laufzeitkomplexität hat der Huffman-Code unter Verwendung von Heap?
\(O({n \log(n)})\)
Wie teuer ist das Einsinken beim Heapaufbau?
maximal 2* (Höhe des Teilbaums unter a[i]) Vergleiche
Mit wie vielen Vergleichen ist der Heapaufbau möglich?
In linearer Zeit mit 2(n+1) Vergleichen
Wie viele Vergleiche benötigt der Standard-Heapsort?
\(2n \log (n)+\mathcal{O}(n)\). Der Aufbau benötigt \(\mathcal{O}(n)\) und der Abbau durch Einsinken \(2n \log(n)\) Vergleiche.
Wie groß ist der Aufwand bei Dijkstra unter Verwendung eines Fibonacci-Heaps
\(\mathcal{O}(e+n\log n)\)
Wie ist der Aufwand beim Bellman-Ford-Algorithmus? Was berechnet dieser?
\(\Theta(|V|\cdot|E|)\). Es berechnet die kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen.
Welche Zeit benötigt der Algorithmus von Schönhagen-Strassen für die schnelle Multplikation zweier Binärzahlen?
\(\mathcal{O}(n\log n \log \log n)\)
Wie schnell ist der Strassen-Algorithmus für die Multiplikation zweier Matrizen?
Subkubisch
Wie schnell lässt sich das Wortproblem kontext-freier Sprachen lösen?
In \(\mathcal{O}(n^3)\) mit CYK und in subkubisch mit Reduktion auf boolescher Matrizen.
Wie schnell lassen sich optimale Suchbäume berechnen?
Mit dem Algorithmus von Knuth in \(\Theta(n^2)\)
Wie viele Elemente hat ein Teilbaum mit der Wurzel x, wenn Rang(x)=r ist?
\(2^r\) Elemente
Wie viele Knoten mit Rang r gibt es höchstens?
\(n/2^r\)
Welche amortisierten Zeiten gelten für einen Fibonacci-Heap? (merge, insert, delete_min, decrease_key)
- \(\text{t}_\text{amort}\text{(merge)}\in\mathcal{O}(1)\)
- \(\text{t}_\text{amort}\text{(insert)}\in\mathcal{O}(1)\)
- \(\text{t}_\text{amort}\text{(delete_min)}\in\mathcal{O}(\log(n))\)
- \(\text{t}_\text{amort}\text{(decrease_key)}\in\mathcal{O}(1)\)
Wie ist die Laufzeit des Stoer-Wagner Algorithmus unter Verwendung eines Heaps? Wie mit Fibonacci-Heaps?
\(\mathcal{O}(e \log(n))\) mit Heaps und \(\mathcal{O}(e + n\log(n))\) mit Fibonacci-Heaps
Bei Heapsort werden immer mehr als die Hälfte der Vergleiche während des Heapaufbaus ausgeführt.
Werden Fibonacci-Heaps verwendet, so hat der Dijkstra Algorithmus eine Worst-Case-Laufzeit von \(\mathcal{O}(e+n \log n)\), wobei e die Anzahl der Kanten und n die Anzahl der Knoten ist
Quickselect hat eine Worst-Case-Laufzeit von \(\Omega(n^2)\)
Der in der Vorlesung behandelte Algorithmus von Karger und Stein zur Berechnung eines minimalen Schnitts liefert immer ein korrektes Ergebnis.
Dijkstras Algorithmus folgt dem Entwurfsprinzip "Backtracking"
Für alle n ist es möglich einen Fibonacci-Heap mit n Knoten und Höhe n-1 zu erzeugen.
Bei Union-Find mit Pfadverkürzung benötigt eine Find-Operation maximal \(\mathcal{O}(\alpha(n))\) Zeit, wobei \(\alpha\) die inverse Ackermannfunktion ist und n die Zahl der Elemente in der Datenstruktur.
Es ist kein subkubischer Algorithmus zur Berechnung optimaler Suchbäume bekannt.
Ultimatives Heapsort benötigt maximal \(\mathcal{O}(n \log \log (n))\) Vergleiche, um ein gegebenes Feld der Länge n zu sortieren.
Der KMP-Algorithmus testet endliche Automaten auf Äquivalenz.
Beim Huffman-Code wird der häufigste Buchstabe stets durch den längsten String codiert.
Das Traveling Salesman Problem kann bis au feinen Faktor 1,5 in Polynomialzeit approxmiert werden.
Jeder vergleichsbasierte Algorithmus um ein Feld mit n Elementen zu sortieren, benötigt im Worst Case \(\Omega(n \log (n))\) Vergleiche.
Das Rucksackproblem kann nicht besser als auf einen Faktor 2 in Polynomialzeit approxmiert werden.
Jede Insert-Operation in einen Fibonacci-Heap kann im Worst-Case in \(\mathcal{O}(1)\) Schritten durchgeführt werden.
Bei der Merge Operation auf Fibonacci-Heaps wird stets die kleinere Liste unter die größere gehängt.
Hat ein Graph zwei Kanten mit demselben Gewicht, dann kann der minimale Spannbaum nicht eindeutig sien.
\(4^n\in\boxed{\Omega,\mathcal{o},\Theta?}(2^n)\)
\(n \log(n!)\in\boxed{\Omega,\mathcal{o},\Theta?}(\sqrt{n^5})\)
\(2^{\sqrt(n)}\in\boxed{\Omega,\mathcal{o},\Theta}(n^{\log(n)})\)
\(n^n\in\boxed{\Omega,\mathcal{o},\Theta}(n^2\cdot n!)\)
\(\log(n)\in\boxed{\Omega,\mathcal{o},\Theta}(\log(\log(n)))\)
\(n^4\in\boxed{\Omega,\mathcal{o},\Theta}((1+\sqrt{n})^n)\)
\(7^n \in\boxed{\Omega,\mathcal{o},\Theta}(n\cdot 3^n)\)
