worst case for heapsort

[voulaji]

ξερει κανείς που μπορω να βρω την αποδειξη για τη χειροτερη περιπτωση του χρόνου εκτέλεσης του heapsort =Ω(nlgn)?

[agmarios]

Μια πολύ καλή ανάλυση της heapsort (και ο κώδικας ) βρίσκεται εδώ

 

Η απόδειξη είναι απλή:

Η heapsort εκτελεί τα παρακάτω:

Ν εισαγωγές σε μια heap

Η εισαγωγή στη heap χρειάζεται lg(k)

άρα συνολικά χρειάζεσαι:

lg(1) + lg(2) + ... + lg(n-1) + lg(n) = nlg(n)

 

Ν εξαγωγές - διαγραφές από τη heap

H διαγραφή από τη heap (του μέγιστου ή του ελάχιστου) χρειάζεται σταθερό χρόνο άρα:

1 + 1 + ... + 1 = n

 

άρασυνολικά χρειάζεσαι Θ(nlog(n)) + Θ(n) = Θ(nlog(n))

 

ελπίζω να βοήθησα