Algorithmique Notion de complexité

1 de 27AlgorithmiqueNotion de complexitéFlorent HivertMél :Florent.Hivert@lri.frAdresse universelle :http://www-igm.univ-mlv.fr/˜hivertOutils mathématiques2 de 27Outils mathématiques : analyse élémentaire(Uk)k2Nsuite de terme généralUk,k2N(Uk)k2Kfamille d"indexKN; suite extraite de(Uk)k2NqXk=pUksomme des termesUkoùkvérifiepkq(entiers);lorsquep>q, la somme estvideet vaut 0qYk=pUkproduit des termesUkoùkvérifiepkq(entiers);lorsquep>q, le produit estvideet vaut 1Outils mathématiques3 de 27Identité sur les sommes et produitsqXk=pUk=0@q1Xk=pUk1A+Uq=Up+0@qXk=p+1Uk1APlus généralement, siP(n)est un prédicat :qXk=pUk=qXk=pP(k)est vraiUk+qXk=pP(k)est fauxUkUn exemple très courant :nXk=1Uk=nXk=1kest pairUk+nXk=1kest impairUkIdem pour les produits.Outils mathématiques4 de 27Outils mathématiques : arithmétiqueopérateurs usuels :+ = n=k retourner1sinon retourner n=kOutils mathématiques13 de 27Algorithme (3)En procédant en croissant sur les diviseurs possibles :2kbpncnvusà voirà ne pas voirAlgorithme (calcul du plus grand diviseur (solution 3))Entrée : un entier nSortie : pgd(n)k 2tant que nmodk6=0et kn=k : k k+1si k>n=k retourner1sinon retourner n=kOutils mathématiques14 de 27Analyse des trois algorithmesCalcul des complexités temporelles pratiques des solutions (1), (2) et (3) :Leurs formulations sont du type :A1tant queC:A2A3Pour un algorithme donné, soientt1,tC,t2ett3les temps d"exécutionrespectifs des actionsA1,C,A2etA3.Hypothèse : la boucle représentée en machine par un branchementconditionnel et un branchement inconditionnel; temps d"exécutionrespectifs :tBCettBI.Le temps d"exécution est donc :t1+ (tBC+tC+t2+tBI)B(n) +tC+tBC+t3;oùB(n)est le nombre de boucles exécutées.Outils mathématiques14 de 27Analyse des trois algorithmesCalcul des complexités temporelles pratiques des solutions (1), (2) et (3) :Leurs formulations sont du type :A1tant queC:A2A3Pour un algorithme donné, soientt1,tC,t2ett3les temps d"exécutionrespectifs des actionsA1,C,A2etA3.Hypothèse : la boucle représentée en machine par un branchementconditionnel et un branchement inconditionnel; temps d"exécutionrespectifs :tBCettBI.Le temps d"exécution est donc :t1+ (tBC+tC+t2+tBI)B(n) +tC+tBC+t3;oùB(n)est le nombre de boucles exécutées.Outils mathématiques14 de 27Analyse des trois algorithmesCalcul des complexités temporelles pratiques des solutions (1), (2) et (3) :Leurs formulations sont du type :A1tant queC:A2A3Pour un algorithme donné, soientt1,tC,t2ett3les temps d"exécutionrespectifs des actionsA1,C,A2etA3.Hypothèse : la boucle représentée en machine par un branchementconditionnel et un branchement inconditionnel; temps d"exécutionrespectifs :tBCettBI.Le temps d"exécution est donc :t1+ (tBC+tC+t2+tBI)B(n) +tC+tBC+t3;oùB(n)est le nombre de boucles exécutées.Outils mathématiques14 de 27Analyse des trois algorithmesCalcul des complexités temporelles pratiques des solutions (1), (2) et (3) :Leurs formulations sont du type :A1tant queC:A2A3Pour un algorithme donné, soientt1,tC,t2ett3les temps d"exécutionrespectifs des actionsA1,C,A2etA3.Hypothèse : la boucle représentée en machine par un branchementconditionnel et un branchement inconditionnel; temps d"exécutionrespectifs :tBCettBI.Le temps d"exécution est donc :t1+ (tBC+tC+t2+tBI)B(n) +tC+tBC+t3;oùB(n)est le nombre de boucles exécutées.Outils mathématiques15 de 27Analyse des trois algorithmesRetenirSur une machine où les opérations sur les entiers s"effectuent entemps constant, le temps d"exécution est donc de la forme :aB(n) +boù a et b sont des constantes.Borne maximale :Pour les solution (1) et (2)B(n)n2Pour la solution (3)B(n) bpnc 1Complexité temporelle maximale :Pour les solution (1) et (2)a0n+b0Pour la solution (3)a0bpnc+b0Outils mathématiques15 de 27Analyse des trois algorithmesRetenirSur une machine où les opérations sur les entiers s"effectuent entemps constant, le temps d"exécution est donc de la forme :aB(n) +boù a et b sont des constantes.Borne maximale :Pour les solution (1) et (2)B(n)n2Pour la solution (3)B(n) bpnc 1Complexité temporelle maximale :Pour les solution (1) et (2)a0n+b0Pour la solution (3)a0bpnc+b0Outils mathématiques16 de 27En pratiqueVoici les temps d"exécution mesurés pour quelques nombres à lafois premiers et proches de puissances de 10 :n solution 1 solution 2 solution 3101 0,000 000 6s 0,000 000 7s 0,000 000 3s100003 0,000 427 s 0,000 425 s 0,000 003 s10000019 0,045 s 0,044 s 0,000 031 s1000000007 4.47 s 4.56 s 0,000 308 sOutils mathématiques17 de 27Opération élémentaireOn cherche à définir une notion de compléxitérobuste:indépendante de l"ordinateur, du compilateur, du langage deprogrammation,etc Exprimée en fonction de laTaillede ladonnée à traiter.Retenir (opération élémentaire)Opération qui prend un temps constant (ou presque).Outils mathématiques17 de 27Opération élémentaireOn cherche à définir une notion de compléxitérobuste:indépendante de l"ordinateur, du compilateur, du langage deprogrammation,etc Exprimée en fonction de laTaillede ladonnée à traiter.Retenir (opération élémentaire)Opération qui prend un temps constant (ou presque).Outils mathématiques18 de 27Complexité d"un algorithmeCout deAsurx: l"exécution de l"algorithmeAsur la donnéxrequiertCA(x)opérations élémentaires.Définitions (Cas le pire, cas moyen)n désigne la taille de la donnée à traité.Dans le pire des cas : CA(n) :=maxxjxj=nCA(x)En moyenne : CMoyA(n) :=Xxjxj=npn(x)CA(x)pn: distribution de probabilité sur les données de taille n.Outils mathématiques19 de 27Notations asymptotiquesLes constantes n"importent pas!Définition (notations asymptotiques)Soit g:N7!R+une fonction positive.O(g)est l"ensemble des fonctions positives f pour lesquelles ilexiste une constante positiveet un rang n0tels que :f(n)g(n);pour tout nn0:(g)est l"ensemble des fonctions positives f pour lesquelles ilexiste une constante positiveet un rang n0tels que :f(n)g(n);pour tout nn0:(g) =O(g)\(g).Outils mathématiques20 de 27Par commodité, les expressions " image » des fonctions sontsouvent utilisées dans les notations plutôt que leurs symboles.

Onécrit ainsi "f(n)2X(g(n))» plutôt que "f2X(g)», oùXsignifieO,ou.Par commodité toujours, on écrit souvent " est » plutôt que "2»et on dit souvent " est » plutôt que " appartient ».Exemplenotations asymptotiques (1/2)n2O(n)n2(n)n2(n)7+1=n2O(1)7+1=n2(1)7+1=n2(1)log2n2O(logn)log2n2(logn)log2n2(logn)n+lnn2O(n)n+lnn2(n)n+lnn2(n)n2+3n2O(n3)n2+3n=2(n3)n2+3n=2(n3)Outils mathématiques20 de 27Par commodité, les expressions " image » des fonctions sontsouvent utilisées dans les notations plutôt que leurs symboles.

Onécrit ainsi "f(n)2X(g(n))» plutôt que "f2X(g)», oùXsignifieO,ou.Par commodité toujours, on écrit souvent " est » plutôt que "2»et on dit souvent " est » plutôt que " appartient ».Exemplenotations asymptotiques (1/2)n2O(n)n2(n)n2(n)7+1=n2O(1)7+1=n2(1)7+1=n2(1)log2n2O(logn)log2n2(logn)log2n2(logn)n+lnn2O(n)n+lnn2(n)n+lnn2(n)n2+3n2O(n3)n2+3n=2(n3)n2+3n=2(n3)Outils mathématiques21 de 27On cherche toujours à exprimer toute notation asymptotique àl"aide de fonctions de référence : constante, somme, produit,puissance, logarithme, minimum, maximum Définitions (désignations des complexités courantes)notation désignation(1)constante(logn)logarithmique(pn)racinaire(n)linéaire(nlogn)quasi-linéairenotation désignation(n2)quadratique(n3)cubique(nk), k2N;k2polynomiale(an), a>1exponentielle(n!)factorielleExempleSuite aux résultats précédents, on peut énoncer que le problème ducalcul du plus grand diviseur peut se résoudre en temps au plusracinaire avec un espace constant.Outils mathématiques21 de 27On cherche toujours à exprimer toute notation asymptotique àl"aide de fonctions de référence : constante, somme, produit,puissance, logarithme, minimum, maximum Définitions (désignations des complexités courantes)notation désignation(1)constante(logn)logarithmique(pn)racinaire(n)linéaire(nlogn)quasi-linéairenotation désignation(n2)quadratique(n3)cubique(nk), k2N;k2polynomiale(an), a>1exponentielle(n!)factorielleExempleSuite aux résultats précédents, on peut énoncer que le problème ducalcul du plus grand diviseur peut se résoudre en temps au plusracinaire avec un espace constant.Outils mathématiques21 de 27On cherche toujours à exprimer toute notation asymptotique àl"aide de fonctions de référence : constante, somme, produit,puissance, logarithme, minimum, maximum Définitions (désignations des complexités courantes)notation désignation(1)constante(logn)logarithmique(pn)racinaire(n)linéaire(nlogn)quasi-linéairenotation désignation(n2)quadratique(n3)cubique(nk), k2N;k2polynomiale(an), a>1exponentielle(n!)factorielleExempleSuite aux résultats précédents, on peut énoncer que le problème ducalcul du plus grand diviseur peut se résoudre en temps au plusracinaire avec un espace constant.Outils mathématiques22 de 27Aucun progrès technologique (modèle de machine standard) nepermet à un algorithme de changer de classe de complexité.Exemple (tyranie de la complexité)Effets de la multiplication de la puissance d"une machine par 10,100 et 1000 sur la taille maximale N des problèmes que peuventtraiter des algorithmes de complexité donnée :Outils mathématiques22 de 27Aucun progrès technologique (modèle de machine standard) nepermet à un algorithme de changer de classe de complexité.Exemple (tyranie de la complexité)Effets de la multiplication de la puissance d"une machine par 10,100 et 1000 sur la taille maximale N des problèmes que peuventtraiter des algorithmes de complexité donnée :complexité101001000(logn)N10N100N1000(pn)102N104N106N(n)10N100N1000N(nlogn)<10N<100N<1000N(n2)'3N10N'32N(n3)'2N'5N10N(2n)'N+3'N+7'N+10Outils mathématiques23 de 27Propriétés des notations asymptotiquesPropositionSoient f;g;h;l des fonctions positives et a;b2R+.X désigne n"importe lequel des opérateur O;ouSi f2X(g)et g2X(h)alors f2X(h);Si f;g2X(h)alors af+bg2X(h);Si f2X(h)et g2X(l)alors fg2X(hl);Si f2(h)alors pour tout g on a af+bg2(h);Outils mathématiques24 de 27Cas des polynômesPropositionUn polynôme est de l"ordre de son degré.

Plus précisément siP=dXi=0cixiavec cd6=0(c"est-à-dire que d est le degré de P) alorsP2(xd).Par exemple, 5x3+3x2+100x+122(x3):Outils mathématiques25 de 27RécapitulatifComplexité Vitesse Temps Formulation ExempleFactorielle très lent proportionnelàNNN!Résolution par recherche exhaus-tive du problème du voyageur decommerce.Exponentielle lent proportionnelà uneconstanteà la puissanceNKNRésolution par recherche exhaus-tive du Rubik"s Cube.Polynomiale moyen proportionnelàNà unepuissancedonnéeNKTris par comparaison, comme le trià bulle (N2).Quasi-linéaire assez rapide intermédiaireentre linéaireet polynomialNlog(N)Tris quasi-linéaires, comme leQuicksort.Linéaire rapide proportionnelàNNItération sur un tableau.Logarithmique très rapide proportionnelau logarithmedeNlog(N)Recherche dans un arbre binaire.Constante le plus rapide indépendantde la donnée1 recherche par index dans un ta-bleau.Outils mathématiques26 de 27Calcul de complexité dans les structures de contrôleInstructions élémentaires (affectations, comparaisons) sont entemps constant, soit en(1).Tests : sia2O(A),b2O(B)etc2O(C)alors(ifathenbelsec)2O(A+max(B;C))Tests : sia2(A),b2(B)etc2(C)alors(ifathenbelsec)2(A+min(B;C))Outils mathématiques27 de 27Cas des boucles imbriquéesBoucles siai2O(Ai)(idem;) alors(forifrom1tondoai)2OnXi=1(Ai)!LorsqueAiest constant égal àA, on a(forifrom1tondoai)2nO(A)Retenir (Boucles imbriqués)Cas particulier important : si Ai2O(ik)(idem;) alors(forifrom1tondoai)2O(nk+1)