Ο συμβολισμός Ο δίνει άνω ένα άνω φραγμα για την πολυπλοκότητα του αλγορίθμου.
Γιατί στις ενότητες 5.3.1 και 5.3.2 εξετάζει καλύτερη, μέση και χειρότερη περίπτωση και όχι μόνο χειρότερη? Αυτές νομίζω είναι απαραίτητες για υπολογισμό Ω και Θ.
Κάνω κάπου λάθος?
Ευχαριστώ
Όσον αφορά το συμβολισμό big-O για την ακρίβεια εμείς ενδιαφερόμαστε όχι για ένα άνω φράγμα όπως πολύ σωστά λες αλλά για το ελάχιστο άνω φράγμα (supremum) του συνόλου αυτού.
Η απορια σου είναι λογική. Η δική μου ερμηνεία είναι ότι επειδή αναφέρονται διαφορετικοί αλγόριθμοι ταξινόμησης, αυτοί δεν μπορούν να συγκριθούν με βάση την πολυπλοκότητα στη χειρότερη περίπτωση, αφού όλοι είναι O(n
2), ακόμα και η Quicksort για την οποία πολλοί έχουν την εσφαλμένη εντύπωση ότι ειναι O(nlogn).
Η σύγκριση αυτή μπορεί να γίνει μόνο εξετάζοντας τι συμβαίνει στην μέση περίπτωση.
Από την άλλη σκοπός των συγγραφέων ίσως ήταν να δώσουν μια πλήρη εικόνα για την έννοια της πολυπλοκότητας.
Παράθεση από: soula στις 06 Μαρ 2016, 09:53:30 ΜΜ
Ο συμβολισμός Ο δίνει άνω ένα άνω φραγμα για την πολυπλοκότητα του αλγορίθμου.
Γιατί στις ενότητες 5.3.1 και 5.3.2 εξετάζει καλύτερη, μέση και χειρότερη περίπτωση και όχι μόνο χειρότερη? Αυτές νομίζω είναι απαραίτητες για υπολογισμό Ω και Θ.
Κάνω κάπου λάθος?
Ευχαριστώ
Συμφωνώ και με τις δύο εκδοχές που δίνεις.
Το μόνο πρόβλημα είναι το επίπεδο εμβάθυνσης στους μαθητές.
Ευχαριστώ πολύ για την απάντηση.