Αποστολέας Θέμα: Συμβολισμός Ο  (Αναγνώστηκε 1424 φορές)

soula

  • Νέος
  • *
  • Μηνύματα: 2
Συμβολισμός Ο
« στις: 06 Μάρ 2016, 09:53:30 μμ »
Ο συμβολισμός Ο δίνει άνω ένα άνω φραγμα για την πολυπλοκότητα του αλγορίθμου.
Γιατί στις ενότητες 5.3.1 και 5.3.2 εξετάζει καλύτερη, μέση και χειρότερη περίπτωση και όχι μόνο χειρότερη? Αυτές νομίζω είναι απαραίτητες για υπολογισμό Ω και Θ.
Κάνω κάπου λάθος?
Ευχαριστώ

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3517
  • to Iterate is human to Recurse divine
Απ: Συμβολισμός Ο
« Απάντηση #1 στις: 07 Μάρ 2016, 12:22:19 πμ »
Όσον αφορά το συμβολισμό big-O για την ακρίβεια εμείς ενδιαφερόμαστε όχι για ένα άνω φράγμα όπως πολύ σωστά λες αλλά για το ελάχιστο άνω φράγμα (supremum) του συνόλου αυτού.
Η απορια σου είναι λογική. Η δική μου ερμηνεία είναι ότι επειδή αναφέρονται διαφορετικοί αλγόριθμοι ταξινόμησης, αυτοί δεν μπορούν να συγκριθούν με βάση την πολυπλοκότητα στη χειρότερη περίπτωση, αφού όλοι είναι O(n2), ακόμα και η Quicksort για την οποία πολλοί έχουν την εσφαλμένη εντύπωση ότι ειναι O(nlogn).
Η σύγκριση αυτή μπορεί να γίνει μόνο εξετάζοντας τι συμβαίνει στην μέση περίπτωση.
Από την άλλη σκοπός των συγγραφέων ίσως ήταν να δώσουν μια πλήρη εικόνα για την έννοια της πολυπλοκότητας.

Ο συμβολισμός Ο δίνει άνω ένα άνω φραγμα για την πολυπλοκότητα του αλγορίθμου.
Γιατί στις ενότητες 5.3.1 και 5.3.2 εξετάζει καλύτερη, μέση και χειρότερη περίπτωση και όχι μόνο χειρότερη? Αυτές νομίζω είναι απαραίτητες για υπολογισμό Ω και Θ.
Κάνω κάπου λάθος?
Ευχαριστώ
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

soula

  • Νέος
  • *
  • Μηνύματα: 2
Απ: Συμβολισμός Ο
« Απάντηση #2 στις: 07 Μάρ 2016, 11:20:42 πμ »
Συμφωνώ και με τις δύο εκδοχές που δίνεις.
Το μόνο πρόβλημα είναι το επίπεδο εμβάθυνσης στους μαθητές.
Ευχαριστώ πολύ για την απάντηση.