Beschreibe Kruskal (Mit Laufzeit)- für welche Art für Graphen ist es am besten geeignet und wie sind diese Definiert?
Eeeesy kleinste Kante und Town. Laufzeit ist O(m log n) und er ist am besten für dünne Graphen die mit Theta(n) definiert sind
Beschreibe Prim (Mit Laufzeit)- für welche Art für Graphen ist es am besten geeignet und wie sind diese Definiert?
Laufzeit mir klassichen Heap O(m log n), verbesserung durch FibHeap Fibanacci O(m + n log n). Für dichte Graphen die m = n^2
Was ist die Rekursionsgleichung für Mergesort?
Laufzeiten Isertionsort
Lauzeiten Selectionsort
Mergesort Laufzeiten
Quicksort Laufzeiten
Countsort Laufzeiten
Theta (n+k)
Wost case Theta(n)
Wie viel Vertauschungen hat Selectionsort
O(n)
Wie viel Vertauschungen braucht Insertionsort?
O(n^2)
Beschreibe das Kantenschnittlemma?
Beschreibe das Kreislemma
Beschreibe das Handshaking Lemma
Gebe mir die Gegenbeweise für Greedy Interval Scheduling - und die Laufzeit..
Ein zusammenhängender ungerichter Graph …
der keinen Kreis enthält, hat n-1 Kanten
Was ist wichtig bei der Definition von Zusammenhangskomponenten?
Was ist ein Zusammenhang?
Zusammenhängender Graph heißt das alle v auch ein Kante zueinander haben.
Frage: Hat jeder DAG eine topologische Sortierung? Was ist die LAuzeit und die Initialisierung
Ja, Laufzeit ist O(n+m) und auch die Initialisierung ist das
Was sind die Laufzeiten für einen Dijksta-Algo?
Laufzeit Kruskal
O(m log n)
Prim Laufzeit als Array, Heap und als Fibheap
Prim Laufzeit ist als Liste O(n^2), als Heap O(m log n) mit einem FibHeap O(m + n log n)
Last changed4 months ago
