[PDF] Complexité dun algorithme I Généralités

View - Download Complexité dun algorithme I Généralités

Previous PDF

Next PDF

2021-2022CoursInformatiqueComplexité d"un algorithme

I

Généralités La question de la performance est centrale en informatique. Si un problème est traité en un

temps raisonnable, l"utilisateur est satisfait. On s"attache en général peu à une mesure précise du

temps d"exécution, mais uniquement à une approximation de ce temps. Si le temps obtenu est perçu comme relativement long, se posera la question d"une solution plus efficace. La machine

étantfixée, l"amélioration portera alors sur la façon dont sont conçus les algorithmes en fonction

du volumende données à traiter. Par exemple, si en doublant le volume de données, un algorithme

renvoie un résultat en multipliant le temps d"exécution par2et un autre le renvoie en multipliant

le temps d"exécution parn >2, on optera évidemment pour le premier : on dit quesa complexité

temporelle est meilleure. Ajoutons que l"on peut aussi définirsa complexité spatialeafin de prendre en compte l"espace mémoire occupé au cours de l"exécution d"un algorithme. Plus sa complexité est grande, plus le programme mettant en oeuvre l"algorithme aura besoin de zones mémoires pour stocker les données. I.1 Complexité temp orelleet s patialed"un a lgorithme

Définition :La complexité

1temporelle d"un algorithme

est une information2sur son temps d"exécution liée au volumende données à traiter.La complexité temporelle d"un programmeest la complexité temporelle de l"algorithme associé. Remarques :•La complexité temporelle ne dépend pas : des performances du processeur de la machine sur laquelle le programme est exécuté, des mo desd"accès à la mémoire viv eet des mo desde sto ckage, du langage de pro grammationdans lequel l"algorithme est traduit, du compilateur/in terpréteurexécuté. On se place sur une machine idéalisée dont la mémoire est considérée comme infinie et l"accès aux données se fait en temps constant.

•Le volume de données (on dit aussila tailledes données) dépend du problème étudié :

il peut s"agir du nombre d"éléments constituant les paramètres de l"algorithme (par exemple le nombre d"éléments d"un tableau), dans le cas d"algorithmes de nature arithmétique (le calcul den!par exemple), il peut s"agir d"un entier passé en argument, dans le cas d"algorithmes avec des chaînes de caractères, il peut s"agir de la longueur des chaînes de caractères. Noter que le volume de données est un entier naturel caractérisant le nombre de données et non son occupation mémoire en octets (ou en bits). Définition :La complexité spatiale d"un algorithme est une estimation de l"espace mémoire

occupé au cours de l"exécution d"un programme en fonction du volumende données à traiter.

La complexité spatiale d"un programmeest la complexité spatiale de l"algorithme associé. Le programme de CPGE met l"accent sur la complexité temporelle et c"est cette notion que nous allons développer.1. On dit aussi le " coût ». 2

. Ce n"est pasletemps d"exécution réel sur une machine donnée, avec des logiciels donnés et des processus en

cours d"exécution.Lycée Michelet - classes de PCSI1

2021-2022CoursInformatiqueI.2Mesure de la complexité temp orelle

La mesure de la complexité temporelle nécessiteun modèle. Dans celui-ci : -on préciseles opérations élémentairesqui, par hypothèse,se déroulent en temps borné par une constante, on suppose quela complexité temporelle d"un algorithme est proportionnelle au nombre d"opérations élémentaires.

Sans être exhaustif,les opérations génériquessuivantes sont considérées commeélémentaires:

le sop érationsarithmétiques ( +,-,*,/,//,%), la comparaison de do nnées: relation d"égalité(==),d"ordre(<,>,...), le transfert de données :lecture(input,open , readline,...) etécriture dans un empla- cement mémoire(print, close, writeline,...), le sinstructions de co ntrôle( if,elif,else,while,for),

l"affectation en général (sans tenir compte de la complexité liée à l"exécution de l"expression

à droite de celle-ci), càd.a= ; par exemplea= 0 .

Remarques :

Les hypothèses ci-dessus sont acceptées, mais simplificatrices. En effet, elles dé- pendent partiellement du langage de programmation. Par exemple, Les entiers python sont de typelong(i.e.8octets) (à partir de la version 3.0) : les opérations arithmétiques ne sont donc pas toujours élémentaires. On supposera cependant leur temps d"exécution borné. La comparaison entre chaînes de caractères n"est pas élémentaire. Seule la comparaison entredeuxcaractères sera supposée élémentaire. La recopie d"un tableau entier n"est pas élémentaire. Seulela copie d"un élémentd"un tableau sera supposée élémentaire.

Par ailleurs, il existedes opérations liées à des structures de données, appelées des types dans

Python. Certaines opérationsse déroulent en temps constant(ouen temps amorti constant3) et on peut les considérer comme des opérationsélémentaires: l"a joutdans un tableau tde typelist, càd.t.append(item)out[i]= item l"a joutdans un dictionnaire dviad[i]=item

l"accès à un élément via son index dans un itérable (tableautde typelist, dictionnaired,

chaîne de caractèress,...) càd.t[i], d[i], s[i], ... l"accès à la longueur d"un itérable (tableautde typelist, dictionnaired, chaîne de caractèress,...) càd.len(t),len (d),len (s),... la suppression d"un élément dans un dictionnaire càd.deldict[key](alors que ce n"est pas en temps constant pour un tableau de typelist) la récup érationdes clés d"un dictionnaire cà d.dict.keys() le test d"existence d"un élément dans un dictionnaire (typedict) ou un ensemble (type set) viaeins(ouenotin s).Attention! Ce test d"existence avec les tableaux de typelistn"est absolument pas une opération élémentaire.

Parmi les opérationsnonélémentaires, on peut citer sans être exhaustif : la recherche d"un

élément dans un tableau de typelist, la suppression d"un élément dans un tableau de type list, les tests d"égalité entre listes (t1== t2 ), le slicing de listes (t[a:b]).3

. Cela signifie que le temps est constant dans la grande majorité des cas, mais qu"il peut y avoir des exceptions.Lycée Michelet - classes de PCSI2

2021-2022CoursInformatiqueI.3La notation O

Notation de Landau: on dit qu"une suite numérique(un)estdominéepar la suite(vn), et on noteun=O(vn), quand il existen0?Net un réelk >0tel que :

Exemple :

Considérons le programme de détermination du nombre d"occurrences dans un tableau

de typelist. On veut déterminer la complexité de la fonctionnbre_occurrences.2defn bre_occurrences(x:object, t :list)- >i nt:3c= 0 4fori i nr ange(len(t)):5ift [i]= =x :6c= c + 1 7returnc

Complexité :•

L"affectationc= 0 compte pour une opération élémentaire (on dit qu"elle est enO(1), car majorée par une constante). La boucle bornéeforiinrange(len(t))se déroulelen(t)fois, oùlen(t)est une opération élémentaire. L"instruction de contrôleif, l"accès àt[i], ainsi que le test d"égalitét[i]== x se déroulent en temps constant (3 opérations). Le calcul de l"expressionc+1ainsi que l"affectationc= c +1se déroulent en temps constant (2 opérations). •returncest une opération élémentaire.

Conclusion :

Sin = len(t)(taille de l"entrée), le traitement se réalise en un maximum de5n+2 des cas de la fonctionnbre_occurrencesestO(n). On dit aussi que la complexité temporelle estlinéaire.

Une fois le travail d"analyse détaillée ci-dessus fait, on se rend compte que l"on aurait pu le

simplifier comme suit grâce à la notation de Landau : La longueur du tableaun = len(t)est une mesure de la taille du problème considéré. •L"affectationc= 0 se déroule enO(1). La boucle bornéeforiinrange(len(t))se déroulenfois. De plus,len(t)se déroule enO(1). Les instructionsift[i]= =x etc= c + 1 se déroulent enO(1). Donc dans le pire des cas, la boucleforet son bloc de code se déroulent enO(n). •returncse déroule enO(1).

Conclusion :

par somme,la complexité temporelle dans le pire des casde la fonction nbre_occurrencesest enO(n). I.4

Le pire et le meilleur des cas.

Reprenons la fonctionnbre_occurrences.

Dans le meilleur des cas,t[0]== x : la boucle s"arrête après1passage. On dit quela complexité temporelle dans le meilleur des casest enO(1). Dans le pire des cas,xn"est pas danst: la boucle s"arrête aprèsnpassage(s). On dit que la complexité temporelle dans le pire des casest enO(n).

Par défaut, on déterminera la complexité temporelle dans le pire des cas.Lycée Michelet - classes de PCSI3

2021-2022CoursInformatiqueI.5Classes de complexité asymptotique

Définition :Lacomplexité asymptotiqueest le comportement de la complexité d"un algorithme lorsque la taille de son entrée est asymptotiquement grande. Il peut s"agir a priori de complexité asymptotique moyenne ou dans le meilleur des cas ou dans le

pire des cas.En CPGE, lorsque l"on demande la " complexité » (ou le " coût ») d"une fonction,

il s"agira toujours de " la complexité asymptotique dans le pire des cas » de cette fonction. Rappelons que la détermination de la complexité algorithmique ne permet pas d"en déduire le temps d"exécution mais seulement de comparer entre eux deux algorithmes résolvant le même

problème. Cependant, il importe de prendre conscience des différences d"échelle considérables qui

existent entre les ordres de grandeurs que l"on rencontre usuellement. Considérons un ordinateur personnel standard capable de réaliser1011opérations numériques par seconde.

Quel est le temps d"exécutiont(n)d"un algorithme avecn= 104entrées pour plusieursfonctionsf(n)?f(n)4

log nnn log nn 2n 32
nt(n)0.13 ns0.01μs0.1μs1ms10 s10

2992années

Ce tableau est édifiant! On comprend que les algorithmes ayant une complexité supérieure à une

complexité quadratique soient en général considérés comme inutilisables en pratique (sauf pour

de petites, voire très petites valeurs den).

Définition :

Soitnun entier naturel non nul. On dit qu"un algorithme de complexité temporelle

T(n)s"exécute dans le pire des cas :

e ntemps constantquandT(n) =O(1) en temps logarithmiquequandT(n) =O(log n) en temps linéairequandT(n) =O(n) en temps quasi-linéairequandT(n) =O(n log n) en temps quadratiquequandT(n) =O(n2) en temps cubiquequandT(n) =O(n3) en temps polynomialquand il existep≥2tel queT(n) =O(np) en temps exponentielquand il existea >1tel queT(n) =O(an)4

. sauf mention autre explicite, en informatique,logsignifie toujourslog2(logarithme en base 2). Il est définie,

pour tout réelxparlog2(x) =ln(x)ln(2)Lycée Michelet - classes de PCSI4

2021-2022CoursInformatiqueIIExemples

II.1

Exemple de b ouclesim briquées10defe st_element(x:object, t:list):11???renvoieT rues ix e std anst ,t ableauà 2 d imensions;F alses inon???12n,p = l en(t),l en(t[0])13fori i nr ange(n):14forj i nr ange(p):15ift [i][j]= =x :16returnT rue17returnF alse

Complexité :Le nombrende lignes etpde colonnes du tableautsont des mesures appropriées de la taille du problème considéré. Les affectationsn, p= len (t),len (t[0])se déroulent enO(1)carlen(t)etlen(t)[0] se déroulent enO(1). Dansle pire des cas, pour chacun desnpcouples d"indices(i,j), on réalise enO(1)le test ift[i]== x . La complexité de la boucle imbriquée est donc enO(np). •Alors, l"instructionreturnFalseest exécutée. Celle-ci se déroule enO(1). Par somme,la complexité temporelle dans le pire des casde la fonctionest_elementest donc enO(np). II.2

Exemple d"app elà une fonction auxiliaire 20defm ystere(t:list,T :list)->l ist:21L= [ ]22fori i nr ange(len(t)):23ifn b_occurrences(t[i],T)> =1 :24L.append(t[i])25returnL

Cette fonction renvoie la liste des éléments detqui sont dansT, dans l"ordre dans lequel ils apparaissent dansT, et répétés autant de fois qu"ils sont danst. Complexité :Il faut tenir compte de la complexité de la fonctionnb_occurrences. Posonsn = len(T)etp = len(t). Le nombrend"éléments du tableauTetpd"éléments du tableautsont des mesures appropriées de la taille du problème considéré.

L"aff ectationL= [] , se déroule enO(1).

Danstousles cas, l"instructionifnb_occurrences(t[i],T)>= 1 est exécutée pour les péléments det. Dansle pire des cas, la fonctionnb_occurrencess"exécute enO(n). Le pire des cas correspond ànb_occurrences(t[i],T)== 0 . Finalement, la complexité temporelle liée à cette boucle est enO(np).

La complexité temporelle dans le pire des cas

de la fonctionmystere, somme d"une opération enO(1)et d"une boucle enO(np), est donc enO(np).Lycée Michelet - classes de PCSI5

2021-2022CoursInformatiqueII.3Rec herchedic hotomiquedans un tableau trié

On se donne un tableautde typelisttrié dans l"ordre croissantet un nombrex.

On veut profiter de l"ordre detafin d"accélérer la recherche dexdanst.Le principe de base est simple : on compare la valeur cherchéexavec celle au milieu du tableau;

si celle dexest plus petite, on cherche à gauche du milieu du tableau, sinon on cherche à sa droite; ensuite, on recommence.28fromm athi mporti nf29

30defr echerche_dichotomique(x:object, t :list)->int:31???renvoiel ap ositiond ex d ansl et ableaut s upposét riée ti nfs ix n es?yt rouvep as???32assertt ! =[ ], " te stu nt ableauv ide! "33ind_g, i nd_d= 0 ,l en(t)-1# indiced eg auchee ti ndiced ed roite34

35whilei nd_g< =i nd_d:36#i nvariant: 0 < =i nd_ge td < =l en(t)-137#i nvariant: x n ep euts et rouverq ued anst [ind_g..ind_d],i nd_ge tind_di nclus

38ind_m= ( ind_g+ i nd_d)//2# i ndiced um ilieud ut ableau( àu neu nitéprèsv ersl eb as)

39ifx > t [ind_m]:40ind_g= i nd_m+ 1 # x e sts trictementà d roited um ilieu41elifx < t [ind_m]:42ind_d= i nd_m- 1 # x e sts trictementà g auched um ilieu43else:44returni nd_m45returni nf# x n ?estp asd ansl et ableau

Nous reviendrons plus tard dans l"année sur la notion d"invariant de boucle, mais on peut noter que six?t[g..d], avecgetdinclus, et que l"on constate ensuite quexest, par exemple, strictement à droite du milieumdu tableau, on a forcémentx?t[m+ 1..d]. Par ailleurs, il est indispensable qu"à chaque boucle, la différenceind_d-ind_gdécroisse strictement afin que la bouclewhiles"arrête. Complexité :Soitple nombre maximal d"itérations de la bouclewhile. Comme toutes les instructions en dehors et dans la boucle sont enO(1), la fonction a donc une complexité temporelle dans le pire des cas enO(p). Déterminons un majorant du nombre maximal d"itérationspen fonction de la longueurndu tableaut.

Considérons la variableind_d-ind_g.

au début : ind_d-ind_g=n-1 apr èsune itération : ind_d-ind_g=?n-12 apr èsdeux itérations : ind_d-ind_g=??n-12 ?2 k Or, n2 k<1??n <2k??ln n < k×ln2??k >ln nln2??k > log n(en base 2).

Ainsi, dès quek=?log n?, on a forcémentind_d= =ind_g . On itère une dernière fois et on sort

p=O(log n).

La complexité temporelle dans le pire des cas

de la fonctionrecherche_dichotomique,

somme d"opérations enO(1)et d"une boucle enO(log n), est donc enO(log n).Lycée Michelet - classes de PCSI6

2021-2022CoursInformatiqueIIIE xercices

Q1Donner la complexité temporelle dans le pire des cas de la fonction suivante :48deff 1(n):49x= 0 50fori i nr ange(n):51forj i nr ange(n):52x+ =1 53returnx

Q2Donner la complexité temporelle dans le pire des cas de la fonction suivante :56deff 2(n):57x= 0 58fori i nr ange(n):59forj i nr ange(i):60x+ =1 61returnx

Q3Donner la complexité temporelle dans le pire des cas de la fonction suivante :64deff 3(n):65x,i = 0 ,n 66whilei > 1 :67x+ =1 68i/ /=2 69returnx

Q4Donner la complexité temporelle dans le pire des cas de la fonction suivante :72deff 4(n):73x,i = 0 ,n 74whilei > 1 :75forj i nr ange(n):76x+ =1 77i/ /=2 78returnx

Q5Donner la complexité temporelle dans le pire des cas de la fonction suivante :81deff 5(n):82x,i = 0 ,n 83whilei > 1 :84forj i nr ange(i):85x+ =1 86i/ /=2 87returnx

Q6Donner la complexité temporelle dans le pire des cas de la fonction suivante :90deff 6(n):91x= 0 92fori i nr ange(n):93j= 0 94whilej * j < i :95x+ =1 96j+ =1 97returnx Lycée Michelet - classes de PCSI7

2021-2022CoursInformatiqueCorrigé

Q1Le nombrenest une mesure de la taille du problème considéré.

L"affectationx= 0 est enO(1).Dansle pire des cas, pour chacun desn2couples d"indices(i,j), on réalise enO(1)l"ins-

tructionx+= 1 . La complexité temporelle des boucles imbriquées est donc enO(n2). Par somme,la complexité temporelle dans le pire des casde la fonctionf1est en

O(n2).

Q2Le nombrenest une mesure de la taille du problème considéré.

L"affectationx= 0 est enO(1).

Dansle pire des cas, déterminons le nombre de couples d"indices(i,j)pour lesquels on réalise enO(1)l"instructionx+= 1 : n-1? i=0i-1? j=01 =n-1? i=0i=(n-1)n2 Comme(n-1)n2=O(n2),la complexité temporelle dans le pire des casde la fonction f2est enO(n2). Q3Le nombrenest une mesure de la taille du problème considéré. Les affectationsx,i= 0 ,nsont réalisées enO(1). Pour chaque boucle suri, on réalise enO(1)les instructionsx+= 1; i//= 2 . Ainsi, sip est le nombre de boucles suri, la complexité temporelle dans le pire des cas est enO(p).

Déterminons une majoration dep.

(en base 2). Ainsi,p=O(log n). Finalement,la complexité temporelle dans le pire des casde la fonctionf3est en

O(log n).

Q4Le nombrenest une mesure de la taille du problème considéré. Les affectationsx,i= 0 ,nsont réalisées enO(1). Pour chaque valeur dei, on réalisenboucles surj. Pour chacune de ces boucles, on réalise enO(1)l"instructionx+= 1 . Ainsi, la boucle surj a une complexité temporelle enO(n). Pour chaque boucle suri, on réalise enO(1)l"instructioni//= 2 . Ainsi, sipest le nombre de boucles suri, la complexité temporelle dans le pire des cas des boucles imbriquées est enO(np). On montre, comme à la question précédente, quep=O(log n). Finalement,la complexité temporelle dans le pire des casde la fonctionf4est en

O(nlogn).

Q5Le nombrenest une mesure de la taille du problème considéré. Les affectationsx,i= 0 ,nsont réalisées enO(1). Pour chaque valeur dei?J0,nK, on réaliseiboucles surj. Quand, pour une valeur dei donnée, toutes les boucles surjsont exécutées, l"instruction eni//= 2 , enO(1), divisei par2, et donc le nombre de boucles surjpar2. Ainsi, P ouri==n, on anboucles surjLycée Michelet - classes de PCSI8

2021-2022CoursInformatique-P ouri==n//2, on an//2boucles surj, nombre majoré parn/2

P ouri== (n//2)//2, on a(n//2)//2boucles surj, nombre majoré parn/22 -Pouri== 1, le nombre de boucles surjest majoré parn/2pavecp=log n. A ce moment-là, on est sorti de la boucle suri. Par conséquent, le nombre totalSde boucles sur(i,j)est majoré par n+n2 +n2

2+···+n2

p-1+n2 p Comme n2 +n2

2+···+n2

p-1) p1-12 Comme l"instructionx+= 1 de la boucle enjest réalisée enO(1), la complexité temporelle dans le pire des cas des boucles imbriquées surietjest enO(n). Finalement,la complexité temporelle dans le pire des casde la fonctionf5est en O(n). Q6Le nombrenest une mesure de la taille du problème considéré.

L"affectationx= 0 est enO(1).

Dansle pire des cas, déterminons le nombre de couples d"indices(i,j), donc le nombre total de boucles, pour lesquels on réalise enO(1)les instructionsj = 0, x += 1etj += 1. On supposen≥2. On a le tableau de valeurs suivant :i012345678910...n-1 nbre. de j0111222223...? ⎷n-2?Notonsnkle nombre de fois qu"apparaîtk?J1,?⎷n-2?Kdans la ligne du nombre dej (on lit dans le tableaun1= 3etn2= 5). Le nombreStotal de boucles est donné par la somme du nombre d"indicesj: S= 1×n1+ 2×n2+···+?⎷n-2? ×n?⎷n-2?

On peut majorerSen majorant lesnk.

Pour chaquek?J1,?⎷n-2?K, considéronsiktel quek2=iketik+1tel que(k+1)2=ik+1.

Alors,nk=ik+1-ik= (k+ 1)2-k2= 2k=⎷i

k<⎷n. Ainsi,S <(1 + 2 +···+?⎷n-2?)⎷n <(1 + 2 +···+⎷n)⎷n.

Donc,S <⎷n(⎷n+1)2

⎷n < ⎷n(⎷n+⎷n)2 ⎷n. Donc,S < n⎷n. Ainsi,la complexité temporelle dans le pire des casde la fonctionf6est enO(n⎷n). Remarque :On peut aussi minorerSen minorant lesnkpar1:

Alors,S≥1 + 2 +...+?⎷n-2?.

On peut montrer par récurrence que :?n?N,1 + 2 +...+⎷n≥n⎷4n+53 Or, n⎷4n+53 ≥23 n⎷n. Donc,S≥1 + 2 +...+?⎷n-2? ≥23 ?(n-2)??⎷n-2? Ainsi, de façon asymptotique,Sest minorée par une fonction de la formekn⎷naveck réel. On note :S= Ω(n⎷n).

Ceci signifie que, quelque soit l"entrée de taillen, le temps d"exécution pour cette entrée est

au moins égal à un multiple constant den⎷n. Quand le temps d"exécution est asymptotiquement à la fois minoré et majoré par un multiple constant d"une fonction den, icin⎷n, on dit quela complexité temporelle de la fonctionf6est enΘ(n⎷n).Lycée Michelet - classes de PCSI9quotesdbs_dbs29.pdfusesText_35

[PDF] calcul de complexité python

[PDF] masse et quantité de matière exercice

[PDF] l'alcool utilisé comme antiseptique local peut être

[PDF] production primaire nette

[PDF] productivité nette de l'écosystème

[PDF] production primaire et secondaire

[PDF] productivité nette de l écosystème

[PDF] taux d'évolution calcul

[PDF] taux d'endettement entreprise

[PDF] numero ine sur internet

[PDF] inscription lycée hors secteur

[PDF] nombre de mole formule

[PDF] nombre de mole d'un gaz

[PDF] nombre d'oxydation exercices corrigés

[PDF] exercices priorités opératoires 5ème pdf