Zusammenfassung Lernzettel_Algodat_SoSe23

Algorithmen und Datenstrukturen und ihre Laufzeiten
Notationen
Notation Bedeutung
o(g(n)) f (n) wächst langsamer als g(n)
O(g(n)) f (n) wächst höchstens genauso schnell wie g(n)
Θ(g(n)) f (n) wächst genauso schnell wie g(n)
ω(g(n)) (Zahlentheorie) f (n) wächst nicht immer langsamer als g(n)
Ω(g(n)) (Komplexitätstheorie) f (n) wächst mindestens genauso schnell wie g(n)
ω(g(n)) f (n) wächst schneller als g(n)


1 Suchalgorithmen
1.1 Binäre Suchbäume (BST)
Ein binärer Suchbaum ist eine Datenstruktur, die schnelles Suchen, Einfügen
und Löschen von Elementen ermöglicht. Jeder Knoten hat höchstens zwei
Kinder, die als linker Knoten und rechter Knoten bezeichnet werden.

Operation Worst-Case Best-Case Durchschnitt
Suchen O(n) Ω(log n) Θ(log n)
Einfügen (add()) O(n) Ω(log n) Θ(log n)
Entfernen (re- O(n) Ω(log n) Θ(log n)
move())

1.2 AVL-Bäume
AVL-Bäume sind selbstbalancierende binäre Suchbäume. Bei jeder Änderung im
Baum wird die Balance überprüft und gegebenenfalls durch Rotationen wieder-
hergestellt.

Operation Worst-Case Best-Case Durchschnitt
Suchen O(log n) Ω(log n) Θ(log n)
Einfügen (add()) O(log n) Ω(log n) Θ(log n)
Entfernen (re- O(log n) Ω(log n) Θ(log n)
move())




1

,1.3 Rot-Schwarz-Bäume
Rot-Schwarz-Bäume sind eine Art von selbstbalancierenden binären Suchbäumen.
Jeder Knoten speichert einen zusätzlichen Bit für die Farbe, der zur Aufrechter-
haltung des Balances im Baum verwendet wird.

Operation Worst-Case Best-Case Durchschnitt
Suchen O(log n) Ω(log n) Θ(log n)
Einfügen (add()) O(log n) Ω(log n) Θ(log n)
Entfernen (re- O(log n) Ω(log n) Θ(log n)
move())

1.4 B-Bäume
B-Bäume sind eine Verallgemeinerung der binären Suchbäume, die für die Spe-
icherung auf externen Medien optimiert sind. Sie können mehr als zwei Kinder
haben.

Operation Worst-Case Best-Case Durchschnitt
Suchen O(log n) Ω(log n) Θ(log n)
Einfügen (add()) O(log n) Ω(log n) Θ(log n)
Entfernen (re- O(log n) Ω(log n) Θ(log n)
move())

1.5 Hashing
Hashing ist eine Technik, die direkten Zugriff auf die Daten ermöglicht. Sie
verwendet eine Hash-Funktion, um die Indexposition für die Speicherung von
Daten zu berechnen.

Operation Worst-Case Best-Case Durchschnitt
Suchen O(n) Ω(1) Θ(1)
Einfügen (add()) O(n) Ω(1) Θ(1)
Entfernen (re- O(n) Ω(1) Θ(1)
move())




2

, 1.6 Heaps
Ein Heap ist eine spezielle Baumstruktur, in der jeder Elternknoten kleiner
oder gleich seinen Kindknoten ist. Es wird hauptsächlich verwendet, um eine
Prioritätswarteschlange zu implementieren.

Operation Worst-Case Best-Case Durchschnitt
Suchen O(n) Ω(1) Θ(log n)
Einfügen (add()) O(log n) Ω(1) Θ(log n)
Entfernen (re- O(log n) Ω(1) Θ(log n)
move())


2 Graphalgorithmen
2.1 Dijkstra’s Algorithmus
Dijkstra’s Algorithmus ist ein Algorithmus für die Suche nach dem kürzesten
Pfad in einem Graphen mit nichtnegativen Kantengewichten.

Worst-Case Best-Case Durchschnitt
O((V + E) log V ) Ω((V + E) log V ) Θ((V + E) log V )

2.2 Bellman-Ford Algorithmus
Der Bellman-Ford Algorithmus berechnet den kürzesten Pfad in einem Graphen.
Im Gegensatz zu Dijkstra’s Algorithmus funktioniert er auch mit negativen Kan-
tengewichten, solange keine negativen Zyklen vorhanden sind.

Worst-Case Best-Case Durchschnitt
O(V E) Ω(V E) Θ(V E)

2.3 Floyd-Warshall Algorithmus
Der Floyd-Warshall Algorithmus ist ein Algorithmus zur Lösung des Problems
des kürzesten Pfades für alle Paare von Knoten in einem gewichteten Graphen.

Worst-Case Best-Case Durchschnitt
O(V 3 ) Ω(V 3 ) Θ(V 3 )

2.4 Prim’s Algorithmus
Prim’s Algorithmus ist ein Algorithmus zur Berechnung des minimalen Spannbaums
für einen zusammenhängenden gewichteten Graphen.

Worst-Case Best-Case Durchschnitt
O(V 2 ) Ω(V 2 ) Θ(V 2 )

3