Algorithmes et complexité
Conception dalgorithmes Principes et 150 exercices non corrigés
ANALYSE DALGORITHMES
MEC6405-Analyse Expérimentale des contraintes
Module  Contraintes & Déformations
Méthodologie danalyse des contraintes résiduelles par diffraction
Analyse des contraintes résiduelles par diffraction des rayons X
Cours de résistance des matériaux
Resistance des materiaux de base
Cours 1ère année ENTPE Résistance des matériaux – Partie 1

Next PDF List

Chapitre 6informatique communeNotion de complexitéalgorithmique1.Intr oductionDéterminer lacomplexité1d"un algorithme, c"est évaluer les ressources nécessaires à son exécution (essentielle-ment la quantité de mémoire requise) et le temps de calcul à prévoir.

Ces deux notions dépendent de nombreuxparamètres matériels qui sortent du domaine de l"algorithmique : nous ne pouvons attribuer une valeur absolueni à la quantité de mémoire requise ni au temps d"exécution d"un algorithme donné.

En revanche, il est souventpossible d"évaluer l"ordre de grandeurde ces deux quantités de manière à identifier l"algorithme le plus efficaceau sein d"un ensemble d"algorithmes résolvant le même problème.Prenons un exemple concret : la détermination du nombre de diviseurs d"un entier natureln.

Une premièresolution consiste à essayer si chacun des entiers compris entre 1 etnest un diviseur den.

Ceci conduit à définirla fonctiondiviseurs1de la figure 1.defdiviseurs1(n):d = 0k = 1whilek <= n:ifn % k == 0:d += 1k += 1returnddefdiviseurs2(n):d = 0k = 1whilek*k < n:ifn % k == 0:d += 2k += 1ifk*k == n:d += 1returndFigure1 - Deux fonctions calculant le nombre de diviseurs d"un entiern.Mais on peut aussi se faire la réflexion suivante : sid2~1;ndivisenalorsd0=ndaussi; de plus,d6pn()d0>pn.

Autrement dit, il suffit de rechercher les diviseurs denqui sont inférieurs ou égaux àpnpouren connaitre le nombre total : c"est le principe utilisé par la fonctiondiviseurs2(on notera le traitementparticulier réservé aux carrés parfaits).Comment comparer ces deux versions? Si on se focalise sur les deux boucles conditionnelles de ces algorithmeson constate que dans les deux cas on effectue deux additions, une division euclidienne et un test.

Chacune deces opérations est effectuéenfois dans le premier cas,pnfois2dans le second.

Nous ne connaissons pas letemps1nécessaire à la réalisation de ces différents calculs, mais on peut légitimement penser que le tempstotal d"execution dediviseurs1n"est pas éloigné de1n+2, le temps2étant le temps requis par les autresopérations.

De même, le temps requis par la fonctiondiviseurs2est de l"ordre de01pn+02.Les temps2et02sont négligeable pour de grandes valeurs den; de plus les valeurs de1et01importent peu;elle dépendent de conditions matérielles qui nous échappent.

Nous n"allons retenir que le taux de croissance dechacune de ces deux fonctions : proportionnel ànpour la première (on dira plus loin qu"il s"agit d"un algorithmede coûtlinéaire), proportionnel àpnpour la seconde.

Autrement dit :-m ultipliernpar 100 multiplie le temps d"exécution dediviseurs1par 100;-m ultipliernpar 100 multiplie le temps d"exécution dediviseurs2par 10.Ainsi, connaissant le temps d"exécution pour une valeur donnée denil est possible d"évaluer l"ordre de grandeurdu temps d"exécution pour de plus grandes valeurs.1.

On dit aussi lecoût.2. tres exactementdpne1 fois.Jean-Pierre Becirspahic6.2informatique commune2.Évalua tionde la complexit éalgorithmique 2.

1) Instructions élémentair esPour réaliser l"évaluation de la complexité algorithmique, il est nécessaire de préciser un modèle de la tech-nologie employée; en ce qui nous concerne, il s"agira d"une machine à processeur unique pour laquelle lesinstructions seront exécutées l"une après l"autre, sans opération simultanées.

Il faudra aussi préciser les instruc-tions élémentaires disponibles ainsi que leurs coûts.

Ceci est particulièrement important lorsqu"on utilise unlangage de programmation tel quePythonpour illustrer un cours d"algorithmique car ce langage possède denombreuses instructions de haut niveau qu"il serait irréaliste de considérer comme ayant un coût constant : ilexiste par exemple une fonctionsortqui permet de trier un tableau en une instruction, mais il serait illusoirede croire que son temps d"exécution est indépendant de la taille du tableau.La première étape consiste donc à préciser quelles sont les instructions élémentaires, c"est-à-dire celle quiseront considérées comme ayant un coût constant, indépendant de leurs paramètres.

Parmi celles-ci figurent engénéral :-les opérations arithmétiques (addition, soustraction, multiplication, division, modulo, partie entière, )-la com paraisonsde données (rela tiond" égalité,d"inf ériorité,. )-le tr ansfertsde données (lecture et écriture dans un em placementmémoire) -les instructions de contrôle (branchement conditionnel et inconditionnel, appel à une fonction auxiliaire, )Attention : il est parfois nécessaire de préciser la portée de certaines de ces instructions.

En arithmétiquepar exemple, il est impératif que les données représentant les nombres soient codées sur un nombrefixedebits.

C"est le cas en général des nombres flottants (le typefloat) et des entiers relatifs (le typeint) représentésusuellement sur 64 bits3, mais dans certains langages existe aussi un typeentier longdans lequel les entiersne sont pas limités en taille.

C"est le cas enPython, où coexistaient jusqu"à la version 3.0 du langage uneclasseintet une classelong.

Ces deux classes ont depuis fusionné, le passage du typeintau typelongétantdésormais transparent pour l"utilisateur.Cependant, dans un but de simplification nous considérerons désormaistoute opération arithmétique comme étant de coût constant.Dans le cas des nombres entiers, l"exponentiation peut aussi être source de discussion : s"agit-t"il d"une opé-ration de coût constant? En général on répond à cette question par la négative : le calcul denknécessite unnombre d"opérations élémentaires (essentiellement des multiplications) qui dépend dek.

Cependant, certainsprocesseurs possèdent une instruction permettant de décaler dekbits vers la gauche la représentation binaired"un entier, autrement dit de calculer 2ken coût constant.Les comparaisons entre nombres (du moment que ceux-ci sont codés sur un nombre fixe de bits) seront aussiconsidérées comme des opérations à coût constant, de même que la comparaison entre deux caractères.

Enrevanche, la comparaison entre deux chaînes de caractères ne pourra être considérée comme une opérationélémentaire, même s"il est possible de la réaliser en une seule instructionPython.

Il en sera de même desopérations d"affectation : lire ou modifier le contenu d"un case d"un tableau est une opération élémentaire, maisce n"est plus le cas s"il s"agit de recopier tout ou partie d"un tableau dans un autre, même si la technique duslicingenPythonpermet de réaliser très simplement ce type d"opération.2.

2) Nota tionsma thématiquesUne fois précisé la notion d"opération élémentaire, il convient de définir ce qu"on appelle lataillede l"entrée.Cette notion dépend du problème étudié : pour de nombreux problèmes, il peut s"agir du nombre d"élémentsconstituant les paramètres de l"algorithme (par exemple le nombre d"éléments du tableau dans le cas d"unalgorithme de tri); dans le cas d"algorithmes de nature arithmétique (le calcul denkpar exemple) il peut s"agird"un entier passé en paramètre, voire du nombre de bits nécessaire à la représentation de ce dernier.

Enfin, ilpeut être approprié de décrire la taille de l"entrée à l"aide de deux entiers (le nombre de sommets et le nombred"arêtes dans le cas d"un algorithme portant sur les graphes).Une fois la taillende l"entrée définie, il reste à évaluer en fonction de celle-ci le nombref(n)d"opérationsélémentaires requises par l"algorithme.

Mais même s"il est parfois possible d"en déterminer le nombre exact, onse contentera le plus souvent d"en donner l"ordre de grandeur à l"aide des notations deLandau.3.

Voir le chapitre 4.Notion de complexité algorithmique 6.

3) La notation la plus fréquemment utilisée est le " grand O » :f(n) = O(n)() 9B>0f(n)6Bn:Cette notation indique que dans le pire des cas, la croissance def(n)ne dépassera pas celle de la suite(n).L"usage de cette notation exprime l"objectif qu"on se donne le plus souvent : déterminer le temps d"exécutiondans le cas le plus défavorable.

On notera qu"un usage abusif est souvent fait de cette notation, en sous-entendant qu"il existe des configurations de l"entrée pour lesquellesf(n)est effectivement proportionnel àn.On dira par exemple que la complexité de la fonctiondiviseurs2est unO(pn)mais jamais qu"elle est unO(n),même si mathématiquement cette assertion est vraie puisquef(n) = O(pn) =)f(n) = O(n).D"un usage beaucoup moins fréquent, la notationexprime une minoration du meilleur des cas :f(n) =(n)() 9A>0An6f(n):L"expérience montre cependant que pour de nombreux algorithmes le cas " moyen » est beaucoup plus souventproche du cas le plus défavorable que du cas le plus favorable.

En outre, on souhaite en général avoir la certitudede voir s"exécuter un algorithme en un temps raisonnable, ce que ne peut exprimer cette notation.Enfin, lorsque le pire et le meilleur des cas ont même ordre de grandeur, on utilise la notation:f(n) =(n)()f(n) = O(n) etf(n) =(n)() 9A;B>0An6f(n)6Bn:Cette notation exprime le fait que quelle que soit le configuration de l"entrée, le temps d"exécution de l"algo-rithme seragrosso-modoproportionnel àn.Ordre de grandeur et temps d"exécutionNous l"avons dit, la détermination de la complexité algorithmique ne permet pas d"en déduire le tempsd"exécution mais seulement de comparer entre eux deux algorithmes résolvant le même problème.

Cependant, ilimporte de prendre conscience des différences d"échelle considérables qui existent entre les ordres de grandeursusuels que l"on rencontre.

En s"appuyant sur une base de109opérations par seconde, le tableau de la figure 2 està cet égard significatif.

Il indique en fonction de la taillende l"entrée (102,103, ) et du nombre d"opérationsrequis par un algorithme (logn,n, ) le temps d"exécution de ce dernier.lognnnlognn2n32n1027 ns100 ns0;7s10s1 ms41013années10310 ns1s10s1 ms1 s10292années10413 ns10s133s100 ms17 s10517 ns100s2 ms10 s11;6 jours10620 ns1 ms20 ms17 mn32 annéesFigure2 - Temps nécessaire à l"exécution d"un algorithme en fonction de sa complexité.La lecture de ce tableau est édifiante : on comprend que les algorithmes ayant une complexité supérieure à unecomplexité quadratique soient en général considérées comme inutilisables en pratique (sauf pour de petitesvoire très petites valeurs den).O(logn)logarithmiqueO(n)linéaireO(nlogn)quasi-linéaireO(n2)quadratiqueO(nk) (k>2)polynomialeO(kn) (k >1)exponentielleFigure3 - Qualifications usuelles des complexités.Jean-Pierre Becirspahic6.4informatique communeExercice 1Pour vous familiariser avec ces notions, évaluez pour chacune des fonctions suivantes le tempsd"exécution en fonction den:deff1(n):x = 0foriinrange (n):forjinrange (n):x += 1returnxdeff2(n):x = 0foriinrange (n):forjinrange (i):x += 1returnxdeff3(n):x = 0foriinrange (n):j = 0whilej*j < i:x += 1j += 1returnxdeff4(n):x, i = 0, nwhilei > 1:x += 1i //= 2returnxdeff5(n):x, i = 0, nwhilei > 1:forjinrange (n):x += 1i //= 2returnxdeff6(n):x, i = 0, nwhilei > 1:forjinrange (i):x += 1i //= 2returnx2.

3) Di fférents types de complexitéCertains algorithmes ont un temps d"exécution qui dépend non seulement de la taille des données mais de cesdonnées elles-mêmes.

Dans ce cas on distingue plusieurs types de complexités :-la complexitédans le pire des cas: c"est un majorant du temps d"exécution possible pour toutes les entréespossibles d"une même taille.

On l"exprime en général à l"aide de la notation O.-la complexitédans le meilleur des cas: c"est un minorant du temps d"exécution possible pour toutes lesentrées possibles d"une même taille.

On l"exprime en général à l"aide de la notation.

Cependant cettenotion n"est que rarement utilisée car souvent peu pertinente au regard des complexités dans le pire descas et en moyenne.-la complexitéen moyenne: c"est une évaluation du temps d"exécution moyen portant sur toutes les entréespossible d"une même taille supposées équiprobables.La plupart du temps on se contentera d"analyser la complexité dans le pire des cas.Exemple.

Considérons les algorithmes de recherche dans une liste de longueurn; nous en avons écrit deuxdans le chapitre précédent (voir figure 4).-L"algorithme de recherche séquentielle effectue dans le meilleur des cas une seule comparaison (lorsque lepremier élément testé est l"élément recherché) et dans le pire des casncomparaisons (par exemple lorsquel"élément recherché ne se trouve pas dans la liste).

On dira que le coût dans le meilleur des cas est constant, cequ"on traduira par un coût en(1), et linéaire dans le pire des cas, c"est-à-dire une complexité en(n).Dans tous les cas la complexité est donc un O(n).-Lorsque la liste est triée, l"algorithme de recherche dichotomique effectue lui aussi une seule comparaisondans le meilleur des cas (lorsque l"élément recherché se trouve au milieu de la liste) et dans le pire des cas unnombre de comparaison proportionnel àlogn.

En effet, siC(n)désigne la complexité dans le pire des cas ondispose de la relation :C(n) =C(n=2)+(1).

Ce type de relation est souvent étudié dans le cas particulier despuissances de 2 en posantup=C(2p)car alors on dispose de la relationup=up1+(1)qui conduit àup=(p),soit C(n) =(logn) lorsquen= 2p.Dans tous les cas, la complexité est donc un O(logn).Notion de complexité algorithmique 6.5defcherche(x, l):foryinl:ify == x:returnTruereturnFalsedefcherche_dicho(x, l):i, j = 0,len(l)whilei < j:k = (i + j) // 2ifl[k] == x:returnTrueelifl[k] > x:j = kelse:i = k + 1returnFalseFigure4 - Les algorithmes de recherche linéaire et de recherche dichotomique.Pour évoquer la notion de complexité en moyenne, il est nécessaire de disposer d"une hypothèse sur ladistribution des données.

Dans le cas de l"algorithme de recherche séquentielle, nous allons supposer que leséléments du tableau sont des entiers distribués de façon équiprobable entre 1 etk2N(au sens large).Nous disposons donc dekntableaux différents; parmi ceux-ci,(k1)nne contiennent pas l"élément que l"oncherche et dans ce cas l"algorithme procède exactement àncomparaisons.Dans le cas contraire, l"entier recherché est dans le tableau, et sa première occurrence est dans laiecase avec laprobabilité(k1)i1ki.

L"algorithme réalise alorsicomparaisons.

La complexité moyenne est donc égale à :C(n) =(k1)nknn+nXi=1(k1)i1kii:À l"aide de la formule :nXi=1ixi1=1+(nxn1)xn(1x)2(valable pourx,1) cette expression se simplifie en :C(n) =n11kn+k11+nk11kn=k111kn:Lorsquekest petit devantnnous avonsC(n)ket il est légitime de considérer que la complexité moyenne estconstante; lorsquenest petit devantk,C(n)net la complexité moyenne rejoint la complexité dans le pire descas.2.

4) C omplexitéspa tialeDe la même façon qu"on définit la complexité temporelle d"un algorithme pour évaluer ses performances entemps de calcul, on peut définir sacomplexité spatialepour évaluer sa consommation en espace mémoire.

Leprincipe est le même sauf qu"ici on cherche à évaluer l"ordre de grandeur du volume en mémoire utilisé : ilne s"agit pas d"évaluer précisément combien d"octets sont consommés par un algorithme mais de préciser sontaux de croissance en fonction de la taillende l"entrée.

Cependant, on notera que la complexité spatiale estbien moins que la complexité temporelle un frein à l"utilisation d"un algorithme : on dispose aujourd"hui leplus souvent d"une quantité pléthorique de mémoire vive, ce qui rend moins important la détermination de lacomplexité spatiale.Jean-Pierre Becirspahic