IntroductionDfinition de la complexitTypes de complexit algorithmiqueNotation asymptotiqueCalcul de Landau de complexitEtude des algorithmes du tri

Complexit algorithmique

1

Introduction

Comparer deux algorithmes ralisant le mme traitement.

Mesurer les performances dun algorithme : valuation des ressources ncessaires pour l'excution de l'algorithme (temps)

L'analyse thorique de l'efficacit d'un algorithme se fait sans tenir compte du : -langage de programmation

-compilateur et systme d'exploitation -puissance de lordinateur

Complexit algorithmique

2

Dfinition de la complexit:

La complexit d'un algorithme est la mesure du nombre d'oprations fondamentales qu'il effectue sur un jeu de donnes.

Elle est exprime comme une fonction qui dpend de la taille du jeu de donnes.

Un algorithme est dit optimal si sa complexit est la complexit minimale parmi les algorithmes de sa classe.

Complexit algorithmique

3

Type de complexit:

Complexit au meilleur: C'est le plus petit nombre d'oprations qu'aura excuter l'algorithme sur des jeux de donnes de taille n (optimiste).

Complexit moyenne: C'est la moyenne de Complexit de l'algorithme sur des jeux de donnes de taille n (moyenne).

Complexit au pire: Cest le plus grand nombre d'oprations qu'aura excuter l'algorithme sur des jeux de donnes de taille n (pessimiste).

Complexit algorithmique

4

La notation DE LANDAU O est celle qui est le plus communment utilise pour expliquer formellement les performances d'un algorithme.

Cette notation exprime la limite suprieure d'une fonction dans un facteur constant.

T(n) = O(f(n)) veut dire qu'il existe une constante c > 0 et une constante n0 > 0 tel que pour

tout n > n0 T(n)

Les rgles de la notation O : Les termes constants :

O(c) = O(1) Les constantes multiplicatives sont omises :

O(cT ) = c O(T) = O(T) L'addition est ralise en prenant le maximum : O(T1 + T2) = O(T1) + O(T2) = max(O(T1),O(T2)) La multiplication reste inchange:

O(T1)O(T2) = O(T1T2)

6

Complexit algorithmique

Cas particulier de f(n):

Les algorithmes usuels peuvent tre classs en un certain nombre de grandes classes de complexit.

Constante : O(1)Logarithme : O(logn)Linaire : O(n)Quasilinaire: O(nlogn)Quadratique : O(n2)Cubique : O(n3)Polynomiale : O(np)avec p>0Expentielle :O(an)avec n>1,a>1

Notation de Landau

7

Courbes des remarquables f(n):

Notation de Landau

8

Le problme du tri:

Le "tri" est l'opration qui consiste ordonner un ensemble d'lments.

Algorithme tri: Entre: Un tableau dentiers de taille N Sortie: Le mme tableau, tri par ordre croissant

Les algorithmes de tri

9

Le tri insertion: Principe : Cette mthode de tri est identique celle utilise pour trier ses

cartes dans un jeu : on prend une carte, puis la deuxime que l'on place aprs l'avoir compar avec la premire, ensuite la troisime que l'on insre sa place en fonction des deux premires et ainsi de suite.

Le principe gnral est donc de considrer que les (i-1) premires cartes, sont tries et de placer la i me carte, sa place parmi les (i-1) dj tries, et ce jusqu ce que i = N.

Les algorithmes de tri

10

Complexit algorithmique

11

Tri par insertion:

Procdure insertion (T[n]) Pour iallant de 1 jusqu' n-1 faire

x T[i]j i -1 tant que (j >= 0) et (T[j] > x) faire

T[j + 1] T[j] j j -1

FinTantque T[j + 1] x

FinPour

Complexit algorithmique

12

Complexit algorithmique

13

Calcul de la complexit:

Au meilleur des cas : O(n)

Au pire des cas : O(n2)

Remarque:

L'fficacit du tri par insertion est meilleure si le tableau possde dj un certain ordre.

Recherche dichotomique

14

La recherche dans un tableau est une opration de base utilse dans plusieurs algorithmes .

Principe:Il s'agit de trouver dans un tableau l'indice correspondant une valeur donne. Le principe de recherche dichotomique ne s'applique que pour des tableaux tris. Soit X l'lment recherch dans un tableau T dont les bornes infrieure et suprieure sont indiceInf et indiceSup. On appelle milieu (indiceInf + indiceSup) Div 2. Principe de la recherche de l'indice X :Si T[milieu] > X, alors l'indice de X, s'il existe, est compris entre indiceInf et milieu-1Si T[milieu] = X, l'indice est trouv.Si T[milieu] < X, alors l'indicede X, s'il existe, est compris entre milieu+1 et indiceSup

Recherche dichotomique

15

Fonction RechercheDicho(Tableau Tab[n] :entier, indiceInf ,indiceSup,X :entier) : entier Variable

Trouv: boolean; mileu:entier;Debut

Trouve false ; Tant que ((trouve=false) ET (indiceInf

Recherche dichotomique

16

Complexit:Le pire des cas pour la recherche d'un lment est de continuer les divisions jusqu obtenir un tableau de taille 1. La complexit = log2(n)

Le Tri-slectionPrincipe:Pour classer n lments, on parcourt le tableau pour rechercher le plus petit

lment que l'on permute alors avec le premier lment.

Le mme traitement est effectu avec le tableau ayant le premier lment en moins.

Cette opration est rpte jusqu' ce que tous les lments soient classs.

Complexit algorithmique

17

Le Tri-slectionExemple:Soit le tableau d'entiers suivant :6 2 8 1 5 3 7 9 4 0L'lment le plus petit se trouve en 9me position 6 2 8 1 5 3 7 9 4 0On change l'lment le plus petit (en 9me position) avec le premier :0 2 8 1 5 3 7 9 4 6Le premier lment du tableau est dsormais forcment le plus petit. On continue donc

en considrant le mme tableau, en ignorant son premier lment :0 2 8 1 5 3 7 9 4 6Toute l'astuce de l'algorithme est l : on ignore volontairement dans la suite du

traitement les lments que l'on a dplacs au dbut du tableau.De mme, on repre l'lment le plus petit en ignorant le premeir et on l'change avec

le deuxime :0 1 8 2 5 3 7 9 4 6

Complexit algorithmique

18

L'ALGORITHME- Tri slectionExemple:

Et ainsi de suite, en ignorant chaque fois les lments dj tris (en bleu).0 1 2 8 5 3 7 9 4 6

0 1 2 3 5 8 7 9 4 6

0 1 2 3 4 8 7 9 5 6

0 1 2 3 4 5 7 9 8 6

0 1 2 3 4 5 6 9 8 7

0 1 2 3 4 5 6 7 8 9

0 1 2 3 4 5 6 7 8 9 le tableau est tri !

Complexit algorithmique

19

L'ALGORITHME- Tri slectionVariables:

i, j: entier ;temp, petit : entier ;tableau tab[n] : entier ;

Dbut Pour i allant de 0 jusqu' n-2 faire

petiti; Pour j de i+1 n-1 faire

Si t[j] < t[petit] alors petit j ; Fin si Fin pour

tempt[petit]; t[petit] t[i];

t[i] temp; Fin pour

Fin .

Complexit algorithmique

20

L'ALGORITHME- Tri slection

On effectue environ n(n1)/2 comparaisons ;

La complexit de notre algorithme est quadratique en O(n2 )

Complexit algorithmique

21

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21