Algorithmen Und Datenstrukturen an der Universität Zu Lübeck | Karteikarten & Zusammenfassungen

Lernmaterialien für Algorithmen und Datenstrukturen an der Universität zu Lübeck

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Algorithmen und Datenstrukturen Kurs an der Universität zu Lübeck zu.

TESTE DEIN WISSEN
Laufzeitkomplexität Union-Find (union Operation & Find Operation
Lösung anzeigen
TESTE DEIN WISSEN
Union: O(1)
Find: O(log* n) armorisiert
Lösung ausblenden
TESTE DEIN WISSEN
Was sagt das Ω der O-Notation aus?
Lösung anzeigen
TESTE DEIN WISSEN
Untere asymptotische Schranke  (ab/garantiert nicht weniger/wird hier nicht drunter liegen)
Lösung ausblenden
TESTE DEIN WISSEN
Laufzeitkomplexität Binary-Heap für die Operationen (insert, min, deleteMin, delete, decreaseKey, merge)

Lösung anzeigen
TESTE DEIN WISSEN
insert: O(log n)
min: O(1)
deleteMin: O(log n)
delete: O(log n)
decreaseKey: O(log n)
merge: O(log n) - besser als Binomial-Heap


Lösung ausblenden
TESTE DEIN WISSEN
Laufzeitkomplexität AVL-Bäume
Lösung anzeigen
TESTE DEIN WISSEN
jede Operation O(log n), außer:
Rekonstruktion: O(1)
Lösung ausblenden
TESTE DEIN WISSEN
Pfadkompression
Lösung anzeigen
TESTE DEIN WISSEN
Pfad wird direkt an Wurzel gelegt
Lösung ausblenden
TESTE DEIN WISSEN
Splay Tree zig-Operation
Lösung anzeigen
TESTE DEIN WISSEN
x ist Kind der Wurzel
Lösung ausblenden
TESTE DEIN WISSEN
Splay Tree zig-zig-Operation
Lösung anzeigen
TESTE DEIN WISSEN
x hat Vater und Großvater rechts
oder
x hat Vater und Großvater links
Lösung ausblenden
TESTE DEIN WISSEN
Was sagt das Θ (Theta) der O-Notation aus?
Lösung anzeigen
TESTE DEIN WISSEN
obere& untere asymptotische Schranke (Gleiches Wachstum/)
Lösung ausblenden
TESTE DEIN WISSEN
Was ist eine amortisierte Analyse im Zsmh. mit Algorithmen? 
Lösung anzeigen
TESTE DEIN WISSEN
amortisierte Analyse, d.h. durchschnittliche Kosten aller Operationen der Sequenz im worst-case Fall (teuerste Folge)
Lösung ausblenden
TESTE DEIN WISSEN
Warum können amortisierte Analysen sinnvoll sein? 
Lösung anzeigen
TESTE DEIN WISSEN
Nur in O-Notation  worst case Laufzeit anzugebenbirgt die Gefahr den Algorithmus nicht richtig zu Repräsentieren, wenn dieser z.B. nur sehr selten diese Worst-Case  Laufzeit trifft. 
Lösung ausblenden
TESTE DEIN WISSEN
log*
Lösung anzeigen
TESTE DEIN WISSEN
anzahl an Anwendungen um zur letzten Wurzel zu gelangen
Lösung ausblenden
TESTE DEIN WISSEN
Union-Find 
Lösung anzeigen
TESTE DEIN WISSEN
jede Teilmenge T wird als gerichteter Baum, mit dem Repräsentanten als Wurzel, repräsentiert
Lösung ausblenden
  • 62065 Karteikarten
  • 579 Studierende
  • 24 Lernmaterialien

Beispielhafte Karteikarten für deinen Algorithmen und Datenstrukturen Kurs an der Universität zu Lübeck - von Kommilitonen auf StudySmarter erstellt!

Q:
Laufzeitkomplexität Union-Find (union Operation & Find Operation
A:
Union: O(1)
Find: O(log* n) armorisiert
Q:
Was sagt das Ω der O-Notation aus?
A:
Untere asymptotische Schranke  (ab/garantiert nicht weniger/wird hier nicht drunter liegen)
Q:
Laufzeitkomplexität Binary-Heap für die Operationen (insert, min, deleteMin, delete, decreaseKey, merge)

A:
insert: O(log n)
min: O(1)
deleteMin: O(log n)
delete: O(log n)
decreaseKey: O(log n)
merge: O(log n) - besser als Binomial-Heap


Q:
Laufzeitkomplexität AVL-Bäume
A:
jede Operation O(log n), außer:
Rekonstruktion: O(1)
Q:
Pfadkompression
A:
Pfad wird direkt an Wurzel gelegt
Mehr Karteikarten anzeigen
Q:
Splay Tree zig-Operation
A:
x ist Kind der Wurzel
Q:
Splay Tree zig-zig-Operation
A:
x hat Vater und Großvater rechts
oder
x hat Vater und Großvater links
Q:
Was sagt das Θ (Theta) der O-Notation aus?
A:
obere& untere asymptotische Schranke (Gleiches Wachstum/)
Q:
Was ist eine amortisierte Analyse im Zsmh. mit Algorithmen? 
A:
amortisierte Analyse, d.h. durchschnittliche Kosten aller Operationen der Sequenz im worst-case Fall (teuerste Folge)
Q:
Warum können amortisierte Analysen sinnvoll sein? 
A:
Nur in O-Notation  worst case Laufzeit anzugebenbirgt die Gefahr den Algorithmus nicht richtig zu Repräsentieren, wenn dieser z.B. nur sehr selten diese Worst-Case  Laufzeit trifft. 
Q:
log*
A:
anzahl an Anwendungen um zur letzten Wurzel zu gelangen
Q:
Union-Find 
A:
jede Teilmenge T wird als gerichteter Baum, mit dem Repräsentanten als Wurzel, repräsentiert
Algorithmen und Datenstrukturen

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang Algorithmen und Datenstrukturen an der Universität zu Lübeck

Für deinen Studiengang Algorithmen und Datenstrukturen an der Universität zu Lübeck gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!

Das sind die beliebtesten Algorithmen und Datenstrukturen Kurse im gesamten StudySmarter Universum

Algorithmen & Datenstrukturen

Hochschule Niederrhein

Zum Kurs
Algorithmen & Datenstrukturen

Hochschule Kempten

Zum Kurs
Datenstrukturen und Algorithmen

Fachhochschule Campus 02 Graz

Zum Kurs
Algorithmen & Datenstrukturen

Duale Hochschule Baden-Württemberg

Zum Kurs
Datenstrukturen und Algorithmen

RWTH Aachen

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Algorithmen und Datenstrukturen
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Algorithmen und Datenstrukturen