Complexité algorithmique NSI : maîtriser le coût d'un algorithme

Tu as déjà écrit un programme qui fonctionne… mais qui met dix secondes à répondre ? En NSI, on ne se contente pas de vérifier qu'un algorithme marche : on veut aussi savoir s'il est efficace. C'est exactement le rôle de la complexité algorithmique, une notion centrale du programme de Première et de Terminale. Dans cet article, on t'explique simplement ce qu'est le coût d'un algorithme, comment on le mesure, et on te donne des astuces concrètes pour réussir les exercices et l'épreuve du bac.

Qu'est-ce que la complexité algorithmique ?

La complexité algorithmique mesure la quantité de ressources (temps de calcul, mémoire) qu'un algorithme consomme en fonction de la taille de ses données d'entrée. On note souvent cette taille n : par exemple, le nombre d'éléments d'une liste, la longueur d'une chaîne de caractères ou le nombre de sommets d'un graphe.

L'idée clé : on ne mesure pas le temps en secondes (car il dépend de la machine), mais on compte le nombre d'opérations élémentaires effectuées. Cela permet de comparer deux algorithmes indépendamment de l'ordinateur qui les exécute.

Complexité temporelle et complexité spatiale

• Complexité temporelle : combien d'opérations l'algorithme réalise-t-il en fonction de n ? C'est la plus étudiée en NSI.
• Complexité spatiale : combien de mémoire supplémentaire l'algorithme utilise-t-il ? Utile quand on travaille avec de gros volumes de données.

La notation grand O

On utilise la notation O(...) (lire « grand O de… ») pour décrire un ordre de grandeur. Par exemple :

• O(1) : temps constant, indépendant de n.
• O(n) : temps linéaire, proportionnel à n.
• O(n²) : temps quadratique, quand on utilise deux boucles imbriquées.
• O(log n) : temps logarithmique, typique de la recherche dichotomique.

Retiens que la notation O donne une tendance pour les grandes valeurs de n. On ignore les constantes multiplicatives : 3n + 5 reste O(n).

Comment calculer le coût d'un algorithme ?

Pour estimer la complexité d'un algorithme, on suit une méthode simple :

1. Identifier la taille de l'entrée n.
2. Repérer les boucles et compter combien de fois elles s'exécutent.
3. Additionner les opérations : une boucle simple donne O(n), deux boucles imbriquées donnent O(n²).

Exemple 1 : recherche linéaire

def recherche_lineaire(liste, cible):
    for element in liste:
        if element == cible:
            return True
    return False

Dans le pire des cas (la cible n'est pas dans la liste), on parcourt tous les éléments : la complexité est O(n).

Exemple 2 : deux boucles imbriquées

def somme_paires(liste):
    total = 0
    for i in range(len(liste)):
        for j in range(len(liste)):
            total += liste[i] * liste[j]
    return total

La boucle externe s'exécute n fois, et pour chaque tour, la boucle interne aussi n fois. Total : n × n = n² opérations, donc O(n²). Attention : dès que tu vois deux boucles imbriquées sur la même taille n, pense immédiatement à O(n²).

Exemple 3 : recherche dichotomique

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

À chaque tour, on divise l'intervalle de recherche par 2. Le nombre d'itérations est donc de l'ordre de log₂(n) : complexité O(log n). C'est bien plus rapide que O(n) pour de grandes listes. Cette fonction exige que la liste soit triée au préalable.

Cas d'usage concret : trier une liste

Le tri est un excellent terrain d'entraînement. Compare deux algorithmes classiques :

Tri par sélection

def tri_selection(liste):
    n = len(liste)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if liste[j] < liste[min_index]:
                min_index = j
        liste[i], liste[min_index] = liste[min_index], liste[i]
    return liste

Deux boucles imbriquées : complexité O(n²). Pour 1000 éléments, cela représente environ un million de comparaisons.

Tri par insertion

def tri_insertion(liste):
    for i in range(1, len(liste)):
        valeur = liste[i]
        j = i - 1
        while j >= 0 and liste[j] > valeur:
            liste[j + 1] = liste[j]
            j -= 1
        liste[j + 1] = valeur
    return liste

Dans le pire des cas (liste inversée), la complexité est aussi O(n²). En revanche, sur une liste déjà presque triée, il devient très rapide (proche de O(n)). C'est un bon exemple de cas où la complexité dépend des données.

Les algorithmes de tri efficaces comme le tri fusion ou le tri rapide atteignent O(n log n). Tu les rencontreras en Terminale. Pour t'entraîner, jette un œil à nos exercices NSI qui couvrent ces algorithmes.

Conseils de méthode et lien avec le bac NSI

La complexité algorithmique apparaît régulièrement dans les sujets du bac NSI, notamment en Terminale. Voici comment t'organiser :

1. Méthode pour analyser un algorithme

• Repère la variable n (taille de la structure).
• Compte les boucles : une boucle simple → O(n), deux imbriquées → O(n²), une boucle qui divise par 2 → O(log n).
• Ne te laisse pas piéger par les constantes : 2n + 10 reste O(n).
• Pense au pire des cas, c'est la convention en NSI.

2. Réviser efficacement

Consulte nos fiches de révision pour revoir les définitions clés : complexité, invariant de boucle, terminaison. Entraîne-toi aussi à coder les algorithmes vus en cours, car la mémorisation passe par la pratique. Nos cours NSI détaillent chaque notion du programme avec des exemples Python.

3. Erreurs fréquentes à éviter

• Confondre O(n) et O(n²) : vérifie toujours s'il y a des boucles imbriquées.
• Oublier que la recherche dichotomique nécessite une liste triée.
• Croire que O(log n) est plus lent que O(n) : c'est l'inverse !

Si tu veux approfondir certaines notions mathématiques (logarithmes, suites), le site Allolycee propose des ressources utiles pour consolider les bases. Et pour des exercices supplémentaires en sciences, jette un œil à Allobac.

Conclusion : la complexité, un superpouvoir

Maîtriser la complexité algorithmique, c'est apprendre à écrire des programmes qui ne se contentent pas de fonctionner, mais qui fonctionnent vite et efficacement, même sur de grandes données. C'est une compétence valorisée au bac et, plus tard, en informatique professionnelle. Retiens les trois ordres de grandeur essentiels : O(1), O(n), O(n²), et entraîne-toi à les repérer dans n'importe quel code. Avec un peu de pratique, tu verras que c'est un jeu d'enfant ! Alors, prêt à optimiser tes algorithmes ? 🚀