Complexité

La complexité algorithmique mesure les ressources (principalement le temps de calcul et l'espace mémoire) nécessaires à l'exécution d'un algorithme en fonction de la taille de ses données d'entrée (notée souvent $n$).

• Complexité en Temps (ou Temporelle): Elle évalue le nombre d'opérations élémentaires (comme les comparaisons, les additions, les affectations, etc.) effectuées par l'algorithme.
• Complexité en Espace (ou Spatiale): Elle évalue la quantité de mémoire utilisée (nombre de variables, de structures de données) par l'algorithme.

L'objectif est d'exprimer cette relation à l'aide de notations asymptotiques (telles que la notation Grand $O$, ou $O(f(n)))$ pour décrire le comportement de l'algorithme lorsque la taille des données d'entrée $n$ devient très grande.

Objectifs:

• Estimer le coût sans exécuter l’algorithme
• Classer les problèmes selon leur difficulté/efficacité
• Comparer les algorithmes résolvant un problème

Notations

$n$ = taille des données

$T(n)$ = nombre d’opérations élémentaires

Exemple 1: recherche d’une valeur dans un tableau (Recherche Séquentielle)

Cet algorithme consiste à parcourir le tableau élément par élément du début à la fin pour trouver une valeur x.

• Algorithme : On parcourt les cases de $0$ à $n−1$. Si la case contient x, on s'arrête.

• Analyse du pire des cas : Le "pire des cas" se produit si la valeur x n'est pas présente dans le tableau ou si elle se trouve à la toute dernière position.

• Calcul de $T(n$) : Dans ce scénario, l'algorithme doit effectuer une comparaison pour chaque élément du tableau.

  • Nombre de comparaisons = $n$.

• Complexité Asymptotique : Comme le temps d'exécution croît linéairement avec la taille du tableau, la complexité est linéaire.

  $$ O(n) $$

<aside> 💡

On calculera en utilisant le pire des cas pour être sûr que l’algorithme ne durera jamais plus longtemps que prévu.

</aside>

Exemple 2: Test de primalité (Naïf amélioré)