Zusammenfassung
Zusammenfassung Lernzettel_Algodat_SoSe23
Zusammenfassung und Lernzettel
[ Mehr anzeigen ]vorschau 3 aus 27 Seiten
Vorschau 3 aus 27 Seiten
In den EinkaufswagenVerkäufer
Folgen
Inhaltsvorschau
Algorithmen und Datenstrukturen und ihre LaufzeitenNotationen
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
Alle Vorteile der Zusammenfassungen von Stuvia auf einen Blick:
Garantiert gute Qualität durch Reviews
Stuvia Verkäufer haben mehr als 700.000 Zusammenfassungen beurteilt. Deshalb weißt du dass du das beste Dokument kaufst.
Schnell und einfach kaufen
Man bezahlt schnell und einfach mit iDeal, Kreditkarte oder Stuvia-Kredit für die Zusammenfassungen. Man braucht keine Mitgliedschaft.
Konzentration auf den Kern der Sache
Deine Mitstudenten schreiben die Zusammenfassungen. Deshalb enthalten die Zusammenfassungen immer aktuelle, zuverlässige und up-to-date Informationen. Damit kommst du schnell zum Kern der Sache.
Häufig gestellte Fragen
Was bekomme ich, wenn ich dieses Dokument kaufe?
Du erhältst eine PDF-Datei, die sofort nach dem Kauf verfügbar ist. Das gekaufte Dokument ist jederzeit, überall und unbegrenzt über dein Profil zugänglich.
Zufriedenheitsgarantie: Wie funktioniert das?
Unsere Zufriedenheitsgarantie sorgt dafür, dass du immer eine Lernunterlage findest, die zu dir passt. Du füllst ein Formular aus und unser Kundendienstteam kümmert sich um den Rest.
Wem kaufe ich diese Zusammenfassung ab?
Stuvia ist ein Marktplatz, du kaufst dieses Dokument also nicht von uns, sondern vom Verkäufer nicomann. Stuvia erleichtert die Zahlung an den Verkäufer.
Werde ich an ein Abonnement gebunden sein?
Nein, du kaufst diese Zusammenfassung nur für 8,19 €. Du bist nach deinem Kauf an nichts gebunden.
Kann man Stuvia trauen?
4.6 Sterne auf Google & Trustpilot (+1000 reviews)
45.681 Zusammenfassungen wurden in den letzten 30 Tagen verkauft
Gegründet 2010, seit 14 Jahren die erste Adresse für Zusammenfassungen