Complexité en temps

Soit un problème P et M une méthode pour résoudre ce problème. L’algorithme est une description avec des structures de contrôle et de données permettant d’écrire la méthode M dans un langage reconnaissable par tout individu ou machine.
Pour rappel, les structures de contrôle sont : une séquence, un embranchement (ou sélection), une boucle (ou itération). Les structures de données sont : des constantes, des variables, des tableaux (ou espace de stockage ordonné), des structures récursives (listes, graphes etc).

Opération élémentaire

La complexité consiste à évaluer l’efficacité de la méthode M et de comparer cette dernière avec une autre méthode M’. Cette comparaison est indépendante de l’environnement (machine, système, compilateur, langage, etc). L’efficacité dépend du nombre d’opérations élémentaires. Ces dernières dépendent de la taille des données et de la nature des données.

Notons n la taille des données et T(n) le nombre d’opérations élémentaires. L’évaluation de efficacité se fera dans le meilleur des cas, le pire des cas et le cas moyen.

Dans le cas d’une structure de type séquence, l’évaluation est égale à la somme des coûts. Par exemple, si l’algorithme possède un traitement T1(n) suivit de T2(n), alors T(n)=T1(n)+T2(n).

Dans le cas d’un embranchement, l’évaluation est égale au maximum des embranchements. Par exemple, l’algorithme exécute T1(n) sinon T2(n), alors T(n)=max(T1(n), T2(n)).

Dans le cas d’une boucle, l’évaluation est égale à la somme des coûts des passages successifs. Par exemple, si l’algorithme est un « tant que faire Ti(n) avec la complexité de Ti(n) dépendant du numéro i de l’itération. Alors la complexité est T(n) = somme(i=1 à n) Ti(n).

Pour une version récursive, je vous invite à aller sur la page correspondante. Posons C(n) le traitement effectué dans une fonction en divide&conquer. Alors la complexité est T(n)=2*T(n/2)+C(n) = n log(n) si C(n)=n.

Notation de Landau

la notation de Landau caractérise le comportement asymptotique d’une fonction, c’est à dire le comportement de f(n) quand n tend vers l’infini.

On dit que f(n) est un grand O de g(n) si \exists k>0, \exists n_0 \; \forall n>n_0 \; |f(n)| \leq |g(n)|\cdot k .

complexity1

Exemples

complexity2

complexity3

complexity4

Pire, meilleur et moyenne

Nous pouvons calculer pour la plupart des algorithmes une complexité dans le pire des cas (le plus grand nombre d’opérations élémentaires), le meilleur et en moyenne. La moyenne est une somme pondérée par la probabilité de présence des complexités possibles. Le plus souvent, on utilise la complexité au pire car on souhaite connaitre une borne supérieur de temps d’exécution.

Considérons un algorithme de recherche d’un élément dans un tableau en forme itérative. L’algorithme s’arrête lorsque la valeur a été trouvée. L’algorithme se décompose ainsi : affectation de 0 à i, tant que i n’a pas parcouru le tableau on incrémente i, si tab[i]=valeur alors on retourne vrai, sinon à la fin du tableau on retourne faux. Notons C la complexité du corps de la boucle.

Au pire des cas, l’algorithme parcours tout le tableau, c’est à dire que T(n)=1+n*C=O(n). Au mieux, l’élément est au début du tableau, donc T(n)=1+C=O(1). Nous considérons qu’en moyenne, il y a 50% de chance que l’élément ne soit pas dans le tableau, et 50% qu’il soit à la moitié du tableau (ceci est bien entendu absurde, mais nous ne ferons pas toutes les possibilités). Dans ce cas, la complexité en moyenne est de T(n)=0.5*(1+n*C)+0.5*(1+n*C/2)=a*n+b avec a et b des constantes = O(n). Nous remarquons que le comportement asymptotique en moyenne est le même qu’au pire cas.

Publicités