Next PDF List

Chapter 5Complexit´e d"un algorithme?Important :Ce chapitre est beaucoup plus de l"informatique que des math´ematiques etse prˆete mal `a des notes succinctes comme le reste du cours.

En cons´equence une partie desconsid´erations du coursne sont pas pr´esentes ci-dessous.5.

1) IntroductionD´efinition 1(Algorithme)Unalgorithmeest un proc´ed´e automatique pour r´esoudre unprobl`eme en un nombre fini d"´etapes.?Le but de ce chapitre est de donner des outils pour comparer diff´erentes solutions algorith-miques `a un probl`eme donn´e.?Pour quantifier les performances d"un algorithme on doit se munir d"une notion detaillesur les entr´ees.?Lacomplexit´ed"un algorithme est la quantit´e de ressources n´ecessaires pour traiter desentr´ees.

On la voit comme une fonction den, la taille de l"entr´ee.?Les principales ressources mesur´ees sont letemps(nombre d"instructions utilis´ees) etl"espace(quantit´e d"espace m´emoire n´ecessaire).?On distingue plusieurs types d"analyses de complexit´e : l"analyse dans lemeilleur des cas,lepire des caseten moyenne.

Pour ce cours on ´etudie exclusivement le pire des cas.

DoncsiT(A) est le nombre d"instructions n´ecessaires pour que l"algorithme fasse ses calculs surl"entr´eeA, on s"int´eresse `a la suite (tn)n?Nd´efinie partn= max|A|=nT(A),o`u|A|est la taille de l"entr´eeA.?Il n"est souvent pas pertinent d"essayer de quantifier trop pr´ecis´ementtn, vu qu"on raisonneau niveau de l"algorithme et non d"une implatation.

On se contente donc d"estimertnavecun ordre de grandeur en Θ ouO. Un r´esultat typique : la complexit´e de l"algorithme de tripar insertion est enO(n2).12CHAPTER 5. COMPLEXIT´E D"UN ALGORITHME5.

2) Principes g´en´eraux?(ligne la plus effectu´ee)La fa¸con la plus simple d´evaluer la complexit´e d"un algorithmeest la suivante : un programme est constitu´e d"un nombre fini de lignes.

Appelons-les?1`a?k.Soitn1 nkle nombre de fois qu"elles sont effectu´ees. La complexit´e de l"algo est??ini.Soit?jl"une des lignes qui est effectu´ee le plus souvent.

Si toutes les lignes s"effectuent entempsO(1), la complexit´e de l"algorithme est major´ee parknjO(1) soitO(nj).?Attention aux instructions qui appellent d"autres fonctions et qui ne s"´ex´ecutent pas entemps constant.?Quand le programme contient une ou plusieurs boucles imbriqu´ees, on se retrouve `a estimerdes sommes.

On peut souvent utiliser le th´eor`eme suivant.Th´eor`eme 2(Sommation)Soit(fn)n≥0et(gn)n≥0deux suites positives, avecfn? O(gn).On suppose de plus que?ni=0gin"est pas toujours nul.

Alorsn?i=0fi=O?n?i=0gi?.Plus g´en´eralement, siα:N→Nest une application croissante qui tend vers l"infini eta?N:α(n)?i=afi=O((α(n)?i=agi)).?On en d´eduit le r´esultat suivant qui est tr`es utilis´e en pratique, vu que les complexit´es ontsouvent cette forme :Th´eor`eme 3(nalnbn)Soit(fn)n≥0une suite telle quefn? O(nalnbn)aveca,b?R+.Alors?ni=0fi? O(na+1lnbn).

Le r´esultat est encore vrai si on remplace lesOpar desΘ.5.

3) Classes de complexit´es classiquesOn voit souvent apparaˆıtre les complexit´es suivantes :• O(logn) Ce sont des algorithmes tr`es rapides.

Exemples typiques : recherche di-chotomique, exponentiation rapide,etc.• O(n) (on ditlin´eaire).

Typiquement quand on parcourt un tableau ou une liste unnombre born´e de fois : recherche dans un tableau, minimum d"une liste,etc.• O(nlogn).

Vous l"avez principalement vu pour les algorithmes efficaces de tri : trirapide, tri fusion, tri par tas,etc.Cette complexit´e apparaˆıt r´eguli`erement lorsque l"on faitdu "diviser pour r´egner".• O(n2) (on ditquadratique).

Quand on manipule des tableaux `a deux dimensions, ouqu"on effectue un assez grand nombre de calculs sur un tableau `a une dimension : somme dedeux matrices, transpos´ee d"une matrice, tri insertion, tri bulle, tri selection,etc.5.4.

TROIS EXEMPLES IMPORTANTS35. 4) Trois exemples importants5.4.

1) Dichotomie?On veut chercher si un entierxest dans un tableau tri´eTde taillen.int dicho(int *t, int n, int x) {int a,b,mid;a = 0; b = n;while(a <= b) {mid = (b+a)/2;if (t[mid] == x)return 1;if (t[mid] < x)a = mid + 1;elseb = mid - 1;}return 0;}Th´eor`eme 4La complexit´e de l"algorithmedichoest enO(logn).5.4.

2) Exponentiation rapide?On veut calculerxn, o`un?Nmesure la taille de l"entr´ee.float puissance(float x,int n) {if (n==0)return 1;if (n&1)return x*puissance(x,n-1);return puissance(x*x,n/2);}Th´eor`eme 5La complexit´e de l"algorithmepuissanceest enO(logn).5.4.

3) Sch´ema de H

orner?On veut calculerP(x), o`uxest un r´eel (float) etPest un polynˆome de degr´en, r´epr´esent´epar un tableau : siP(X) =a0+a1X+ +anXn, alors pour touti? {0, ,n}on aP[i] =ai.float Horner(float P[], int n, float x) {int i; float r = P[n];for(i=n-1;i>=0;i--)r = (r*x)+P[i];return r;}4CHAPTER 5.

COMPLEXIT´E D"UN ALGORITHMETh´eor`eme 6La complexit´e de l"algorithmeHornerest enO(n).