Αλγόριθμοι Ταξινόμησης και Είσοδος Χειρότερης Περίπτωσης

[kio89]

Χαιρετώ την παρέα του insomnia!

Έγω υλοποιήσει σε Java,τους αλγόριθμους ταξινόμησης :Mergesort, Heapsort και Counting Sort και πρέπει να κατασκευάσω πίνακες που θα αποτελούν είσοδο χειρότερης περίπτωσης για κάθε ένα από αυτούς τους αλγόριθμους.

Η ερώτηση είναι: αρκεί να φτιάξω πίνακες στους οποίους τα στοιχεία θα είναι ανάποδα διατεταγμένα ( σε φθίνουσα σειρά) ή κάθενας από αυτούς τους αλγόριθμους έχει την δικιά του είσοδο χειρότερης περίπτωσης;

Ευχαριστώ!

[ΠάρηςΓ]

Νομίζω οτι διαφέρει.Δε μπορω να σου απαντησω με βεβαιοτητα αλλα απο οσο ξερω υπάρχουν και αλγόριθμοι που ειναι πιο αργοί απο αλλους εαν ειναι ταξινομημενα τα στοιχεία!

[Blondeamon]

Κάθε αλγόριθμος έχει την δικια του χειρότερη είσοδο, που του αυξάνει την πολυπλοκότητα.

 

πχ η quicksort εχει χειρότερη περιπτωση O(n^2) ενω κανονικά έχει O(nlogn) και το ίδιο και για τις άλλες.

 

Διαβασε καλα αυτες τις σημειωσεις και θα τα βρεις ολα:

 

http://rapidshare.de/files/47508383/sorting.pdf.html

[kio89]

Κάθε αλγόριθμος έχει την δικια του χειρότερη είσοδο, που του αυξάνει την πολυπλοκότητα.

 

πχ η quicksort εχει χειρότερη περιπτωση O(n^2) ενω κανονικά έχει O(nlogn) και το ίδιο και για τις άλλες.

 

Διαβασε καλα αυτες τις σημειωσεις και θα τα βρεις ολα:

 

http://rapidshare.de/files/47508383/sorting.pdf.html

 

Ευχαριστώ για τη βοήθεια.

Γνωρίζω ότι κάθε αλγόριθμος έχει την δική του πολυπλοκότητα χειρότερης περίπτωσης.

Αυτό που ψάχνω είναι τι είσοδος πρέπει να δωθεί σε κάθε αλγόριθμο,ώστε αυτός να εμφανίσει χρόνο χειρότερης περίπτωσης.

[ΠάρηςΓ]

Βασικα αν καταλαβεις τον αλγοριθμο ποτε συμβαινει η χειροτερη περίπτωση τοτε θα μπορεσεις να βρεις και τη χειροτερη εισοδο