Notation Big-O : complexité temporelle

Optimiser le code en Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Qu'est-ce que la complexité temporelle ?

Complexité temporelle : mesure la croissance du temps d'exécution avec la taille d'entrée
Aide à répondre : « Que se passe-t-il si mes données sont 10× plus grosses ? »
Ne vise pas le temps absolu

Notation Big-O

Notation mathématique décrivant le pire cas.

Quelques classes courantes :

O(1) : Temps constant — indépendant de la taille

Comprendre O(1)

Exemple d'une opération O(1) : get() de ArrayList

Implémentation interne (simplifiée) d'un ArrayList de Strings :

public class ArrayList {}
    private String[] data; // Internal array
    private int size;

    // Get operation - direct array access
    public String get(int index) {
        return data[index]; // O(1)
    }
}

Notation Big-O

Notation mathématique décrivant le pire cas

Quelques classes courantes :

O(1) : Temps constant — indépendant de la taille
O(n) : Temps linéaire — croît avec la taille d'entrée

Comprendre O(n)

Exemple semblable, pour contains() de ArrayList

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // Linear search through array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Not found
}

Notation Big-O

Notation mathématique décrivant le pire cas

Quelques classes courantes :

O(1) : Temps constant — indépendant de la taille
O(n) : Temps linéaire — croît avec la taille d'entrée
O(n²) : Temps quadratique — croît au carré avec la taille d'entrée

Exemple pratique à complexité quadratique

// Trouver une paire de nombres dont la somme vaut une cible
// Complexité temporelle : O(n²)

public int[] findPairWithSum(ArrayList<Integer> numbers, int targetSum) {
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers.get(i) + numbers.get(j) == targetSum) {
                console.log("Found them!")
            }
        }
    }
}

Pourquoi la complexité temporelle compte

Effet de la taille d'entrée :

O(1) : 1 000 -> 1 000 000 éléments = Même temps !
O(n) : 1 000 -> 1 000 000 éléments = 1 000× plus lent
O(n²) : 1 000 -> 1 000 000 éléments = 1 000 000× plus lent

Capture d'écran du 2025-05-10 à 14 h 27 min 06 s.png

Passons à la pratique !

Optimiser le code en Java