Wachstum von Funktionen - Elementare Datenstrukturen Flashcards
Asymptotische Notation, Stapen/Warteschlangen, Verkettete Listen, Graphen representation
Wie beschreibt man die Laufzeit von Algorithmen?
Verhalten im Grenzwert
O == ≤ (big oh) Obere asymptotische Schranke
Ω == ≥ (Ohm) untere asymptotische Schranke
θ == = (Theta) enge Grenze
o == < (klein o)
ω == > (klein Ohm)
== ist wie, oder ähnlich zu
Die Symbole werden Landau Symbole genannt
Landau Symbole / Notationen
Definition der O- Notation (Big oh)
Die Big-O-Notation, auch bekannt als asymptotische obere Schranke, wird verwendet, um das Wachstumsverhalten einer Funktion zu beschreiben. Eine Funktion f(n) gehört zu O(g(n)), wenn es positive Konstanten c und n_0 gibt, so dass |f(n)|≤c⋅|g(n)| für alle n≥n_0.
Landau Symbole / Notationen
Definition der Ω- Notation (Ohmega)
Die Omega-Notation, auch bekannt als asymptotische untere Schranke, wird verwendet, um das untere Wachstumsverhalten einer Funktion zu beschreiben. Eine Funktion f(n)f(n) gehört zu Ω(g(n))Ω(g(n)), wenn es positive Konstanten c und n_0 gibt, so dass |f(n)|≥c⋅|g(n)| für alle n≥n_0.
Landau Symbole / Notationen
Definition der Θ-Notation (Theta)
Die Theta-Notation wird verwendet, um ein enges Wachstumsverhalten zwischen Funktionen zu beschreiben. Eine Funktion f(n) gehört zu Θ(g(n)), wenn sie sowohl zu O(g(n)) als auch zu Ω(g(n)) gehört, was bedeutet, dass es positive Konstanten c_1, c_2 und n_0 gibt, so dass c_1|g(n)|≤|f(n)|≤C2⋅|g(n)| für alle n≥n_0.
Landau Symbole / Notationen
Mach folgendes Sinn?
f(n) ist mindestens O(n²)
Nein, da die O-Notation die obere Grenze beschreibt.
Stapel
Stapel DELETE
Entfernt das zuletzt hinzugefügte Elementlast in, first out (LIFO)
Warteschlange
Warteschlange DELETE
Entfernt das am längsten in der Menge befindliche Elementfirst in, first out (FIFO)
Warteschlange
Laufzeiten Stapel
Laufzeit: O(1)
~~~
INSERT == PUSH
DELETE == POP
STACK-EMPTY
~~~
veranschaulichung durch Tellerstapel:
unterster Teller == zuerst hinzugefügt, aber zuletzt entnehmbar
== ist gleich
Warteschlange
Laufzeiten Warteschlange
Laufzeit: O(1)
~~~
INSERT == ENQUEUE
DELETE == DEQUEUE
~~~
veranschaulichung durch Schlange von Bankkunden vor Bankschalter. Schlange hat Kopf und Ende.
- Neues Element kommt ans Ende
- Element am Kopf wird als nächstes entfernt
== ist gleich
verkettete Listen
Unterschied zwischen einfach und doppelt verkettete Listen?
Einfach verkettete Listen haben nur einen zeiger auf das nächste Element. Wenn es das letzte Element ist, zeigt dieser auf NIL.
Doppelt verkettete Listen haben zusätzlich einen zeiger auf das vorherige Element. Das erste Element in dieser Liste zeigt dann auf NIL als vorheriges Element.
NIL = Not In List (Nicht in Liste)
verkettete Listen
Was ist eine Zyklisch verkettete Liste?
Wenn das letzte Element auf das erste Element der Liste zeigt. Somit zeigt kein Element auf NIL.
NIL = Not In List (Nicht in Liste)
verkettete Listen
Was ist ein Wächter (Sentinal) in verketteten Listen?
Ein Wächter ist ein Element, dass in doppelt verketteten Listen vorkommt und auf das nächste Element zeigt, wobei das letzte Element der Liste auf diesen Wächter zeigt.
Zum Beispiel Rundkurs Autorennen. Die Startlinie zeigt gleichzeitig die Ziellinie an.
Graphen
Was ist der Unterschied zwischen gerichteten und ungerichteten Graphen?
Ungerichtete Graphen sind Verticies die über Edges verbunden sind. Dabei spielt die Richtung keine Rolle. Bei gerichteten Graphen haben die Kanten eine Richtung. Dann wird durch doppelnennung der Kanten klarer ob diese in beide Richtungen geht.
V = Verticies (Knoten)
E = Edges (Kanten)
Graphen
Was ist ein dünn besetzter Graph?
Wenn|E| < |V|²
ist
Dann benutzt man Adjazenzlisten.
|x| = Betrag von x
V = Verticies (Knoten)
E = Edges (Ecken, bzw Kanten)
Graphen
Was ist ein dicht besetzter Graph?
Wenn|E| ≈ |V|²
ist.
Dann benutzt man Adjazenzmatritzen.
≈ = ungefär
|x| = Betrag von x
V = Verticies (Knoten)
E = Edges (Kanten)
