Εξηγήθηκε η μεγάλη θήτα και η ασυμπτωτική σημείωση

Το Big Omega μας λέει το κάτω όριο του χρόνου εκτέλεσης μιας συνάρτησης και το Big O μας λέει το ανώτερο όριο.

Συχνά φορές, είναι διαφορετικές και δεν μπορούμε να δώσουμε εγγύηση στο χρόνο εκτέλεσης - θα διαφέρει μεταξύ των δύο ορίων και των εισόδων. Αλλά τι συμβαίνει όταν είναι τα ίδια; Τότε μπορούμε να δώσουμε ένα δεσμευμένο θήτα (Θ) - η λειτουργία μας θα τρέξει εκείνη τη στιγμή, ανεξάρτητα από το τι εισάγουμε.

Σε γενικές γραμμές, πάντα θέλουμε να δώσουμε ένα δεσμευμένο θήτα, αν είναι δυνατόν, επειδή είναι το πιο ακριβές και πιο στενό. Εάν δεν μπορούμε να δώσουμε ένα δεσμευμένο θήτα, το επόμενο καλύτερο πράγμα είναι το πιο στενό δυνατό δεσμευμένο O.

Πάρτε, για παράδειγμα, μια συνάρτηση που αναζητά έναν πίνακα για την τιμή 0:

def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false
  1. Ποια είναι η καλύτερη περίπτωση; Λοιπόν, εάν ο πίνακας που δίνουμε έχει 0 ως την πρώτη τιμή, θα χρειαστεί σταθερός χρόνος: Ω (1)
  2. Ποια είναι η χειρότερη περίπτωση; Εάν ο πίνακας δεν περιέχει 0, θα έχουμε επαναλάβει ολόκληρο τον πίνακα: O (n)

Το έχουμε δώσει ένα ωμέγα και το O δεσμευμένο, τι γίνεται λοιπόν με το theta; Δεν μπορούμε να το δώσουμε! Ανάλογα με τον πίνακα που του δίνουμε, ο χρόνος εκτέλεσης θα είναι κάπου μεταξύ σταθεράς και γραμμικής.

Ας αλλάξουμε λίγο τον κωδικό μας.

def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)

Μπορείτε να σκεφτείτε μια καλύτερη και χειρότερη περίπτωση; Δεν μπορώ! Ανεξάρτητα από τον πίνακα που το δίνουμε, πρέπει να επαναλάβουμε κάθε τιμή του πίνακα. Έτσι, η συνάρτηση θα διαρκέσει τουλάχιστον το χρόνο (Ω (n)), αλλά επίσης γνωρίζουμε ότι δεν θα διαρκέσει περισσότερο από το χρόνο n (O (n)). Τι σημαίνει αυτό? Η λειτουργία μας θα διαρκέσει ακριβώς n χρόνο: Θ (n).

Εάν τα όρια είναι σύγχυση, σκεφτείτε το έτσι. Έχουμε 2 αριθμούς, x και y. Μας δίνεται ότι x <= y και ότι y <= x. Εάν το x είναι μικρότερο ή ίσο με το y και το y είναι μικρότερο ή ίσο με το x, τότε το x πρέπει να είναι ίσο με το y!

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

  1. παίρνω
  2. αφαιρώ
  3. Προσθήκη

Τα πράγματα γίνονται ακόμη πιο ενδιαφέροντα όταν εξετάζετε μια λίστα με διπλή σύνδεση!

Ασυμπτωτική σημειογραφία

Πώς μετράμε την τιμή απόδοσης των αλγορίθμων;

Σκεφτείτε πώς ο χρόνος είναι ένας από τους πιο πολύτιμους πόρους μας. Στον υπολογισμό, μπορούμε να μετρήσουμε την απόδοση με το χρόνο που χρειάζεται μια διαδικασία για να ολοκληρωθεί. Εάν τα δεδομένα που υποβάλλονται σε επεξεργασία από δύο αλγόριθμους είναι τα ίδια, μπορούμε να αποφασίσουμε για την καλύτερη εφαρμογή για την επίλυση ενός προβλήματος.

Το κάνουμε αυτό καθορίζοντας τα μαθηματικά όρια ενός αλγορίθμου. Αυτά είναι τα big-O, big-omega και big-theta, ή οι ασυμπτωτικοί συμβολισμοί ενός αλγορίθμου. Σε ένα γράφημα το big-O θα είναι το μεγαλύτερο που μπορεί να πάρει ένας αλγόριθμος για οποιοδήποτε δεδομένο σύνολο δεδομένων ή το "άνω όριο". Το μεγάλο-ωμέγα είναι σαν το αντίθετο του big-O, το «κάτω όριο». Εκεί ο αλγόριθμος φτάνει στην τελική του ταχύτητα για οποιοδήποτε σύνολο δεδομένων. Το μεγάλο θήτα είναι είτε η ακριβής τιμή απόδοσης του αλγορίθμου, είτε ένα χρήσιμο εύρος μεταξύ στενών άνω και κάτω ορίων.

Μερικά παραδείγματα:

  • «Η παράδοση θα είναι εκεί μέσα στη ζωή σου.» (big-O, άνω όριο)
  • "Μπορώ να σας πληρώσω τουλάχιστον ένα δολάριο." (μεγάλα ωμέγα, κάτω όριο)
  • «Το υψηλό σήμερα θα είναι 25ºC και το χαμηλότερο θα είναι 19ºC.» (μεγάλο-θήτα, στενό)
  • "Είναι ένα χιλιόμετρο με τα πόδια από την παραλία." (μεγάλο-θήτα, ακριβές)

Περισσότερες πληροφορίες:

//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-notation-represent //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/