Kurs:Algorithmen und Datenstrukturen/Vorlesung/Omega-Notation

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

$\Omega$ -Notation

Für eine Funktion $f:\mathbb {N} \to \mathbb {N}$ ist die Menge $\Omega (f(n))$ wie folgt definiert:

$\Omega (f(n))=\{g:\mathbb {N} \to \mathbb {N} |\exists c\in \mathbb {R} ^{>0},\exists n_{o}\in \mathbb {N} \ \forall n\geq n_{0}:g(n)\geq c\cdot f(n)\}$

Anschaulich formuliert bedeutet das, dass $\Omega (f(n))$ die Menge aller durch f nach unten beschränkter Funktionen ist und somit die asymptotische untere Schranke ist.