Πρέπει να ομολογήσω ότι όταν άκουσα για πρώτη φορά το Big O notation, μου πήρε αρκετό καιρό να αντιληφθώ πραγματικά την έννοιά του. Αρκετές ήταν η φορές που πίστευα ότι το είχα καταλάβει, μέχρι που ερχόταν μια στιγμή να μου αποδείξει το αντίθετο. Ίσως φταίει ότι δεν είμαι μαθηματικός και δεν έχω «συμφιλιωθεί» με κάποιες έννοιες. Ίσως φταίει ότι δεν υπάρχει «απλή» εξήγηση στο ίντερνετ. Ίσως απλά να είμαι λίγο πιο χαζός απ’ όσο πίστευα. Όπως και να ‘χει, ήρθε η ώρα να κάνω τη δική μου προσπάθεια να εξηγήσω το Big O notation μιας και με λίγη αναζήτηση στο google, δεν βρήκα κανένα άρθρο στα ελληνικά. Θα πρωτοπορήσω λοιπόν! (lol)

 

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

Το \(O(1)\) περιγράφει έναν αλγόριθμο που θα εκτελείται πάντα στον ίδιο χρόνο (ή χώρο), άσχετα με το μέγεθος των δεδομένων που του εισάγουμε.

Στον παραπάνω κώδικα έχουμε ένα array με strings και τσεκάρουμε αν το πρώτο στοιχείο του array είναι κενό. Από την στιγμή που κοιτάμε μόνο το πρώτο στοιχείο, δεν μας νοιάζει το πόσα στοιχεία έχει συνολικά μέσα το array. Όσα και να έχει, εμείς θα κοιτάμε πάντα το πρώτο και γι’ αυτό τον λόγο, ο κώδικας θα εκτελείται πάντα στον ίδιο χρόνο. Αν δηλαδή βάλουμε 10 στοιχεία στο array και ο υπολογιστής μας θέλει 1 δευτερόλεπτο να εκτελέσει τον κώδικα, τον ίδιο ακριβώς χρόνο θα θέλει κι όταν βάλουμε 1.000.000 στοιχεία στο array.

Το \(O(n)\) περιγράφει έναν αλγόριθμο του οποίου η απόδοση αυξάνεται γραμμικά και κατ’ αναλογία του μεγέθους των δεδομένων που εισάγουμε.

Εδώ έχουμε πάλι ένα array με strings και ψάχνουμε μια συγκεκριμένη τιμή. Ο χρόνος που χρειάζεται να βρούμε την τιμή που θέλουμε είναι άμεσα συνδεδεμένος με το πόσες φορές θα πρέπει να εκτελεστεί η εντολή for. Εδώ αξίζει να σημειώσουμε ότι το Big O περιγράφει το χειρότερο πιθανό σενάριο σε κάθε αλγόριθμο που στην προκειμένη περίπτωση, είναι να βρίσκεται η τιμή που θέλουμε στην τελευταία θέση. Αν λοιπόν το array μας περιέχει 10 στοιχεία, το χειρότερο που μπορεί να μας συμβεί είναι η τιμή που ψάχνουμε να βρίσκεται στην θέση 10 άρα το for θα εκτελεστεί 10 φορές. Αν είχαμε 1.000 στοιχεία στο array, το for θα έπρεπε να εκτελεστεί 1.000 φορές κ.ο.κ. Μπορούμε λοιπόν να μετρήσουμε ότι για παράδειγμα, με 10 στοιχεία χρειαζόμαστε 1 δευτερόλεπτο εκτέλεσης και να συμπεράνουμε με ασφάλεια ότι τα 1.000 στοιχεία απαιτούν 100 δευτερόλεπτα. Αν θέλαμε να αναπαραστήσουμε γραφικά το \(O(n)\), θα ήταν κάπως έτσι:

Αυτό μας δείχνει ότι όσο αυξάνεται το \(x\) (δηλαδή τα δεδομένα που εισάγουμε), το \(y\) (ο χρόνος ή ο χώρος) αυξάνεται γραμμικά. Αν μια εντολή θέλει 1 δευτερόλεπτο, οι 10 εντολές θέλουν 10 δευτερόλεπτα. Το πώς εμφανίζεται η γραμμή δεν μας ενδιαφέρει, δηλαδή όλα αυτά τα γραφήματα:

είναι όλα αναπαραστάσεις του \(O(n)\) απλά η μεταβολή είναι πιο γρήγορη. Ο ρυθμός όμως παραμένει γραμμικός.

Το \(O(n^{2})\) περιγράφει έναν αλγόριθμο του οποίου η απόδοση αυξάνεται ανάλογα με το τετράγωνο του μεγέθους των δεδομένων που εισάγουμε. Κλασσικό παράδειγμα \(O(n^{2})\) είναι τα nested loops:

Ένας απλός τρόπος να υπολογίζουμε το Big O σε αυτές τις περιπτώσεις είναι να αυξάνουμε τον εκθέτη του \(n\) κατά 1 για κάθε for που έχουμε. Αν έχουμε 1 for, τότε έχουμε \(O(n)\) όπως είδαμε πριν, ή αλλιώς \(O(n^{1})\). Αν έχουμε 2 for (το ένα μέσα στο άλλο), τότε έχουμε \(O(n^{2})\). Με 3 for έχουμε \(O(n^{3})\) κ.ο.κ. Πλέον ο ρυθμός αύξησης σταμάτησε να είναι γραμμικός και όσο περισσότερα δεδομένα εισάγουμε, τόσο αυξάνεται και ο ρυθμός μεταβολής. Ας πούμε ότι εισάγουμε 10 δεδομένα και ότι ο αλγόριθμός μας θέλει 100 δευτερόλεπτα να τα επεξεργαστεί. Αν εισάγουμε άλλο ένα δεδομένο και τα κάνουμε 11, ο αλγόριθμός μας πλέον θέλει 121 δευτερόλεπτα να τα επεξεργαστεί (\(11^2)\), δηλαδή ο χρόνος αυξήθηκε κατά 21 δευτερόλεπτα ενώ τα δεδομένα αυξήθηκαν μόλις κατά 1. Αν βάλουμε 100 δεδομένα, ο χρόνος θα είναι /(100^2 = 10000/) δευτερόλεπτα και αν αυξήσουμε τα δεδομένα πάλι κατά 1 και τα κάνουμε 101, ο χρόνος γίνεται \(101^2 = 10201\). Βλέπουμε ότι ενώ και στις 2 περιπτώσεις αυξήσαμε τα δεδομένα κατά 1 επιπλέον στοιχείο, στην πρώτη περίπτωση η επίπτωση στον χρόνο ήταν 21 δευτερόλεπτα ενώ στην δεύτερη 201 δευτερόλεπτα. Αυτό συμβαίνει διότι όσο πιο δεξιά πάμε στην καμπύλη, τόσο πιο απότομη γίνεται με αποτέλεσμα ακόμα και οι μικρές μεταβολές στο μέγεθος των δεδομένων να έχουν τεράστιες επιπτώσεις στον χρόνο. Στο παρακάτω γράφημα βλέπουμε τις καμπύλες που σχηματίζουν οι συναρτήσεις \(f(x)=x^{2}\), \(g(x)=x^{3}\), \(h(x)=x^{4}\):

Εδώ πλέον πάμε σε τρελούς ρυθμούς μεταβολής. Κάθε νέο στοιχείο που εισάγουμε θα διπλασιάζει την μεταβολή μας και όπως καταλαβαίνεις, τα νούμερα θα ξεφύγουν πολύ εύκολα. Αν πίστευες ότι η καμπύλη του \(O(n^{2})\) ήταν αρκετά απότομη, δεν την τώρα πλάι-πλάι με την (μωβ) γραμμή του \(O(2^{n})\):

Στα δύο τελευταία παραδείγματα, είδαμε ότι όσο αυξάνονται τα δεδομένα που εισάγουμε, τόσο πιο απότομη γίνεται η καμπύλη μας. Υπάρχει όμως κι ένα είδος αλγόριθμων που όσο αυξάνονται τα δεδομένα που εισάγουμε, τόσο μικρότερη είναι η επίπτωση στον χρόνο (ή στον χώρο). Αυτοί οι αλγόριθμοι περιγράφονται από το \(O(log n)\).

Το πιο κλασσικό παράδειγμα λογαριθμικού αλγορίθμου είναι το binary search (δυαδική αναζήτηση) που είναι μια μέθοδος αναζήτησης sorted δεδομένων. Λειτουργεί επιλέγοντας το μεσαίο στοιχείο από το σύνολο των δεδομένων που του έχουμε δώσει και το συγκρίνει με την τιμή που αναζητάμε. Αν είναι αυτό που ψάχνουμε, τελειώνει η αναζήτηση (προφανώς!). Αν η τιμή που ψάχνουμε είναι μεγαλύτερη από την μεσαία τιμή, ο αλγόριθμος θα πάρει το άνω μισό των δεδομένων και θα ξεκινήσει από την αρχή. Αν η τιμή είναι μικρότερη από την μεσαία τιμή, τότε θα πάρει το κάτω μισό των δεδομένων. Θα συνεχίσει να κόβει στη μέση τα δεδομένα και να επιλέγει το μεσαίο στοιχείο μέχρι να βρει την τιμή που ψάχνουμε ή μέχρι να μην μπορεί να κόψει άλλο τα δεδομένα.

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

Αυτό μας δείχνει ότι αν, για παράδειγμα, χρειαζόμαστε 1 δευτερόλεπτο για να αναζητήσουμε κάτι μέσα σε ένα array 10 στοιχείων, θα χρειαστούμε μόλις 3 δευτερόλεπτα για να κάνουμε μια αναζήτηση σε ένα array 100 στοιχείων. Όσο αυξάνονται τα δεδομένα που εισάγουμε, τόσο μικραίνει ο ρυθμός αύξησης του χρόνου εκτέλεσης.

Αυτά ήταν τα πιο βασικά του Big O notation. Φυσικά υπάρχει πάρα πολύ θεωρία ακόμα αλλά στα πλαίσια του προγραμματισμού, αυτά είναι τα βασικά που θα πρέπει να γνωρίζουμε.