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

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

Οι πιο συνηθιστές τάξεις πολυπλοκότητας χρόνου:

• O(1): Σταθερός χρόνος. Ο χρόνος εκτέλεσης δεν εξαρτάται από το μέγεθος των εισερχόμενων δεδομένων.
• O(log n): Λογαριθμικός χρόνος. Ο χρόνος εκτέλεσης αυξάνεται αργά καθώς αυξάνεται το μέγεθος των εισερχόμενων δεδομένων (π.χ., δυαδική αναζήτηση).
• O(n): Γραμμικός χρόνος. Ο χρόνος εκτέλεσης είναι ανάλογος με το μέγεθος των εισερχόμενων δεδομένων (π.χ., γραμμική αναζήτηση).
• O(n log n): Γραμμικός-λογαριθμικός χρόνος. Συχνά συναντάται σε αποδολικούς αλγορίθμους ταξινόμησης (π.χ., γρήγορη ταξινόμηση, ταξινόμηση συγχώνευσης).
• O(n^2): Τετραγωνικός χρόνος. Ο χρόνος εκτέλεσης αυξάνεται ανάλογα με το τετράγωνο του μεγέθους των εισερχόμενων δεδομένων (π.χ., ταξινόμηση φυσαλίδας, επιλογής).
• O(2^n): Εκθετικός χρόνος. Ο χρόνος εκτέλεσης αυξάνεται πολύ γρήγορα με το μέγεθος των εισερχόμενων δεδομένων. Συχνά σε προβλήματα πλήρους αναζήτησης.

Παραδείγματα κώδικα και η πολυπλοκότητά τους:

// O(1)
int πρώτοΣτοιχείο = array[0];

// O(n)
for (int i = 0; i < array.length; i++) {
    // κάποια λειτουργία
}

// O(n^2)
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        // κάποια λειτουργία
    }
}

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

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