Big O Notation - Απλώς εξηγείται με εικόνες και βίντεο

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

Οι χρόνοι λειτουργίας του αλγορίθμου αυξάνονται με διαφορετικούς ρυθμούς

Ο γιος μου ο Ιούδας έχει πολλά παιχνίδια. Στην πραγματικότητα, έχει αποκτήσει ένα δισεκατομμύριο παιχνίδια! Θα εκπλαγείτε πόσο γρήγορα ένα παιδί μπορεί να πάρει τόσα πολλά παιχνίδια εάν είναι το πρώτο εγγόνι και στις δύο πλευρές της οικογένειας. ??

Τέλος πάντων, ο Ιούδας έχει ένα πρόβλημα. Όταν οι φίλοι του επισκέπτονται και θέλουν να παίξουν με ένα συγκεκριμένο παιχνίδι, μπορεί να χρειαστεί ΠΕΡΙΣΣΟΤΕΡΑ να βρει το παιχνίδι. Έτσι θέλει να δημιουργήσει έναν αλγόριθμο αναζήτησης για να τον βοηθήσει να βρει ένα συγκεκριμένο παιχνίδι όσο το δυνατόν γρηγορότερα. Προσπαθεί να αποφασίσει μεταξύ δύο διαφορετικών αλγορίθμων αναζήτησης: απλή αναζήτηση και δυαδική αναζήτηση. (Μην ανησυχείτε εάν δεν είστε εξοικειωμένοι με αυτούς τους αλγόριθμους.)

Ο αλγόριθμος που επιλέγεται πρέπει να είναι γρήγορος και σωστός. Από τη μία πλευρά, η δυαδική αναζήτηση είναι ταχύτερη. Και ο Ιούδας συχνά έχει μόνο περίπου 3 0 δευτερόλεπτα πριν ο φίλος του βαρεθεί ψάχνοντας ένα παιχνίδι. Από την άλλη πλευρά, ένας απλός αλγόριθμος αναζήτησης είναι πιο εύκολο να γραφτεί και υπάρχει λιγότερη πιθανότητα εισαγωγής σφαλμάτων. Σίγουρα θα ήταν ενοχλητικό εάν ο φίλος του βρήκε σφάλματα στον κώδικα του! Για να είμαστε πολύ προσεκτικοί, ο Ιούδας αποφασίζει να χρονομετρήσει και τους δύο αλγόριθμους με μια λίστα με 100 παιχνίδια.

Ας υποθέσουμε ότι χρειάζεται 1 χιλιοστό του δευτερολέπτου για να ελέγξετε ένα παιχνίδι. Με απλή αναζήτηση, ο Ιούδας πρέπει να ελέγξει 100 παιχνίδια, οπότε η αναζήτηση διαρκεί 100 ms για να τρέξει. Από την άλλη πλευρά, πρέπει μόνο να ελέγξει 7 παιχνίδια με δυαδική αναζήτηση (το log2 100 είναι περίπου 7, μην ανησυχείτε εάν αυτό το μαθηματικό είναι μπερδεμένο καθώς δεν είναι το κύριο σημείο αυτού του άρθρου), έτσι ώστε η αναζήτηση να διαρκεί 7 ms τρέχω. Αλλά στην πραγματικότητα, η λίστα θα έχει ένα δισεκατομμύριο παιχνίδια. Εάν ναι, πόσο καιρό θα διαρκέσει η απλή αναζήτηση; Πόσο διαρκεί η δυαδική αναζήτηση;

Χρόνος εκτέλεσης για απλή αναζήτηση έναντι δυαδικής αναζήτησης, με λίστα 100 στοιχείων

Ο Ιούδας εκτελεί δυαδική αναζήτηση με 1 δισεκατομμύριο παιχνίδια και διαρκεί 30 ms (το log2 1.000.000.000 είναι περίπου 30). "32 ms!" νομίζει. «Η δυαδική αναζήτηση είναι περίπου 15 φορές ταχύτερη από την απλή αναζήτηση, επειδή η απλή αναζήτηση διήρκεσε 100 ms με 100 στοιχεία και η δυαδική αναζήτηση χρειάστηκε 7 ms. Έτσι, η απλή αναζήτηση θα διαρκέσει 30 × 15 = 450 ms, σωστά; Πολύ κάτω από τα 30 δευτερόλεπτα χρειάζεται να βαρεθεί ο φίλος μου. " Ο Ιούδας αποφασίζει να πάει με απλή αναζήτηση. Αυτή είναι η σωστή επιλογή;

Όχι. Αποδεικνύεται ότι ο Ιούδας ήταν λάθος και έχασε έναν φίλο για ζωή. ; Ο χρόνος εκτέλεσης για απλή αναζήτηση με 1 δισεκατομμύριο αντικείμενα θα είναι 1 δισεκατομμύριο ms, δηλαδή 11 ημέρες! Το πρόβλημα είναι ότι οι χρόνοι εκτέλεσης για δυαδική αναζήτηση και απλή αναζήτηση δεν αυξάνονται με τον ίδιο ρυθμό.

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

Έτσι ο Ιούδας έκανε λάθος ότι η δυαδική αναζήτηση ήταν πάντα 15 φορές πιο γρήγορη από την απλή αναζήτηση. Αν υπάρχουν 1 δισεκατομμύριο παιχνίδια, μοιάζει περισσότερο με 33 εκατομμύρια φορές πιο γρήγορα.

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

Η σημείωση Big O σας λέει πόσο γρήγορα είναι ένας αλγόριθμος. Για παράδειγμα, ας υποθέσουμε ότι έχετε μια λίστα με μέγεθος n . Η απλή αναζήτηση πρέπει να ελέγχει κάθε στοιχείο, οπότε θα χρειαστούν n λειτουργίες. Ο χρόνος εκτέλεσης στη σημείωση Big O είναι O ( n ).

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

Ας κάνουμε ένα άλλο παράδειγμα. Η δυαδική αναζήτηση χρειάζεται λειτουργίες log n για να ελέγξει μια λίστα με το μέγεθος n . Ποιος είναι ο χρόνος λειτουργίας στη σημείωση Big O; Είναι O (log n ). Γενικά, η σημείωση Big O γράφεται ως εξής.

Αυτό σας λέει τον αριθμό των λειτουργιών που θα κάνει ένας αλγόριθμος. Ονομάζεται Big O notation επειδή βάζετε ένα "μεγάλο O" μπροστά από τον αριθμό των λειτουργιών.

Το Big O δημιουργεί έναν χειρότερο χρόνο εκτέλεσης

Ας υποθέσουμε ότι χρησιμοποιείτε απλή αναζήτηση για να αναζητήσετε έναν χρήστη στη βάση δεδομένων χρήστη. Γνωρίζετε ότι η απλή αναζήτηση χρειάζεται O ( n ) χρόνο για να τρέξει, πράγμα που σημαίνει στη χειρότερη περίπτωση, ότι ο αλγόριθμος θα πρέπει να κοιτάξει μέσα από κάθε χρήστη στη βάση δεδομένων. Σε αυτήν την περίπτωση, αναζητάτε έναν χρήστη με το όνομα "aardvark213". Αυτός είναι ο πρώτος χρήστης στη λίστα. Έτσι ο αλγόριθμος σας δεν έπρεπε να κοιτάξει κάθε καταχώριση - το βρήκε στην πρώτη προσπάθεια. Χρειάστηκε χρόνος ο αλγόριθμος O ( n ); Ή χρειάστηκε χρόνος O (1) επειδή βρήκε το άτομο στην πρώτη προσπάθεια;

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

Μερικοί συνηθισμένοι χρόνοι εκτέλεσης Big O

Ακολουθούν πέντε χρόνοι Big O που θα συναντήσετε πολύ, ταξινομημένοι από ταχύτερος έως πιο αργός:

  • O (log n ), επίσης γνωστό ως χρόνος log. Παράδειγμα: Δυαδική αναζήτηση.
  • O ( n ), επίσης γνωστό ως γραμμικός χρόνος . Παράδειγμα: Απλή αναζήτηση.
  • O ( n * log n ). Παράδειγμα: Ένας αλγόριθμος γρήγορης ταξινόμησης, όπως γρήγορη ταξινόμηση.
  • O ( n 2). Παράδειγμα: Ένας αργός αλγόριθμος ταξινόμησης, όπως η επιλογή επιλογής.
  • Ο ( ν !). Παράδειγμα: Ένας πολύ αργός αλγόριθμος, όπως ο ταξιδιωτικός πωλητής.

Οπτικοποίηση διαφορετικών χρόνων εκτέλεσης Big O

Ας υποθέσουμε ότι σχεδιάζετε ένα πλέγμα 16 κουτιών και μπορείτε να επιλέξετε από 5 διαφορετικούς αλγόριθμους για να το κάνετε. Εάν χρησιμοποιήσετε τον πρώτο αλγόριθμο, θα χρειαστείτε O (log n ) χρόνο για να σχεδιάσετε το πλέγμα. Μπορείτε να κάνετε 10 λειτουργίες ανά δευτερόλεπτο. Με το χρόνο O (log n ), θα χρειαστείτε 4 λειτουργίες για να σχεδιάσετε ένα πλέγμα 16 κουτιών (log 16 base 2 is 4). Έτσι θα χρειαστείτε 0,4 δευτερόλεπτα για να σχεδιάσετε το πλέγμα. Τι γίνεται αν πρέπει να σχεδιάσετε 1.024 κουτιά; Θα χρειαστείτε 1,024 = 10 λειτουργίες ή 1 δευτερόλεπτο για να σχεδιάσετε ένα πλέγμα 1.024 κουτιών. Αυτοί οι αριθμοί χρησιμοποιούν τον πρώτο αλγόριθμο.

Ο δεύτερος αλγόριθμος είναι πιο αργός: παίρνει O ( n ) χρόνο. Θα χρειαστούν 16 πράξεις για να τραβήξουν 16 κουτιά, και θα χρειαστούν 1.024 πράξεις για να τραβήξουν 1.024 κουτιά. Πόσος χρόνος είναι σε δευτερόλεπτα;

Δείτε πόσο καιρό θα χρειαστεί να σχεδιάσετε ένα πλέγμα για τους υπόλοιπους αλγόριθμους, από ταχύτερα έως πιο αργά:

Υπάρχουν και άλλοι χρόνοι εκτέλεσης, αλλά αυτοί είναι οι πέντε πιο συνηθισμένοι.

Αυτή είναι μια απλοποίηση. Στην πραγματικότητα, δεν μπορείτε να μετατρέψετε από το χρόνο εκτέλεσης του Big O σε πολλές λειτουργίες, αλλά αυτό είναι καλή εκτίμηση.

συμπέρασμα

Εδώ είναι τα κύρια προϊόντα:

  • Η ταχύτητα του αλγορίθμου δεν μετριέται σε δευτερόλεπτα, αλλά στην αύξηση του αριθμού των λειτουργιών.
  • Αντ 'αυτού, μιλάμε για το πόσο γρήγορα αυξάνεται ο χρόνος εκτέλεσης ενός αλγορίθμου καθώς αυξάνεται το μέγεθος της εισόδου.
  • Ο χρόνος εκτέλεσης των αλγορίθμων εκφράζεται με τη σημείωση Big O.
  • Το O (log n ) είναι ταχύτερο από το O ( n ), αλλά γίνεται πολύ πιο γρήγορο καθώς μεγαλώνει η λίστα των στοιχείων που αναζητάτε.

Και εδώ είναι ένα βίντεο που καλύπτει πολλά όσα υπάρχουν σε αυτό το άρθρο και πολλά άλλα.

Ελπίζω ότι αυτό το άρθρο σας έφερε περισσότερη σαφήνεια σχετικά με τη σημειογραφία Big O Αυτό το άρθρο βασίζεται σε ένα μάθημα στο βίντεό μου από Manning Publications που ονομάζεται Algorithms in Motion. Το μάθημα βασίζεται στο εκπληκτικό βιβλίο Αλγόριθμοι Grokking του Adit Bhargava. Είναι αυτός που σχεδίασε όλες τις διασκεδαστικές εικόνες σε αυτό το άρθρο.

Εάν μάθετε καλύτερα μέσω βιβλίων, πάρτε το βιβλίο! Εάν μάθετε καλύτερα μέσω βίντεο, σκεφτείτε να αγοράσετε το μάθημά μου. Μπορείτε να κερδίσετε 39% έκπτωση στο μάθημά μου χρησιμοποιώντας τον κωδικό « 39carnes ».