La complexité d'un algorithme

Updated 990 Days AgoPublic

Actions

Le coût d'un algorithme

Il existe de nombreuses façons de représenter un ensemble de donnée. L'algorithme le plus approprié pour effectuer une recherche dépend de la façon dont les données sont rangées. Le bon algorithme permet d'effectuer une recherche la moins couteuse possilbe. C’est-à-dire que s'il est parfois possible de trouver plus rapidement la donnée. La capacité des ordinateurs étant limités, c'est pourquoi on préféra toujours réfléchir deux fois à la meilleure méthode pour trouver l'information.

Le coût d'exécution d'un algorithme est la plupart du temps évalué au pire des cas. Ce coût n'a pas besoin d'être précis, on préféra généralement utiliser un ordre de grandeur pour comparer des algorithmes. Pour y parvenir, on compte le nombre de fois qu'une boucle va se répéter. Par exemple, l'algorithme suivant possède un ordre de grandeur de N opération, noté: $O(n)$. Celà signifie que le coût de l'algorithme est proportionnel aux nombres d'éléments qu'on lui fournira en entrée. Ainsi, plus un algorithme est complexe, plus sa notation $O$ sera importante.

FONCTION FACTORIEL_MULT(N: ENTIER)
VARIABLE r: ENTIER
r <- 1

POUR i DE 1 À N+1:
    r <- r * i
FIN POUR

RETOURNER r
FIN FONCTION

Si l'on souhaite effectuer ce même algorithme, mais en transformant la multiplication en une suite d'addition (3x9 = 9+9+9). On obtient le résultat ci-dessous. On constate que la complexité de cette version est beaucoup plus importante en raison de ces deux boucles imbriquées. Plus précisément, la complexité de cet algorithme correspond à $\frac{n*(n+1)}{2}$. Pour indiquer l'ordre de grandeur, il faut simplifier en retirant toutes les constantes, c’est-à-dire $O(n^{2})$. On dit alors que la complexité est quadratique, celà signifie que le coût de l'algorithme augmente en fonction du nombre d'éléments qu'on lui fournira en entrée.

FONCTION FACTORIEL_ADD(N: ENTIER)
VARIABLE r, t: ENTIER
r <- 1

POUR i DE 1 À N+1:
    t <- 0
    POUR j DE 0 À i:
        t <- t + r
    FIN POUR
    r <- t
FIN POUR

RETOURNER r
FIN FONCTION

Exercices