Heapsort Aufwand

Rob64

Bin auf der Suche nach dem Worst Case von Heepsort.
Leider stoße ich im Netz auf Unterschiedliche Informationen

O(log (n)) und O(n log(n))

Ich glaube O(log (n)) ist richtig

Wenn ich in eine Priority Queue mit einen Heap als Struktur mache dann sollte dabei
der Aufwand dann gleich dem Heap sein oder ? ?

Christoph R.

Theta(n log(n)) ist richtig. Das ist auch die Komplexität des Sortierproblems, der Algorithmus kann daher gar nicht schneller sein (und auch kein anderer).

Kampi

Zitat von Christoph R.

Theta(n log(n)) ist richtig. Das ist auch die Komplexität des Sortierproblems, der Algorithmus kann daher gar nicht schneller sein (und auch kein anderer).

dem stimme ich (bzw mein algodat-skript) zu. vielleicht zusaetzlich noch interessant:
C_max = C_avg = C_min = Theta (n log (n))
M_max = M_avg = M_min = Theta (n log (n))

Rob64

Danke!
Ich hab den Durchblick

Jetzt mitmachen!