💻 Programmation🟡 Intermédiaire⏱ 1 min de lecture📂 🔢 Fondamentaux

💻 Programmation · Fondamentaux

Complexité algorithmique (Big O)

La notation Big O décrit comment le temps (ou la mémoire) d'un algorithme grandit avec la taille n des données, en ignorant les constantes.

Schéma
O(1)        constant       accès par index
O(log n)    logarithmique  recherche dichotomique
O(n)        linéaire       parcourir une liste
O(n log n)  quasi-linéaire  tri efficace
O(n²)       quadratique    deux boucles imbriquées
O(2ⁿ)       exponentielle  tester tous les sous-ensembles

Comment le lire

Si les données doublent : O(n) double le temps, O(n²) le quadruple, O(log n) ajoute une seule étape.

Exemple concret

Chercher un nom dans une liste non triée d'un million d'éléments : jusqu'à 1 000 000 de comparaisons (O(n)). Dans une liste triée, la recherche dichotomique en demande environ 20 (log₂ de 1 000 000).

Pourquoi c'est important

Un algorithme en O(n²) passe sans problème sur 100 éléments et devient inutilisable sur 1 000 000.

Pire cas

Big O décrit en général le pire cas (le comportement quand n devient grand). Il existe aussi une complexité en mémoire.

📌 À retenir

Une boucle ≈ n. Deux boucles imbriquées ≈ n². On divise par 2 à chaque étape ≈ log n.

Teste-toi

Quelle est la complexité d'une recherche dichotomique dans une liste triée ?
  1. O(1)
  2. O(log n)
  3. O(n)
  4. O(n²)

Réponse : B. O(log n)

On divise la zone de recherche par deux à chaque étape : environ 20 étapes pour un million d'éléments.

Plus de questions dans Discord avec /qcm matiere:dev.

Pour aller plus loin

Tableaux, objets, piles et filesUne structure de données organise l'information pour y accéder efficacement. Le bon choix peut changer la vitesse d'un…La récursivitéUne fonction récursive s'appelle elle-même sur un problème plus petit, jusqu'à atteindre un cas de base.

Fiche mise à jour le 6 novembre 2026. Une erreur, une précision à proposer ? Écris-nous.