Complexité algorithmique

De WikiMéca
Sauter à la navigation Sauter à la recherche

Etudier la complexité d'un algorithme permet de l'optimiser afin qu'il utilise le moins de temps et le moins d'espace mémoire possible.

Complexité en temps

La complexité algorithmique en temps représente la "rapidité" d'un algorithmique à résoudre un problème. C'est une notion relative car elle permet de comparer les rapidités de deux algorithmique résolvant le même problème mais pas de donner un temps de exécution précis, celui-ci dépendant de la machine sur lequel le programme est exécuté.

Dans un but de simplification nous considérerons toute opération élémentaires (test, affectation, opération arithmétique) comme étant de coût constant.

Complexité en mémoire

Lors de l’exécution du programme, des données sont stockées. La complexité en mémoire mesure l’espace occupé pendant l’exécution. Par exemple, si le programme nécessite le stockage de données dans un tableau N×N, la complexité en mémoire est de .

Notation "Omicron" ou "grand O"

La notation "grand O" ou "Omicron" de Landau dénote le caractère dominé d'une fonction par rapport à une autre.

Soient et deux fonctions de la variable réelle . On dit que est dominée par en , ou que domine en , et on note :

lorsqu'il existe des constantes et telles que

Intuitivement, cela signifie que ne croît pas plus vite que .

Ordres de grandeur

Les ordres de grandeur utilisés pour comparer la complexité des algorithmes sont les suivants. Le temps de calcul est estimé pour 10-9 s par opération.

Ordre de grandeur Temps de calcul estimé pour

N=1000

Exemple d'algorithme
Constant

10-8 s accès liste, affectation
logarithmique

3.10-8 s dichotomie
linéaire

10-5 s parcours de liste
linéarithmique

3.10-5 s tri fusion, tri sélection
quadratique

10-2 s tri par insertion
cubique

10 s produit matriciel naïf
exponentiel

ou

trop long pour être exploitable

problème du voyageur de commerce
Représentation graphique

Ordre de grandeur nb opérations.svg


Remarques :

  • Dans le cas d’une complexité logarithme, l’exécution est quasiment instantannée.
  • Dans le cas d’une complexité linéaire, le temps d’exécution ne dépasse 1mn que pour des données de taille comparable à celle des mémoires vives. Le problème de complexité en mémoire se posera donc en priorité.
  • Dans le cas d’une complexité quadratique, la taille de N ne devra pas dépasser 106 environ.
  • Un algorithme de complexité exponentielle n’est praticable que pour des petites données : N< 50.

Complexité dans le meilleur/le pire des cas

Les paramètres d'entrée étant inconnus au préalable, leur taille change souvent le temps d’exécution de l'algorithme, mais aussi leur configuration. On distingue souvent la complexité dans le pire des cas, correspondant au nombre maximum d'opération nécessaire à la terminaison de l'algorithme, de la complexité dans le meilleur des cas, correspondant au nombre minimum d'opération nécessaire à la terminaison de l'algorithme. On parle aussi quelques fois de la complexité dans le cas moyen, mais son ordre de grandeur est souvent égale au pire des cas.

Dans une logique de conception de programme, en tenant compte de l'expérience utilisateur, la complexité la plus souvent utilisée est la complexité dans le pire des cas.

Exemples - algorithmes de recherche

Considérons deux algorithmes de recherche dans une liste de longueur n. L'un de recherche séquentielle, l'autre de recherche dichotomique.

Algorithme de recherche séquentielle

1 def cherche(x, liste):
2     for y in liste:
3     if y == x:
4         return True
5     return False

L'algorithme parcours la liste élément par élément depuis le début ( for y in liste: ) et, dans le cas ou il rencontre l'élément recherché ( if y == x: ) il renvoie True et renvoie False si il a parcouru la liste en entier et n'a pas trouvé de correspondance.

L’algorithme de recherche séquentielle effectue dans le meilleur des cas une seule comparaison (lorsque le premier élément testé est l’élément recherché) et dans le pire des cas n comparaisons (par exemple lorsque l’élément recherché ne se trouve pas dans la liste). On dira que le coût dans le meilleur des cas est constant et linéaire (proportionnel au nombre d'éléments de la liste) dans le pire des cas. Dans tous les cas la complexité est donc un .

Algorithme de recherche dichotomique

L'algorithme de recherche dichotomique nécessite que la liste soit triée au préalable.

 1 def cherche_dicho(x, liste):
 2     i, j = 0, len (liste)
 3     while i < j:
 4         k = (i + j) // 2
 5         if liste[k] == x:
 6             return True
 7         elif liste[k] > x:
 8             j = k
 9         else :
10             i = k + 1
11     return False

L’algorithme de recherche dichotomique compare la valeur recherchée avec l'élément en milieu de liste. Si celui-ci est égale à la valeur recherchée ( if liste[k] == x ) il renvoie True et termine le programme. C'est le meilleur des cas. Il n'aura effectué lui aussi une seule comparaison. Sinon, il compare la valeur recherchée à l'élément en milieu de liste (elif liste[k] > x: et else :) et continue la recherche soit dans la première moitié (j = k), soit dans la seconde (i = k + 1).

La complexité dans le pire des cas sera donc telle que la liste aura été coupée en deux jusqu'au dernier cas ou i=j, c'est à dire que la boucle s'est executée n fois tel que ou N est le nombre d'éléments de la liste.

En calculant n :

La complexité est donc un .


Autres pages de la catégorie "Informatique"

Pages relatives à l'informatique en CPGE scientifiques.

Bases du langage Python

Algorithmes et méthodes numériques‎