Complexité Algorithme

• Mesurer l'efficacité d'un algorithme, ce qu'on appelle sa complexité
  • Prévoir son temps d'exécution
  • Estimer les ressources qu'il va mobiliser dans une machine lors de son exécution (place occupée en mémoire en particulier)
  • Comparer avec un autre qui fait le même traitement d'une autre façon, de manière à choisir le meilleur
• L'évaluation de la complexité peut se faire à plusieurs niveaux
  • Niveau purement algorithmique, par l'analyse et le calcul
  • Niveau du programme, par l'analyse et le calcul
  • Niveau de l'exécution du programme expérimentalement

• Jusqu'aux années 70, seule la mesure expérimentale de la complexité d'un algorithme était (parfois) effectuée
• Cette évaluation expérimentale dépendait énormément des machines mais permettait de comparer l'efficacité de différents algorithmes si on les écrivait dans un même langage et qu'on les faisait tourner sur une même machine
• Si on les faisait tourner sur des machines différentes, il fallait évaluer la puissance des machines qui dépend du matériel mais aussi du système d'exploitation et varie en fonction des traitements effectués (calculs bruts, sur des entiers ou des réels, calculs liés à l'affichage, ...)

• Plusieurs complexités peuvent être évaluées :
  • Complexité en temps : il s'agit de savoir combien de temps prendra l'exécution d'un algorithme
  • Complexité en espace : il s'agit de savoir combien d'espace mémoire occupera l'exécution de l'algorithme
• Souvent, si un algorithme permet de gagner du temps de calcul, il occupe davantage de place en mémoire (mais un peu d'astuce permet parfois de gagner sur les deux tableaux)
• Généralement, on s'intéresse essentiellement à la complexité en temps

(ce qui n'était pas forcément le cas quand les mémoires coutaient cher)

• La complexité n'est pas la même selon les déroulements du traitement
  • Complexité au pire : complexité maximum, dans le cas le plus défavorable ( borne supérieur du temps d'exécution)
  • Complexité   en   moyenne   :    il   s'agit   de    la    moyenne des complexités obtenues selon les issues du traitement
  • Complexité au mieux : complexité minimum, dans le cas le plus favorable. En pratique, cette complexité n'est pas très utile
• Si on veut comparer les algorithmes indépendamment des implémentations et des machines, on ne peut comparer que la forme générale de la complexité, en particulier la façon dont elle évolue selon la taille des données

• La complexité d'un algorithme est calculée en fonction d'un paramètre

par rapport auquel on veut calculer cette complexité

• Pour un algorithme qui opère sur une structure de données (tableau), la complexité est généralement exprimée en fonction d'une dimension de la structure.
• Si l'algorithme prend en entrée une structure à plusieurs dimensions il faut préciser en fonction de quelle dimension on calcule la complexité (l'algorithme peut avoir des complexités différentes)
• Pour un algorithme qui opère sur un nombre, la complexité est généralement exprimée en fonction de la valeur du nombre

Calculer la complexité de façon exacte n'est pas raisonnable (quantité d'instructions ) et n'est pas utile (comparaison des algorithmes)

• Première approximation : considérer souvent que la complexité au pire
• Deuxième approximation : calculer la forme générale de la complexité, qui indique la façon dont elle évolue en fonction d'un paramètre
• Troisième approximation : étudier comportement asymptotique de la complexité, quand la valeur du paramètre devient “assez” grande

Notation Landau

• g est dominée asymptotiquement par f : f(n) = O(g(n)) si $ c > 0 et no > 0 tels que ∀ n ³ no f(n) £ c. g(n)
• f domine asymptotiquement g : f(n) = Ω(g(n)) si $ c > 0 et no > 0 tels que ∀ n ³ no f(n) ³ C. g(n)
• f est asymptotiquement équivalente à g :      f(n) = Θ(g(n)) si $ c1 et c2 > 0 et no > 0 tels que ∀ n ³ no c1.g(n) £ f(n) £ c2. g(n)

Exemples

	x = O(x2) car pour x>1, x<x2
	100*x = O(x2) car pour x>100, x<x2
	x2 = O(x3) car pour x>1, x2<x3
	ln(x) = O(x) car pour x>0, ln(x)<x
	∀i>0, xi = O(ex) car pour x tel que x/ln(x)>i, xi<ex
	O(x) = O(x2) mais	O(x2) ≠  O(x)
	Si f(x) = O(1) alors f est majorée
	Si f(x) = Ω (1) f est minorée
	6*2x + x2 = O(2x)
	10n2+4n+2= Ω (n2)
	6*2n + n2 = Ω (n2)

Types de complexité

• Complexité constante en O(1)
• Complexité logarithmique en O(log(n))
• Complexité linéaire en O(n)
• Complexité quasi-linéaire en O(nlog(n))
• Complexité quadratique en O(n2) :
• Complexité polynomiale en O(ni)
• Complexité exponentielle en O(in)
• Complexité factorielle en O(n!)

Exemple

Calcul de la valeur d'un polynôme en un point

1. p  a[0]
2.	pour i 0 à n-1 faire {puissance(a, n) retourne an}
3.	xpi  puissance (x , i)
4.	p  p + a[i]* xpi
fpour
Nombre de multiplications
en 3 --> 1+2+3+...+ (n-1) = (n-l)n/2
en4 --> n
Nombre d'additions			en 4 --> n soit au total:	n(n + 3)/2	< n2	pour n > 3.