Laufzeit des Prim Algorithmus

[Mariexshhx]

Hallo, in diesem Fall wird ein Min Heap für den Alogorthmus genutzt. er benötigt für Initialisierung und Erzeugung des Heaps eine Laufzeit von O(V). Dann wird höchstens O(V) mal extract-min() aufgerufen. Wenn im schlimmsten Fall jede Kanre angeguckt wird muss decrease-key() O(E) aufgerufen werden.Extract-min() und decrease-key() haben beide eine Worst-Case-Laufzeit von O(log(V)). Jetzt ergibt sich eine Gesamtlaufzeit von O((|V | + |E|) log |V |).meine Frage ist wieso wird die O(V) für Erzeugung des heaps nicht miteinbezogen bei der Gesamtlaufzeit?

 

[mihe7]

meine Frage ist wieso wird die O(V) für Erzeugung des heaps nicht miteinbezogen bei der Gesamtlaufzeit?

Die ist doch einbezogen worden.

 

[Mariexshhx]

Die ist doch einbezogen worden.

fällt es raus, weil es nicht das max ist ? Wenn ich zum Beispiel O(E) und O(V*log(V)) habe und E>V ist die Gesamtlaufzeit dann O(E) oder O(E+V*logV) ?

 

[mihe7]

Da muss man ein bisschen aufpassen. Was |V| alleine betrifft: ja. |V| <= |V|*log(|V|), also gilt gesamt O(|V|*log(|V|). In Deinem Beispiel geht es um eine bessere Abschätzung der Laufzeitkomplexität, die von Knoten und Kanten in unterschiedlichem Maße abhängt (in der Regel hat man so etwas bei ausgabesensitiven Algorithmen, d. h. die Laufzeitkomplexität hängt entscheidend von der Zahl der Elemente in der Ausgabe ab). Da macht es natürlich keinen Sinn, die Kanten oder Knoten unter den Tisch fallen zu lassen.

Bei einem allgemeinen Sortieralgorithmus wäre ja O(n log(n)) optimal. Das n bezieht sich hier auf die Zahl der Elemente, die Ausgabe hat auch n Elemente -> alles gut. Beim Suchen des Maximums hätte man dagegen O(n + 1), weil man alle Elemente betrachtet und eines ausgibt. Die 1 ist aber konstant, also fällt die unter den Tisch: O(n), der Algorithmus ist nicht ausgabesensitiv.

Wenn dagegen ein Algorithmus eine vorab nicht bekannte Zahl an Elementen ausgibt und dafür eine Datenstruktur verwenden muss (z. B. ein Baum), dann ist der Algorithmus ausgabesensitiv und man interessiert sich für die Laufzeitkomplexität.