Aller au contenu

Algorithm — Complexité (O(1), O(n), O(log n))

La complexité est un concept fondamental pour comprendre la performance d’un programme, surtout quand on manipule beaucoup de données.

Idée simple

La complexité mesure :

le temps nécessaire pour exécuter une opération en fonction de la taille des données

⚡ Les 3 complexités essentielles

O(1) — Constant

Temps fixe, peu importe la taille

map.get(key);
  • Très rapide
  • Idéal pour les systèmes performants

O(n) — Linéaire

Temps proportionnel au nombre d’éléments

for (int i = 0; i < n; i++) {
    // traitement
}

Plus il y a de données, plus c’est lent

🔵 O(log n) — Logarithmique

Très efficace sur de grandes données

Exemple : recherche dichotomique (binary search)

public int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

À chaque étape :

  • on divise le problème par 2
  • donc très rapide même avec beaucoup de données

Exemples concrets

Structure Opération Complexité
HashMap get O(1)
Array boucle O(n)
Binary Search recherche O(log n)

Piège important

HashMap :

  • ✔️ O(1) en moyenne
  • ❌ peut devenir O(n) dans le pire cas

Intuition simple

  • O(1) → instant
  • O(log n) → très rapide
  • O(n) → peut devenir lent avec beaucoup de données

Questions classiques

Q1

Complexité moyenne d’un HashMap ? O(1)

Q2

Complexité d’une boucle ? O(n)

Q3

Complexité d’une binary search ? O(log n)

Q4

Le plus rapide ?

  • A. O(n)
  • B. O(log n)
  • C. O(1)

Réponse : C

À retenir

  • la complexité détermine la performance
  • O(1) est idéal
  • O(log n) est très efficace
  • O(n) peut devenir coûteux
  • toujours penser à l’impact avec de grandes données

🧾 En résumé

  • O(1) → temps constant
  • O(n) → dépend du volume
  • O(log n) → très performant

Bien choisir la complexité permet d’améliorer fortement les performances et la latence d’une application.

Voir aussi