AlegsaOnline.com

Ο συμβολισμός Big O

Συγγραφέας: Leandro Alegsa

11-04-3647

Ο συμβολισμός Big O είναι ένας τρόπος σύγκρισης αλγορίθμων. Τους συγκρίνει υπολογίζοντας πόση μνήμη απαιτείται και πόσος χρόνος απαιτείται για την ολοκλήρωσή τους.

Ο συμβολισμός Big O χρησιμοποιείται συχνά για τον προσδιορισμό της πολυπλοκότητας ενός προβλήματος, γνωστή και ως κλάση πολυπλοκότητας του προβλήματος. Ο μαθηματικός Paul Bachmann (1837-1920) ήταν ο πρώτος που χρησιμοποίησε αυτόν τον συμβολισμό, στη δεύτερη έκδοση του βιβλίου του "Analytische Zahlentheorie", το 1896. Ο Edmund Landau (1877-1938) έκανε τον συμβολισμό δημοφιλή. Για το λόγο αυτό, όταν οι άνθρωποι μιλούν για σύμβολα Landau, αναφέρονται σε αυτή τη σημειογραφία.

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

Το Big O είναι μια έκφραση που βρίσκει το χειρότερο σενάριο χρόνου εκτέλεσης, δείχνοντας πόσο αποδοτικός είναι ένας αλγόριθμος χωρίς να χρειάζεται να τρέξει το πρόγραμμα σε υπολογιστή. Αυτό είναι επίσης χρήσιμο, καθώς διαφορετικοί υπολογιστές μπορεί να έχουν διαφορετικό υλικό και επομένως να χρειάζονται διαφορετικά χρονικά διαστήματα για την ολοκλήρωσή του. Δεδομένου ότι το Big O υποθέτει πάντα τη χειρότερη περίπτωση, μπορεί να δείξει μια συνεπή μέτρηση της ταχύτητας: ανεξάρτητα από το υλικό σας, το O ( 1 ) {\displaystyle O(1)} $O(1)$ θα ολοκληρώνεται πάντα γρηγορότερα από το O ( n ! ) {\displaystyle O(n!)} $O(n!)$ επειδή έχουν διαφορετικά επίπεδα αποδοτικότητας.

Παραδείγματα

Τα παρακάτω παραδείγματα χρησιμοποιούν κώδικα γραμμένο σε Python. Σημειώστε ότι αυτή δεν είναι μια πλήρης λίστα των τύπων Big O.

Σταθερή

O ( 1 ) {\displaystyle O(1)} $O(1)$ . Παίρνει πάντα τον ίδιο χρόνο ανεξάρτητα από την είσοδο. Για παράδειγμα, πάρτε μια συνάρτηση που δέχεται έναν ακέραιο (που ονομάζεται x) και επιστρέφει τη διπλάσια τιμή του:

def double(x): return x * 2 #Επιστρέφει την τιμή του x επί 2

Μετά την αποδοχή της εισόδου, η συνάρτηση αυτή θα κάνει πάντα ένα βήμα για να επιστρέψει μια έξοδο. Είναι σταθερό επειδή θα χρειάζεται πάντα τον ίδιο χρόνο, οπότε είναι O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Γραμμική

O ( n ) {\displaystyle O(n)} $O(n)$ . Αυξάνεται ανάλογα με το μέγεθος της εισόδου, που αντιπροσωπεύεται από το n {\displaystyle n} . Ας υποθέσουμε ότι μια συνάρτηση δέχεται n και επιστρέφει κάθε αριθμό από το 1 έως το n:

def count(n): i = 1 #Δημιουργήστε έναν μετρητή με όνομα "i" και τιμή 1 while i <= n: #While i is less-than or equal to n print(i) #Print the value of i i = i + 1 #Redefine i as "the value of i + 1"

Αν εισάγαμε την τιμή 5, τότε αυτό θα έβγαζε 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,3,4,5} $1,2,3,4,5$ , απαιτώντας 5 βρόχους για να ολοκληρωθεί. Αντίστοιχα, αν εισάγουμε την τιμή 100 θα έβγαζε 1 , 2 , 3...98 , 99 , 100 {\displaystyle 1,2,3...98,99,100} $1,2,3...98,99,100$ , απαιτώντας 100 βρόχους για να ολοκληρωθεί. Αν η είσοδος είναι n {\displaystyle n} τότε ο χρόνος εκτέλεσης του αλγορίθμου είναι ακριβώς n {\displaystyle n} βρόχοι κάθε φορά, επομένως είναι O ( n ) {\displaystyle O(n)} $O(n)$ .

Παραγοντικό

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ . Αυξάνεται σε παραγοντικά ποσά, πράγμα που σημαίνει ότι ο χρόνος που απαιτείται αυξάνεται μαζικά με την είσοδο. Για παράδειγμα, ας πούμε ότι επιθυμούμε να επισκεφθούμε πέντε πόλεις σε όλο τον κόσμο και θέλουμε να δούμε κάθε πιθανή διάταξη (αντιμετάθεση). Ένας αλγόριθμος που θα μπορούσαμε να γράψουμε χρησιμοποιώντας τη βιβλιοθήκη itertools της Python είναι ο εξής:

import itertools #Εισαγωγή της βιβλιοθήκης itertools cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Ένας πίνακας με τις πόλεις που επιλέξαμε def permutations(cities): #Λαμβάνοντας έναν πίνακα πόλεων ως είσοδο: for i in itertools. permutations(cities): #Για κάθε αντιμετάθεση των στοιχείων μας (ανατίθεται στη μεταβλητή "i") print(i) #Έξοδος i

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

('Λονδίνο', 'Παρίσι', 'Βερολίνο', 'Άμστερνταμ', 'Ρώμη') ('Λονδίνο', 'Παρίσι', 'Βερολίνο', 'Ρώμη', 'Άμστερνταμ') ('Λονδίνο', 'Παρίσι', 'Άμστερνταμ', 'Βερολίνο', 'Ρώμη') ... ('Ρώμη', 'Άμστερνταμ', 'Παρίσι', 'Βερολίνο', 'Λονδίνο') ('Ρώμη', 'Άμστερνταμ', 'Βερολίνο', 'Λονδίνο', 'Παρίσι') ('Ρώμη', 'Άμστερνταμ', 'Βερολίνο', 'Παρίσι', 'Λονδίνο')

Εδώ η λίστα εισόδου μας έχει μήκος 5 στοιχεία και για κάθε επιλογή οι εναπομείνασες επιλογές μας μειώνονται κατά 1. Με άλλα λόγια, οι 5 είσοδοι μας επιλέγουν 5 × 4 × 3 × 2 × 1 {\displaystyle 5\times 4\times 3\times 2\times 1} $5\times 4\times 3\times 2\times 1$ στοιχεία (ή 5 ! {\displaystyle 5!} $5!$ ). Αν η είσοδός μας είναι n {\displaystyle n} πόλεις, τότε ο αριθμός των εξόδων είναι n ! {\displaystyle n! } $n!$ ; με άλλα λόγια, υποθέτοντας ότι θα περάσουμε από κάθε μετάλλαξη θα χρειαστούμε O ( n ! ) {\displaystyle O(n!)} $O(n!)$ βρόχους για να την ολοκληρώσουμε.

Little-o Notation

Μια πιο αυστηρή εκδοχή του Big O είναι το little-o. Η διαφορά μεταξύ του big O και του little-o είναι ότι το little-o είναι ένα αυστηρό άνω όριο: ενώ το O ( n ) {\displaystyle O(n)} $O(n)$ σημαίνει ότι ο χρόνος ολοκλήρωσης θα αυξηθεί σε αυτό το μέγιστο με βάση το μέγεθος της εισόδου, το o ( n ) {\displaystyle o(n)} $o(n)$ σημαίνει ότι ο χρόνος ολοκλήρωσης θα είναι γενικά κάτω από αυτό το χρονικό διάστημα. Με άλλα λόγια, το Big O υποθέτει ότι κάθε βρόχος θα ακολουθήσει τη μεγαλύτερη διαδρομή και ότι η διαδικασία θα διαρκέσει όσο το δυνατόν περισσότερο, ενώ το little-o είναι πιο ρεαλιστικό όσον αφορά τους πραγματικούς χρόνους εκτέλεσης- αν ο αριθμός των βρόχων βασίζεται στη ρίψη ενός 6πλευρου ζαριού, το Big O θα υποθέτει πάντα ότι ρίχνεται ένα 6, ενώ το little-o θα λαμβάνει υπόψη του την ίση πιθανότητα να ριχτούν και άλλοι αριθμοί.

Ερωτήσεις και απαντήσεις

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

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

Ερ: Ποιος ήταν ο πρώτος που χρησιμοποίησε αυτή τη σημειογραφία;

Α: Ο μαθηματικός Paul Bachmann (1837-1920) ήταν ο πρώτος που χρησιμοποίησε αυτή τη σημειογραφία στο βιβλίο του "Analytische Zahlentheorie" το 1896.

Ερ: Τι σημαίνει το Big O;

Α: Το Big O σημαίνει "τάξη της συνάρτησης", η οποία αναφέρεται στον ρυθμό αύξησης των συναρτήσεων.

Ε: Πώς χρησιμοποιείται το Big O;

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

Ε: Τι είναι τα σύμβολα Landau;

Α: Τα σύμβολα Landau αναφέρονται στη σημειογραφία Big O, που πήρε το όνομά της από τον Edmund Landau (1877-1938), ο οποίος έκανε αυτή τη σημειογραφία δημοφιλή.

Ε: Γιατί είναι χρήσιμο το Big O;

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