Notions de complexité

Complexité des algorithmes

Un même problème peut être, le plus souvent, résolu par plusieurs algorithmes, c’est pourquoi il est très important de pouvoir comparer l’efficacité des différents algorithmes pouvant être mis en œuvre pour résoudre ce problème. Deux critères principaux sont généralement considérés quand on étudie l’efficacité d’un algorithme ; le premier est le temps de calcul qu’on appelle aussi parfois coût de l’algorithme, le second l’espace mémoire nécessaire à l’exécution de l’algorithme. Si l’espace mémoire reste un critère important de l’évaluation de l’efficacité d’un algorithme, en pratique, dans la majorité des problèmes à résoudre, le temps de calcul devient un paramètre principal mesurant l’efficacité d’un algorithme. Par exemple, pour un logiciel interactif, un temps de réponse court est un élément essentiel du confort de l’utilisateur. De même, certains programmes industriels doivent être utilisés un grand nombre de fois dans un délai très court.

Nous nous intéresserons à la complexité en temps d’un algorithme que, par abus de langage, nous appellerons simplement « complexité d’un algorithme ».

Exemple :

On cherche à afficher la liste des diviseurs d’un nombre entier n :

defdiviseurs(n) :

            for i in range(1,n+1) :

                        if n % i == 0 :

                                   print(i)

Cet algorithme réalise exactement n calculs de restes de divisions euclidiennes, n comparaisons et au plus n affichages.

Import  math

defdiviseurs(n) :

            for i in range (1,int(math.sqrt(n))+1):

                        if n % i == 0 :

                                   print(i)

                                   if n//i != i :

                                               print(n//i)

Cet algorithme réalise  un calcul de racine carrée, ⌊√n⌋calculs de reste, entre ⌊√n⌋et 2 ⌊√n⌋comparaisons etentre 0 et 2⌊√n⌋affichages.

Déterminer le coût d’un algorithme

Pour déterminer le coût d’un algorithme, on se fonde en général sur le modèle de complexité suivant :

• Une affectation, une comparaison ou l’évaluation d’une opération arithmétique ayant en général un faible temps d’exécution, celui-ci sera considéré comme l’unité de mesure du coût d’un algorithme.

• Le coût des instructions p et q en séquence est la somme des coûts de l’instruction p et de l’instruction q.

• Le coût d’un test if b: p else: q est inférieur ou égal au maximum des coûts des instructions p et q, plus le temps d’évaluation de l’expression b.

• Le coût d’une boucle for i in iterable: p est égal au nombre d’éléments de l’itérable multiplié par le coût de l’instruction p si ce dernier ne dépend pas de la valeur de i. Quand le coût du corps de la boucle dépend de la valeur de i, le coût total de la boucle est la somme des coûts du corps de la boucle pour chaque valeur de i.

• Le cas des boucles whileest plus complexe à traiter puisque le nombre de répétitions n’est en général pas connu a priori. On peut majorer le nombre de répétitions de la boucle de la même façon qu’on démontre sa terminaison et ainsi majorer le coût de l’exécution de la boucle.

Complexité et notation O

En réalité, lorsqu’on cherche à évaluer l’efficacité d’un algorithme, il est souvent inutile d’aller jusqu’à ce niveau de détail : on se contentera de dire que le nombre d’opérations élémentaires effectuées est par exemple proportionnel à n ou à √n. Il y a plusieurs raisons à cela.

·        les différentes opérations élémentaires considérées ne demandent pas toutes exactement le même temps de calcul et cachent donc un facteur multiplicatif, borné mais très compliqué à déterminer précisément. D’autre part,

·        le même programme peut être exécuté sur deux machines différentes, l’une étant par exemple deux fois plus rapide que l’autre. Cela ne change évidemment rien à l’efficacité intrinsèque de l’algorithme et ce qui nous intéresse réellement n’est pas le temps précis d’exécution d’un programme, mais l’ordre de grandeur de ce temps en fonction de la taille des données.

Une dernière notion à considérer est celle du terme dominant dans le temps d’exécution d'un algorithme.Par exemple, si on a déterminé que ce temps était proportionnel à n²+3n, dès que la taille n des données devient un peu importante, il est connu que le terme 3n augmente beaucoup moins vite que n² : on dit qu’il est négligeable devant ce dernier. Pour décrire l’efficacité d’un algorithme, seul le terme qui croît le plus vite a donc un intérêt. Par exemple, ici pour n ≥ 3, on a n²+3n ≤ 2n² ; la quantité n²+3n est donc bornée, à partir d’un certain rang, par le produit de n² et d’une constante. On dit alors que la quantité de n² + 3n est « un grand O de n² » et on écrira n² + 3n = O(n²).

La relation O

La notation f(x) = O(g(x)) signifie qu'il existe c > 0 tel que f(x) ≤c.g(x) dès que x est suffisamment grand. Noter qu'elle ne s'applique qu'à des fonctions positives à partir d'unecertaine valeur n0. On a :

Réflexivité : f(x) = O(f(x))

transitivité : si f(x) = O(g(x)) et g(x) = O(h(x)), alors f(x) = O(h(x))

linéarité : si f1(x) = O(f2(x)) et g1(x) = O(g2(x)), alors

f1(x)+a.g1(x) = O(f2(x)+a.g2(x)).

f(x) = O(a.f(x)) pour tout réel a > 0 ;

De manière générale, on dira qu’un algorithme a une complexité en O(f(n)) si son coût est, à partir d’un certain rang, inférieur au produit de f(n) par une constante .

Les complexités les plus utilisées sont :

Constante :O(1) accéder au premier élément d’un ensemble de données.

Logarithmique : O(log(n))couper un ensemble de données en deux parties égales, puis ces moitié en deux parties égales, etc.

Linéaire : O(n) parcourir un ensemble de données.

Quasi-linéaire : O(nlog(n)) couper répétitivement un ensemble de données en deux et combiner les solutions partielles pour calculer la solution générale.

Quadratique : O(n²) parcourir un ensemble de données en utilisant deux boucles imbriquées.

Polynomial : O(n^p)parcourir un ensemble de données en utilisant p boucles imbriquées.

Exponentielle : O(2ⁿ)générertous les sous ensemblespossibles d’un ensemble de données.

Cependant, on peut donner lesordres de grandeur des temps d’exécution que l’on rencontre en pratique pour un problèmede taille n = 10⁶ sur un ordinateur personnel effectuant un milliard d’opérations parseconde.

Complexité en espace

On appelle complexité en espace d’un algorithme la place nécessaire en mémoire pour le faire fonctionner. Elle s’exprime également sous la forme d’un O(f(n)) où n est la taille du problème.

Évaluer la complexité en espace d’un algorithme ne pose pas de difficulté; il suffit de faire le total des tailles en mémoire des différentes variables utilisées. Une première exception à la règle est le cas où on alloue dynamiquement de l’espace mémoire au cours du programme. L’autre cas est celui des fonctions récursives, qui cachent souvent une complexité en espace élevée.

Exercices :

Exercice 1 :En utilisant la notation O, donner, en fonction de n, la complexité dans le pire des cas desfonctions suivantes :

(a) Fonction prodmat :

pour i = 1 à n faire

pour j = 1 à n faire

C[i; j]   0 ;

pour k = 1 à n faire

C[i; j]   C[i; j] + A[i; k] _ B[k; j] ;

fin pour

fin pour

fin pour

(b) Fonction mystere :

pour i = 1 à n 􀀀 1 faire

pour j = i + 1 à n faire

pour k = 1 à j faire

opération en O(1) ;

fin pour

fin pour

fin pour

(c) Fonction oddidonc :

pour i = 1 à n faire

si i impair

pour j = 1 à n faire

x   x + 1 ;

fin pour

pour j = 1 à n faire

yy + 1 ;

fin pour

fin si

fin pour

Exercice 2 : On considère l’algorithme suivant où toutes les variables contiennent des entiers.

Entrée: un entier n>1

Sortie: la racine de n

infß 1; sup ß n

tant que inf< sup-1 faire

midß (inf + sup) / 2

si mid*mid <= n faire

infßmid

sinon

supßmid

retournerinf

Quelle est la complexité ?

Exercice 3 : Écrire un programme qui trouve le plus petit multiple commun à 2 entiers naturels m et n. Puis calculer la complexité en temps de l’algorithme.

Exercice 4 :Quelle est la complexité en temps d’un algorithme de division euclidienne procédant par soustractions successives ? Et sa complexité en espace?

Exercice 5 : calculer la complexité de la recherche séquentielle, la recherche dichotomique, tri à bulle, tri par sélection, tri par insertion.

Complexité et récursivité

Exercice 6 : calculer la complexité du tri rapide, tri fusion et l’algorithme récursif de la recherche dichotomique.

Problème de Hanoï :

Le jeu est constitué d’une plaquette de bois où sont plantées trois tiges numérotées 1,2 et 3. Sur ces tiges sont empilés des disques de diamètres tous différents. Les seules règles du jeu sont que l’on ne peut déplacer qu’un seul disque à la fois, et qu’il est interdit de poser un disque sur un disque plus petit.

Au début, tous les disques sont sur la tige 1 ( celle de gauche), et à la fin ils doivent être sur celle de droite.

Algorithme :

Procédure   Hanoi(n, départ, intermédiaire, destination)

            Si n > 0 alors

                        Hanoi(n-1,départ, destination, intermédiaire)

                        Déplacer un disque de départ vers destination

                        Hanoi(n-1,intermédiaire,départ,destination)

            Fin Si

Fin

Question :

Calculer la complexité de l’algorithme de Hanoi