Complexité de temps

La notation O (ou Big-O) est un outil mathématique utilisé en informatique pour décrire la complexité de temps d'un algorithme. Elle permet d'exprimer comment le temps d'exécution d'un algorithme croît en fonction de la taille de l'entrée (n).

Pourquoi utiliser la notation O ?

• Comparer l'efficacité des algorithmes.
• Estimer la scalabilité d'un programme.
• Identifier les goulots d'étranglement en performance.

Types essentiels de complexité

1. O(1) – Temps constant

L'algorithme s'exécute en un temps fixe, peu importe la taille de l'entrée.

Exemple : Accès à un élément d'un tableau

int getElement(int[] arr, int index) {
    return arr[index];  // O(1)
}

Même si arr contient 1 million d'éléments, cette opération prend toujours le même temps.

2. O(log n) – Logarithmique

L'algorithme réduit la taille du problème à chaque étape, souvent en le divisant par 2.

Exemple : Diviser par 2 jusqu'à atteindre 1

int compter(int n) {
    int count = 0;
    while (n > 1) {
        n = n / 2;  // On divise par 2 à chaque tour
        count++;
    }
    return count;  // O(log n)
}

Si n = 1000, la boucle s'exécute environ 10 fois au lieu de 1000 !

3. O(n) – Linéaire

Le temps d'exécution augmente proportionnellement à la taille de l'entrée.

Exemple : Parcourir un tableau

void printAll(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);  // O(n)
    }
}

Si n = 1000, on effectue exactement 1000 opérations.

4. O(n²) – Quadratique

Le temps d'exécution grandit au carré par rapport à n. Souvent causé par deux boucles imbriquées.

Exemple : Afficher toutes les paires possibles

void afficherPaires(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + ", " + arr[j]);  // O(n²)
        }
    }
}

Si n = 1000, on effectue 1,000,000 opérations !

Récapitulatif

Notation	Nom	Exemple	Taille max réaliste (n)
O(1)	Constant	Accès à un tableau	∞
O(log n)	Logarithmique	Diviser par 2 en boucle	1 milliard
O(n)	Linéaire	Parcourir une liste	10-100 millions
O(n²)	Quadratique	Deux boucles imbriquées	~10,000

Conclusion

• O(1) est idéal — c'est pourquoi HashSet et HashMap visent cette complexité.
• O(n²) est à éviter dès que les données grossissent.
• Plus la notation est petite, plus l'algorithme est efficace.