CM8

Complexité des algorithmes

Fonction en la taille de la donnée Ex: un entier se code en O(log(n)) Toute algo de cette forme est exponentiel : T(log n) = O(n)

Complexité des algorithmes recursifs

⇒ Arbre d’execution dont les noeuds sont des appels a la fonction La complexité c’est le nombre de nœuds $\times$ coût d’un nœud Certains noeuds prennent les meme parametres Hypothese : un algo avec les meme parametres donne le même resultat

Acceleration (Programmation dynamique)

Complexité = nombre de noeuds differents $\times$ cout d’un noeud Espace = Les combinaisons d’entré possible (tableau, matrice, etc.)

Exemple

input : $P_1,P_2,P_n$ Qui représente les dimensions de n matrices. Le coût du produit de 2 matrices est $P+1=P_{i-1}\times P_i\times$ Question : Calculer le produit de $A_1\times \dots A_n$ avec un coût minimal. Par exemple

M(i, j)
deb
si i=j alors retourner 0
v = +inf
pour k=i à j-1 faire
	x=M(i,k)
	y=M(k+1,j)
	v'=x+y+P_i-1 P_k P_j
	si v' < v
		v = v'
retourner v

Complexité : profondeur de l’arbre = n dégré max = n Donc la complexité = $O(n^n)$

Avec acceleration : Nombre de noeuds differents : Dom(i) x Dom(j) n x n = O(n²) Cout d’un noeud = O(n)

Classes

Classe P = polynomial Classe NP = Non-deterministe (Certificat poly + Verification poly) Classe NP-hard = $\forall Q^{\prime }\in NP$ alors $Q^{\prime }\ll Q$

P = NP

On suppose que P=NP alors on a un oracle pour un problème de décision