Σε αυτό το σεμινάριο, θα μάθετε τι είναι οι ασυμπτωτικές συμβολές. Επίσης, θα μάθετε για τη σημειογραφία Big-O, τη σημειογραφία Theta και τη σημείωση Omega.
Η αποτελεσματικότητα ενός αλγορίθμου εξαρτάται από το χρόνο, την αποθήκευση και άλλους πόρους που απαιτούνται για την εκτέλεση του αλγορίθμου. Η αποτελεσματικότητα μετράται με τη βοήθεια ασυμπτωτικών συμβολισμών.
Ένας αλγόριθμος μπορεί να μην έχει την ίδια απόδοση για διαφορετικούς τύπους εισόδων. Με την αύξηση του μεγέθους εισόδου, η απόδοση θα αλλάξει.
Η μελέτη της αλλαγής στην απόδοση του αλγορίθμου με την αλλαγή στη σειρά του μεγέθους εισόδου ορίζεται ως ασυμπτωτική ανάλυση.
Ασυμπτωτικές σημειώσεις
Οι ασυμπτωτικοί συμβολισμοί είναι οι μαθηματικοί συμβολισμοί που χρησιμοποιούνται για την περιγραφή του χρόνου εκτέλεσης ενός αλγορίθμου όταν η είσοδος τείνει προς μια συγκεκριμένη τιμή ή μια περιοριστική τιμή.
Για παράδειγμα: Στην ταξινόμηση με φυσαλίδες, όταν ο πίνακας εισόδου έχει ήδη ταξινομηθεί, ο χρόνος που απαιτείται από τον αλγόριθμο είναι γραμμικός, δηλαδή στην καλύτερη περίπτωση.
Όμως, όταν ο πίνακας εισόδου βρίσκεται σε αντίστροφη κατάσταση, ο αλγόριθμος χρειάζεται τον μέγιστο χρόνο (τετραγωνικό) για να ταξινομήσει τα στοιχεία, δηλαδή τη χειρότερη περίπτωση.
Όταν ο πίνακας εισόδου δεν έχει ταξινομηθεί ούτε σε αντίστροφη σειρά, τότε απαιτείται μέσος χρόνος. Αυτές οι διάρκειες συμβολίζονται με ασυμπτωτικούς συμβολισμούς.
Υπάρχουν κυρίως τρεις ασυμπτωτικοί συμβολισμοί:
- Μεγάλη σημειογραφία
- Ωμέγα σημειογραφία
- Theta συμβολισμός
Σημείωση Big-O (O-notation)
Η σημειογραφία Big-O αντιπροσωπεύει το άνω όριο του χρόνου εκτέλεσης ενός αλγορίθμου. Έτσι, δίνει τη χειρότερη πολυπλοκότητα ενός αλγορίθμου.
Το Big-O δίνει το ανώτερο όριο μιας συνάρτησης
O (g (n)) = (f (n): υπάρχουν θετικές σταθερές c και n 0 έτσι ώστε 0 ≦ f (n) ≦ cg (n) για όλα τα n ≧ n 0 )
Η παραπάνω έκφραση μπορεί να περιγραφεί ως συνάρτηση που f(n)ανήκει στο σύνολο O(g(n))εάν υπάρχει μια θετική σταθερά cέτσι ώστε να βρίσκεται μεταξύ 0και cg(n), για αρκετά μεγάλο n.
Για οποιαδήποτε τιμή n, ο χρόνος εκτέλεσης ενός αλγορίθμου δεν υπερβαίνει τον χρόνο που παρέχεται από O(g(n)).
Δεδομένου ότι δίνει το χειρότερο χρόνο λειτουργίας ενός αλγορίθμου, χρησιμοποιείται ευρέως για την ανάλυση ενός αλγορίθμου, καθώς πάντα ενδιαφερόμαστε για το χειρότερο σενάριο.
Ωμέγα σημειογραφία (Ω-σημειογραφία)
Η σημείωση ωμέγα αντιπροσωπεύει το κατώτερο όριο του χρόνου εκτέλεσης ενός αλγορίθμου. Έτσι, παρέχει την καλύτερη πολυπλοκότητα περιπτώσεων ενός αλγορίθμου.
Το Omega δίνει το κάτω όριο μιας συνάρτησης
Ω (g (n)) = (f (n): υπάρχουν θετικές σταθερές c και n 0 έτσι ώστε 0 ≦ cg (n) ≦ f (n) για όλα τα n ≧ n 0 )
Η παραπάνω έκφραση μπορεί να περιγραφεί ως συνάρτηση που f(n)ανήκει στο σύνολο Ω(g(n))εάν υπάρχει μια θετική σταθερά cέτσι ώστε να βρίσκεται πάνω cg(n), για αρκετά μεγάλο n.
Για οποιαδήποτε τιμή n, ο ελάχιστος χρόνος που απαιτείται από τον αλγόριθμο δίνεται από το Omega Ω(g(n)).
Σημειοθεραπεία (Θ-σημειογραφία)
Η σημειογραφία Theta περικλείει τη λειτουργία από πάνω και κάτω. Δεδομένου ότι αντιπροσωπεύει το άνω και το κατώτερο όριο του χρόνου εκτέλεσης ενός αλγορίθμου, χρησιμοποιείται για την ανάλυση της περίπλοκης μέσης περίπτωσης ενός αλγορίθμου.
Το Theta δεσμεύει τη λειτουργία εντός σταθερών παραγόντων
Για μια συνάρτηση g(n), Θ(g(n))δίνεται από τη σχέση:
Θ (g (n)) = (f (n): υπάρχουν θετικές σταθερές c 1 , c 2 και n 0 έτσι ώστε 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) για όλους n ≧ n 0 )
Η παραπάνω έκφραση μπορεί να περιγραφεί ως μια συνάρτηση που f(n)ανήκει στο σετ Θ(g(n))εάν υπάρχουν θετικές σταθερές και έτσι ώστε να μπορεί να περικλείεται μεταξύ και , για αρκετά μεγάλο n.c1c2c1g(n)c2g(n)
Εάν μια συνάρτηση f(n)βρίσκεται οπουδήποτε μεταξύ και για όλους , τότε λέγεται ότι είναι ασυμπτωτικά σφιχτή.c1g(n)c2g(n)n ≧ n0f(n)
