Τι είναι η σημειογραφία Big-O;

Αναρωτηθήκατε ποτέ γιατί χρειάστηκε τόσο πολύ ένα πρόγραμμα που γράψατε; Ίσως θα θέλατε να μάθετε εάν μπορείτε να κάνετε τον κωδικό σας πιο αποτελεσματικό. Η κατανόηση του τρόπου λειτουργίας του κώδικα μπορεί να φέρει τον κώδικά σας στο επόμενο επίπεδο. Η σημειογραφία Big-O είναι ένα εύχρηστο εργαλείο για τον υπολογισμό της αποτελεσματικότητας του κώδικα σας.

Τι είναι η σημείωση Big-O;

Η σημειογραφία Big-O σάς δίνει έναν τρόπο υπολογισμού του χρόνου που απαιτείται για την εκτέλεση του κωδικού σας. Μπορείτε φυσικά να ορίσετε πόσο χρόνο χρειάζεται ο κώδικάς σας, αλλά με αυτήν τη μέθοδο, είναι δύσκολο να εντοπίσετε μικρές χρονικές διαφορές. Για παράδειγμα, ο χρόνος που απαιτείται μεταξύ της εκτέλεσης 20 και 50 γραμμών κώδικα είναι πολύ μικρός. Ωστόσο, σε ένα μεγάλο πρόγραμμα, αυτές οι ανεπάρκειες μπορούν να αυξηθούν.

Η σημείωση Big-O μετρά πόσα βήματα πρέπει να εκτελέσει ένας αλγόριθμος για να μετρήσει την αποτελεσματικότητά του. Η προσέγγιση του κωδικού σας με αυτόν τον τρόπο μπορεί να είναι πολύ αποτελεσματική αν χρειαστεί να συντονίσετε τον κωδικό σας για να αυξήσετε την αποτελεσματικότητα. Η σημειογραφία Big-O θα σας επιτρέψει να μετρήσετε διαφορετικούς αλγόριθμους με τον αριθμό των βημάτων που χρειάζεται για να εκτελέσετε και να συγκρίνετε αντικειμενικά την αποτελεσματικότητα των αλγορίθμων.

Πώς υπολογίζετε τη σημειογραφία Big-O

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

Αλγόριθμος 1:

def sockCounter (numberOfPairs):
individualSocks = 0
για εύρος x (numberOfPairs):
individualSocks = individualSocks + 2
επιστροφή μεμονωμένων κάλτσες

Αλγόριθμος 2:

def sockCounter (numberOfPairs):
αριθμός επιστροφήςOfPairs * 2

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

ΣΧΕΤΙΖΟΜΑΙ ΜΕ: Τι είναι μια λειτουργία στον προγραμματισμό;

Τι είναι μια λειτουργία στον προγραμματισμό;

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

Ο αλγόριθμος 1 έχει πολλά βήματα:

1. Εκχωρεί μια τιμή μηδέν στη μεταβλητή individualSocks.
2. Εκχωρεί μια τιμή στη μεταβλητή i.
3. Συγκρίνει την τιμή του i με το numberOfPairs.
4. Προσθέτει δύο σε individualSocks.
5. Εκχωρεί την αυξημένη αξία του individualSocks στον εαυτό του.
6. Αυξάνει το ένα προς ένα.
7. Στη συνέχεια βγαίνει πίσω στα βήματα 3 έως 6 για τον ίδιο αριθμό φορών με (indiviualSocks - 1).

Ο αριθμός των βημάτων που πρέπει να ολοκληρώσουμε για έναν αλγόριθμο μπορεί να εκφραστεί ως:

4n + 2

Υπάρχουν τέσσερα βήματα που πρέπει να ολοκληρώσουμε n φορές. Σε αυτήν την περίπτωση, το n ισούται με την τιμή του numberOfPairs. Υπάρχουν επίσης 2 βήματα που ολοκληρώνονται μία φορά.

Συγκριτικά, ο αλγόριθμος 2 έχει μόνο ένα βήμα. Η τιμή του numberOfPairs πολλαπλασιάζεται με δύο. Θα το εκφράσουμε ως:

1

Εάν δεν ήταν ήδη εμφανές, μπορούμε τώρα εύκολα να δούμε ότι ο αλγόριθμος 2 είναι πιο αποτελεσματικός από λίγο.

Ανάλυση Big-O

Γενικά, όταν ενδιαφέρεστε για τη σημείωση Big-O ενός αλγορίθμου, ενδιαφέρεστε περισσότερο για τη συνολική απόδοση και λιγότερο για την ανάλυση λεπτών κόκκων του αριθμού των βημάτων. Για να απλοποιήσουμε τη σημειογραφία, μπορούμε απλώς να δηλώσουμε το μέγεθος της αποτελεσματικότητας.

Στα παραπάνω παραδείγματα, ο αλγόριθμος 2 θα εκφράζεται ως ένας:

Ο (1)

Αλλά ο αλγόριθμος 1 θα απλοποιηθεί ως εξής:

Επί)

Αυτό το γρήγορο στιγμιότυπο μάς λέει πώς η απόδοση του αλγορίθμου συνδέεται με την τιμή του n. Όσο μεγαλύτερος είναι ο αριθμός, τόσο περισσότερα βήματα θα χρειαστεί να ολοκληρώσει ο αλγόριθμος.

Γραμμικός κώδικας

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

Τετραγωνικός κώδικας

Δεν είναι όλες οι σχέσεις τόσο απλές όσο το γραμμικό παράδειγμα. Φανταστείτε ότι έχετε έναν πίνακα 2D και θα θέλατε να αναζητήσετε μια τιμή στον πίνακα. Ίσως δημιουργήσετε έναν αλγόριθμο ως εξής:

def searchForValue (targetValue, arraySearched):
foundTarget = Λάθος
για x σε πίνακα
για y σε x:
εάν (y == targetValue):
foundTarget = True
return foundTarget

Σε αυτό το παράδειγμα, ο αριθμός των βημάτων εξαρτάται από τον αριθμό των συστοιχιών στο arraySearched και τον αριθμό των τιμών σε κάθε πίνακα. Έτσι, ο απλοποιημένος αριθμός βημάτων θα ήταν n * n ή n².

Αυτή η σχέση είναι μια τετραγωνική σχέση, που σημαίνει ότι ο αριθμός των βημάτων στον αλγόριθμό μας αυξάνεται εκθετικά με το n. Στη σημείωση Big-O, θα το γράφατε ως:

O (n²)

ΣΧΕΤΙΖΟΜΑΙ ΜΕ: Χρήσιμα εργαλεία για έλεγχο, καθαρισμό και βελτιστοποίηση αρχείων CSS

Λογαριθμικός κώδικας

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

log 2 (8) = 3

Το ημερολόγιο ισούται με τρία γιατί αν η βάση μας ήταν 2, θα χρειαζόμασταν μια εκθετική τιμή 3 για να φτάσουμε στον αριθμό 8.

Έτσι, η σχέση μιας λογαριθμικής συνάρτησης είναι το αντίθετο μιας εκθετικής σχέσης. Καθώς το n αυξάνεται, απαιτούνται λιγότερα νέα βήματα για την εκτέλεση του αλγορίθμου.

Με μια πρώτη ματιά, αυτό φαίνεται αντιδιαισθητικό. Πώς μπορούν τα βήματα ενός αλγορίθμου να αναπτυχθούν πιο αργά από το n; Ένα καλό παράδειγμα αυτού είναι οι δυαδικές αναζητήσεις. Ας σκεφτούμε έναν αλγόριθμο για αναζήτηση ενός αριθμού σε μια σειρά από μοναδικές τιμές.

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

Όπως μπορείτε να δείτε, δεδομένου ότι οι δυαδικές αναζητήσεις εξαλείφουν τις μισές από τις πιθανές τιμές κάθε πέρασμα, καθώς το n μεγαλώνει, η επίδραση στον αριθμό των φορών που ελέγχουμε ότι ο πίνακας επηρεάζεται μόλις. Για να το εκφράσουμε στη σημείωση Big-O, γράφουμε:

O (ημερολόγιο (n))

Η σημασία της σημειογραφίας Big-O

Το Big-O nation σας δίνει έναν γρήγορο και εύκολο τρόπο να επικοινωνήσετε πόσο αποτελεσματικός είναι ένας αλγόριθμος. Αυτό διευκολύνει την επιλογή μεταξύ διαφορετικών αλγορίθμων. Αυτό μπορεί να είναι ιδιαίτερα χρήσιμο εάν χρησιμοποιείτε έναν αλγόριθμο από μια βιβλιοθήκη και δεν γνωρίζετε απαραίτητα πώς φαίνεται ο κώδικας.

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

10 πιο συνηθισμένα λάθη προγραμματισμού και κωδικοποίησης

Τα λάθη κωδικοποίησης μπορούν να οδηγήσουν σε τόσα πολλά προβλήματα. Αυτές οι συμβουλές θα σας βοηθήσουν να αποφύγετε λάθη προγραμματισμού και να διατηρήσετε τον κώδικα σας σημαντικό.

Σχετικά με τον Συγγραφέα