Complexité algorithmique NSI : les pièges à éviter

Tu as déjà écrit un programme qui marche… mais qui met trois secondes à répondre sur une petite liste et qui devient inutilisable dès qu'on lui donne un million d'éléments ? Bienvenue dans le monde de la complexité algorithmique ! En NSI, ce n'est pas juste une notion abstraite : c'est un critère d'évaluation central au bac, et surtout un réflexe de programmeur. Dans cet article, on te montre les pièges classiques que les élèves rencontrent, comment les éviter, et comment rédiger une réponse propre le jour de l'épreuve.

1. Comprendre la complexité algorithmique (et son coût)

La complexité algorithmique mesure les ressources consommées par un algorithme en fonction de la taille des données d'entrée, notée n. On distingue deux grandes familles :

• La complexité temporelle : combien d'opérations élémentaires l'algorithme effectue-t-il ?
• La complexité spatiale : combien de mémoire supplémentaire utilise-t-il ?

Quand on parle du coût d'un algorithme, on ne compte pas en secondes (ça dépend de la machine !), mais en nombre d'opérations. C'est pour ça qu'on utilise la notation grand O : O(n), O(n²), O(log n)… Elle décrit l'ordre de grandeur du coût quand n devient grand.

Les ordres de grandeur à connaître

• O(1) : coût constant, comme accéder à tab[i].
• O(log n) : coût logarithmique, comme la recherche dichotomique.
• O(n) : coût linéaire, comme parcourir une liste une fois.
• O(n log n) : coût quasi-linéaire, comme le tri fusion ou le tri par tas.
• O(n²) : coût quadratique, comme deux boucles imbriquées sur n.
• O(2^n) : coût exponentiel, à éviter dès que n > 30.

Retiens bien cette hiérarchie : O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n). Elle te servira à comparer deux algorithmes sans les exécuter.

2. Les pièges classiques à éviter

Piège n°1 : confondre complexité et temps d'exécution réel

Beaucoup d'élèves écrivent « cet algorithme est rapide car mon PC met 0,1 s ». Faux ! Le temps réel dépend du processeur, du langage, de la version de Python… La complexité, elle, est indépendante de la machine. On compare des courbes, pas des chronomètres.

Piège n°2 : oublier de préciser « dans le pire cas »

Quand on te demande la complexité, précise toujours le cas considéré : meilleur cas, cas moyen ou pire cas. Par exemple, la recherche dans une liste non triée est O(1) au meilleur cas (l'élément est en première position) mais O(n) au pire. Au bac, le pire cas est souvent attendu par défaut.

Piège n°3 : mal compter les boucles imbriquées

Deux boucles for imbriquées ne font pas forcément O(n²). Si la boucle interne dépend de la boucle externe, il faut calculer précisément. Exemple :

def mystere(n):
    total = 0
    for i in range(n):
        for j in range(i):
            total += 1
    return total

Ici, la boucle interne fait i tours, donc le total est 0 + 1 + 2 + … + (n-1) = n(n-1)/2, soit O(n²). Mais si la boucle interne allait jusqu'à n, ce serait aussi O(n²)… avec un facteur 2 en plus. Le grand O ne garde que l'ordre de grandeur.

Piège n°4 : négliger la complexité spatiale

Un algorithme peut être rapide mais manger toute la mémoire. Par exemple, une fonction récursive qui crée une nouvelle liste à chaque appel peut exploser la pile d'appels. Pense toujours à deux questions : combien de temps, mais aussi combien de mémoire ?

Piège n°5 : croire que le tri intégré de Python est « magique »

sorted() et list.sort() utilisent l'algorithme Timsort, de complexité O(n log n) dans le pire cas. Ce n'est pas O(n) ! Si tu tries une liste à chaque tour d'une boucle O(n), tu obtiens O(n² log n), ce qui est souvent une erreur de conception.

3. Exemple concret : recherche linéaire vs recherche dichotomique

Prenons un cas classique du programme NSI : chercher une valeur dans une liste triée. Voici les deux approches, en Python.

Recherche linéaire — O(n)

def recherche_lineaire(tab, x):
    for i in range(len(tab)):
        if tab[i] == x:
            return i
    return -1

# Coût : on parcourt au pire toute la liste
# -> O(n)

Recherche dichotomique — O(log n)

def recherche_dichotomique(tab, x):
    debut = 0
    fin = len(tab) - 1
    while debut <= fin:
        milieu = (debut + fin) // 2
        if tab[milieu] == x:
            return milieu
        elif tab[milieu] < x:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return -1

# À chaque tour, on divise l'espace de recherche par 2
# -> O(log n)

Compare : pour n = 1 000 000, la recherche linéaire fait jusqu'à 1 000 000 de comparaisons, la dichotomique seulement 20 ! C'est ça, la puissance de O(log n). Attention : la dichotomie exige une liste triée, sinon elle renvoie n'importe quoi.

Le piège du tri préalable

Si ta liste n'est pas triée, tu dois d'abord la trier en O(n log n), puis faire la dichotomie en O(log n). Le coût total est O(n log n). Si tu ne fais qu'une seule recherche, la recherche linéaire O(n) est plus efficace ! En revanche, pour beaucoup de recherches, trier d'abord devient rentable. C'est exactement le genre de raisonnement attendu au bac.

4. Mise en pratique : repérer une complexité dans un vrai sujet

Imaginons un exercice type : on te donne une liste de notes d'élèves et on te demande de trouver la note maximale, puis de compter combien d'élèves ont cette note.

def statistiques(notes):
    maximum = notes[0]
    for note in notes:          # O(n)
        if note > maximum:
            maximum = note
    compteur = 0
    for note in notes:          # O(n)
        if note == maximum:
            compteur += 1
    return maximum, compteur

# Complexité totale : O(n) + O(n) = O(n)

Ici, on a deux boucles séquentielles, pas imbriquées : on additionne les coûts, on ne les multiplie pas. O(n) + O(n) = O(2n) = O(n). C'est une erreur fréquente de croire qu'on obtient O(n²).

Autre cas : trier une liste de résultats, puis afficher les 10 premiers. Le tri coûte O(n log n), l'affichage O(1) (ou O(10) = O(1)). Donc la fonction complète est O(n log n). Au bac, on attend que tu identifies l'étape dominante : c'est elle qui fixe la complexité globale.

5. Méthode et révision : réussir l'épreuve du bac NSI

Voici une méthode en 5 étapes pour ne plus te tromper :

1. Identifie les entrées et note leur taille n.
2. Repère les boucles : combien de tours font-elles ? Sont-elles imbriquées ou séquentielles ?
3. Compte le coût dominant : additionne les blocs séquentiels, multiplie les blocs imbriqués.
4. Garde l'ordre de grandeur : supprime les constantes et les termes négligeables.
5. Précise le cas : meilleur, moyen ou pire. Justifie en une phrase.

Pour t'entraîner, va voir les exercices NSI et les fiches de révision du site : tu y trouveras des sujets corrigés qui te feront gagner du temps. Le cours complet reprend aussi les notions de bases et les algorithmes classiques à connaître.

Si tu veux aller plus loin, pense aussi à consulter des ressources complémentaires sur Allolycée et Allobac pour varier les supports et croiser les explications.

Les phrases à ne plus écrire

• ❌ « L'algorithme est rapide. » → ✅ « L'algorithme est en O(n log n) dans le pire cas. »
• ❌ « Il y a deux boucles donc c'est O(n²). » → ✅ « Les deux boucles sont séquentielles, donc le coût est O(n). »
• ❌ « La complexité est de 5n + 3. » → ✅ « La complexité est O(n) : on néglige les constantes. »

6. Conclusion : la complexité, un super-pouvoir

La complexité algorithmique, ce n'est pas un chapitre à mémoriser puis à oublier : c'est un réflexe de programmeur. Savoir évaluer le coût d'un algorithme te permet de choisir la bonne structure de données, d'éviter les programmes qui plantent sur de gros volumes, et surtout de briller à l'épreuve du bac NSI. Alors entraîne-toi, compare, justifie, et n'oublie jamais : on ne compte pas en secondes, on compte en opérations. Tu as maintenant toutes les clés pour éviter les pièges. À toi de jouer ! 🚀