Notation Big-O : complexité temporelle

Optimiser son 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 grandes ? »
Ne s'intéresse pas au 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 en O(1) : get() de ArrayList

Implémentation interne (simplifiée) d'un ArrayList stockant des 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 similaire, 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é de la taille d'entrée

Exemple pratique à complexité quadratique

// Finding a pair of numbers that sum to a target value
// Time complexity: 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

Impact 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 10/05/2025 à 14:27:06.png

Passons à la pratique !

Optimiser son code en Java