Notion de complexité algorithmique : nombre d'opérations et comparaison des tris

En 30 secondes

• La complexité algorithmique estime le nombre d'opérations d'un algorithme selon la taille n des données, indépendamment de la machine.
• Linéaire (proportionnel à n) : le parcours d'un tableau ; la taille double, les opérations doublent.
• Quadratique (proportionnel à n multiplié par n) : les tris simples ; la taille double, les opérations sont multipliées par 4.

Ce que tu sauras faire

• Comprendre que la complexité algorithmique estime le nombre d'opérations d'un algorithme en fonction de la taille des données.
• Distinguer une complexité linéaire d'une complexité quadratique et savoir laquelle croît le plus vite.
• Comparer le coût du parcours simple d'un tableau et celui d'un tri simple sur ce tableau.

Les mots à connaître

Tableau

une structure de données qui stocke une suite de valeurs, chacune repérée par son indice (sa position).

Taille des données

le nombre d'éléments à traiter, souvent noté n ; par exemple le nombre de cases d'un tableau.

Opération élémentaire

une action simple comptée dans un algorithme, comme une comparaison entre deux valeurs ou un échange de deux cases.

Le piège classique

Confondre complexité linéaire (proportionnelle à n) et complexité quadratique (proportionnelle à n multiplié par n) : la seconde croît beaucoup plus vite.

L'astuce

Complexité = nombre d'OPÉRATIONS selon la taille n, pas un temps en secondes (qui dépend de la machine).