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

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

Για παράδειγμα, αν ένας αλγόριθμος έχει πολυπλοκότητα O(n), αυτό σημαίνει ότι ο χρόνος εκτέλεσης αυξάνεται γραμμικά με το μέγεθος της εισόδου. Αν είναι O(n²), αυξάνεται ανάλογα με το τετράγωνο του μεγέθους της εισόδου.

Παράδειγμα σε Go:

func sum(arr []int) int {
    total := 0
    for _, v := range arr {
        total += v
    }
    return total
}

Η συνάρτηση sum έχει πολυπλοκότητα O(n), καθώς διασχίζει όλα τα στοιχεία του πίνακα μία φορά.