Introduction à la complexité algorithmique
La complexité en informatique est une mesure qui permet d’évaluer les ressources nécessaires pour exécuter un algorithme. Elle peut être utilisée pour estimer le temps d’exécution et la mémoire utilisée par un algorithme en fonction de la taille de ses données d’entrée. En général, nous cherchons à minimiser la complexité des algorithmes pour qu’ils soient aussi efficaces que possible.
La complexité est un outil important pour les informaticiens, car elle leur permet de choisir les algorithmes les plus adaptés à leurs besoins et de les optimiser pour obtenir de meilleures performances.
La complexité d’un algorithme est une mesure qui permet d’évaluer les ressources nécessaires pour exécuter cet algorithme. Il existe deux types principaux de complexité :
Définition : La complexité temporelle
Elle mesure le temps d’exécution d’un algorithme. Plus précisément, elle est souvent utilisée pour estimer le nombre d’opérations élémentaires (comme les additions, les multiplications, les comparaisons, etc.) qu’un algorithme effectue en fonction de la taille de ses données d’entrée.
Définition : La complexité spatiale
Elle mesure la quantité de mémoire utilisée par un algorithme pendant son exécution. Elle est généralement exprimée en fonction de la taille des données d’entrée.
Nous ne la détaillerons pas dans ce cours.
Remarque : Variations
Il est important de noter que la complexité d’un algorithme peut varier en fonction des données d’entrée. Par exemple, un algorithme de tri peut avoir une complexité temporelle différente si les données d’entrée sont déjà triées ou si elles sont dans l’ordre inverse.
Définition : Temps d'exécution
Le temps d’exécution d’un algorithme est le temps qu’il faut pour exécuter toutes les instructions de l’algorithme sur un ordinateur. Ce temps dépend de nombreux facteurs, tels que la vitesse du processeur, la taille des données en entrée, et la nature des opérations effectuées par l’algorithme.
Définition : Espace mémoire
L’espace mémoire utilisé par un algorithme est la quantité de mémoire nécessaire pour stocker les données utilisées par l’algorithme pendant son exécution. Comme pour le temps d’exécution, l’espace mémoire dépend de nombreux facteurs, tels que la taille des données en entrée et la nature des opérations effectuées par l’algorithme.
En général, nous cherchons à minimiser le temps d’exécution et l’espace mémoire utilisés par un algorithme pour qu’il soit aussi efficace que possible. Cependant, il peut y avoir un compromis entre ces deux mesures. Par exemple, un algorithme peut être plus rapide (avoir une faible complexité temporelle) mais utiliser plus de mémoire (avoir une grande complexité spatiale), ou vice versa.
Exemple : Analyse de complexité d’un algorithme simple
Prenons l’exemple d’un algorithme simple : la recherche linéaire. C’est un algorithme qui parcourt un tableau pour trouver un élément spécifique.
def recherche_lineaire(tableau, element):
"""Recherche un élément dans un tableau et renvoie l'indice de la première occurence"""for i in range(len(tableau)):
if tableau[i] == element:
return i
return -1
Dans cet algorithme, le nombre exact d’opérations effectuées dépend des données d’entrée. Si l’élément recherché se trouve au début du tableau, l’algorithme s’arrêtera après avoir effectué une seule opération de comparaison. Si l’élément recherché se trouve à la fin du tableau, l’algorithme effectuera n opérations de comparaison, où n est la taille du tableau. Dans le pire des cas, si l’élément recherché n’est pas dans le tableau, l’algorithme effectuera également n opérations de comparaison.
En général, nous ne pouvons pas connaître à l’avance la position de l’élément recherché dans le tableau. Par conséquent, nous utilisons souvent la complexité dans le pire des cas pour évaluer la performance d’un algorithme. Dans le cas de l’algorithme de recherche linéaire, la complexité dans le pire des cas est de n opérations de comparaison.
On dit donc que le nombre d’opérations effectuées par l’algorithme est proportionnel à n. Cela signifie que plus le tableau est grand, plus l’algorithme prendra de temps pour s’exécuter.