Qu'est-ce que la notation O (notation Big O) ?

La notation O (notation Big O) est une méthode pour décrire l’évaluation asymptotique de la complexité d’un algorithme, c’est-à-dire comment le temps d’exécution ou l’utilisation de la mémoire augmente avec la taille des données d’entrée.

Par exemple, si un algorithme a une complexité O(n), cela signifie que le temps d’exécution augmente linéairement avec la taille de l’entrée. Si c’est O(n²), le temps augmente proportionnellement au carré de la taille de l’entrée.

Exemple en Go:

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

La fonction sum a une complexité O(n), car elle parcourt tous les éléments du tableau une fois.