Page MenuHomePhabricator

La complexité d'un algorithme
Updated 36 Days AgoPublic

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)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 OO 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 à n(n+1)2\frac{n*(n+1)}{2}. Pour indiquer l'ordre de grandeur, il faut simplifier en retirant toutes les constantes, c’est-à-dire O(n2)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

Dans ce cours, il vous sera demandé régulièrement d'évaluer la complexité d'un algorithme que vous venez d'écrire. L'objectif est de vous sensibiliser au choix du meilleur algorithme dans un contexte donné.
Last Author
Steve
Last Edited
Sep 13 2020, 11:10 AM

Event Timeline

Steve edited the content of this document. (Show Details)Sep 13 2020, 10:32 AM
Steve edited the content of this document. (Show Details)Sep 13 2020, 10:39 AM
Steve edited the content of this document. (Show Details)Sep 13 2020, 11:10 AM