1 Les algorithmes: complexité et notation asymptotique

1

Les algorithmes: complexité et notation asymptotique

2

Analyse d'algorithmes

Notation O( )Comparer deux algorithmes

Soient deux algorithmes A1 et A2 Base de comparaison

Mesure indépendante de l'implémentation : TAILLE D'UN PROBLÈME (n)

Temps d'exécution d'un algorithme = fonction(taille du problème) i.e. f(n)

Exemples : Taille d'une liste (recherche d'un élément dans une

liste) Nombre de nœuds d'un arbre (impression d'un arbre) Taille d'un tableau (tri)

3

Analyse d'algorithmes

Notation O( )

4

Analyse d'algorithmes

Notation O( )

5

Analyse d'algorithmesNotation O( )

Exemple: évaluer le temps d’ exécution d’algorithme suivant:

void TriSelection(int tab[MAXTAB], int n){ int PositionMin, temp,i,j;

for (i = n-1; i > 0; i--) { PositionMin = i;

for (j = 0; j < i; j++) {

if (tab[j] < tab[PositionMin]) {

PositionMin = j; }

} temp = tab[i]; tab[i] = tab[PositionMin]; tab[PositionMin] = temp;}

}

Boucle externe

Boucle interne

6

Analyse d'algorithmes

Notation O( ) Exemple (suite)

for (i = n-1; i>0; i--){

Coût b1 /* PositionMin = i */Coût i*a; /* pour exécuter la boucle interne*/Coût b2; /* pour l'échange de tab[i] et tab[PositionMin] */

}

Boucle externe

7

Analyse d'algorithmesNotation O( )

Exemple (suite)

b=b1 +b2 n-1S = ∑ (ai + b) i=1 (n-1)nS = a + (n-1)b 2 a aS = n2 + (b )n - b 2 2

Le programme est O(n2)

8

Analyse d'algorithmes

Notation O( )

Définition du O( )

Nous dirons que f(n) est O(g(n)) s'il existe deux constantes positives K et n0 tel que |f(n)| <= K |g(n)| pour tout n>n0

Conclusion : Évaluer le coût d'un algorithme = Rechercher la fonction

g(n) qui est la plus proche au dessus ou égale a f(n)

9

Analyse d'algorithmesLa recherche séquentielle

A. Données pas triées

recherche(3) = 1 comparaison recherche(10) = 11 comparaisons recherche(12) = 7 comparaisons recherche(13) = 11 comparaisons

meilleur cas = O(1) pire cas = O(n) en moyenne = O(n/2) absences = O(n)

10

Analyse d'algorithmesLa recherche séquentielle

B. Données triées

recherche(1) = 1 comparaison recherche(14) = 11 comparaisons recherche(8) = 6 comparaisons recherche(13) = 11 comparaisons

meilleur cas = O(1) pire cas = O(n) en moyenne = O(n/2) absences = O(n/2)

11

12

13

Analyse d'algorithmesLa recherche binaire

implantation en tableau = accès direct à n’importe quel élément

en regardant tout de suite au milieu, on peut éliminer la moitié des données

14

Analyse d'algorithmesLa recherche binaire: 10?

1 2 3 4 6 8 9 10 11 12 14

9 10 11 12 14

9 10

10

11 n

5 n/2

2 n/4

1 n/8

15

Analyse d'algorithmesAlgorithme récursif

récursion ? conditions d’arrêt ? convergence ?

1 2 3 4 6 8 9 10 11 12 14

16

Analyse d'algorithmesAlgorithme récursif - récursion

X Є tab[debut..fin]

si x = tab[milieu] (condition d’arrêt) si x < tab[milieu] et x Є tab[debut..milieu-1] si x > tab[milieu] et x Є tab[milieu+1..fin]

1 2 3 4 6 8 9 10 11 12 14

17

Analyse d'algorithmesAlgorithme récursif - conditions d’arrêt

X € tab[debut..fin] si debut > fin X Є tab[debut..fin] si x = tab[milieu]

1 2 3 4 6 8 9 10 11 12 14

18

Analyse d'algorithmesAlgorithme récursif - convergence

1 2 3 4 6 8 9 10 11 12 14

9 10 11 12 14

9 10

10

19

Analyse d'algorithmesAlgorithme récursif

1 2 3 4 6 8 9 10 11 12 14

int rechercheBinRec(int tab[ ], int val, int debut, int fin){ int milieu;

if (debut > fin) return -1;else { milieu= (debut + fin)/2; if( val == tab[milieu]) return milieu; else

{ if( val < tab[milieu])

return(rechercheBinRec(tab,val,debut, milieu-1)); else

return(rechercheBinRec(tab,val,milieu+1,fin));}

}}

20

Analyse d'algorithmesAlgorithme récursif

Recherche séquentielle (données triées) Données présentes: O(n/2) Données absentes: O(n/2)

Recherche binaire (données triées) Données présentes: O(log n) Données absentes: O(log n)

21

Analyse d'algorithmes

Algorithme récursif

Il vaut bien mieux implanter cet algorithme de manière itérative, car

la fonction se rappelle jusqu'à trouver la position désirée, puis seulement on effectue les dépilages, alors que l'on n'a plus besoin des états intermédiaires qui ont été mémorisés par la récursivité puisque le problème est résolu.