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
-
Flashcards
\(\log(n)\in\boxed{\Omega,\mathcal{o},\Theta}(\log(\sqrt{n})\)
\(\log(n!)\in\boxed{\Omega,\mathcal{o},\Theta}(\sqrt{n}+n \log_{10} (n))\)
\(n^{\log(n)}\in\boxed{\Omega,\mathcal{o},\Theta}(\frac{1}{1000}n^2)\)
\(\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)\)
