Terminale · Numérique et sciences informatiques

Utiliser la complexité pour comparer et choisir un algorithme

Estimer à partir du code puis d'une trace d'exécution le nombre d'opérations d'un algorithme, en déduire sa complexité (constante, logarithmique, linéaire, quadratique) et choisir l'algorithme adapté à un problème donné.

Aperçu gratuit
Illustration de la fiche « Utiliser la complexité pour comparer et choisir un algorithme »

Les points essentiels

  • La complexité en temps mesure le nombre d'opérations élémentaires (comparaisons, affectations, accès) en fonction de la taille n des données, et non une durée en secondes qui dépend de la machine.
  • On lit la complexité dans le code : une boucle for de n tours donne un coût linéaire, deux boucles imbriquées de n tours donnent un coût quadratique, une boucle dont la variable est divisée par 2 à chaque tour donne un coût logarithmique.

Les mots à connaître

Complexité en temps
Fonction qui associe à la taille n d'une entrée le nombre d'opérations élémentaires effectuées par l'algorithme dans le pire cas, exprimée par son ordre de grandeur.
Notation O (grand O)
O(f(n)) indique que le nombre d'opérations est borné, à une constante multiplicative près et pour n grand, par f(n). Ainsi 3n + 5 est en O(n).

Un exemple pour comprendre

Soit la fonction : def somme_paires(t): total = 0 ; for i in range(len(t)): for j in range(len(t)): if t[i] + t[j] == 10: total += 1 ; return total. Pour une liste de n éléments, combien de fois le test t[i] + t[j] == 10 est-il évalué ? Quelle est la complexité ?

La boucle sur i fait n tours et, pour chacun, la boucle sur j fait n tours. Le test est donc évalué n × n = n² fois, par exemple 16 fois pour n = 4 et 64 fois pour n = 8. Les autres opérations (initialisation, return) sont en nombre constant. Quand n double, le coût est multiplié par 4. La complexité est donc quadratique, en O(n²).

Première page de l’Essentiel : Utiliser la complexité pour comparer et choisir un algorithme
Ketty