La complexité des algorithmes PDF

Ici la complexité de nos algorithmes peuvent être calculer en nombre de comparaisons effectuées. — Définition : Tri par comparaison [2 p.178] On s'autorise

Algorithmes de tri

Dans le pire cas ou en moyenne la complexité du tri par sélection est en O(n2). Page 25. Plan. 1. Introduction. 2. Algorithmes de tri. Tri par sélection. Tri

La complexité des algorithmes

Algorithme 2 : La complexité du tri par insertion. Complexité au pire et en moyenne. Si l'insertion du pieme élément =⇒ le décalage des p − 1 éléments qui

Diviser pour Régner : Complexité et Tri Fusion

Nous allons étudier la complexité des algorithmes étudiés. Il s'agit en général

Algorithmes de tri

On considérera toujours la complexité en termes de comparaisons entre deux valeurs du tableau. Dans notre algorithme à chaque comparaison entre deux valeurs du

Algorithmes de tri 1

18 oct. 2017 Ceci minimise la complexité spatiale. Exemple : tri à bulles de [41

Informatique en CPGE (2018-2019) Algorithmes de tri 1 Introduction

Une opération de tri consomme un temps de calcul important sur un ordinateur et il donc nécessaire d'étudier la complexité temporelle des différents algorithmes

Tri par tas

1. Définition de cette structure de données. 2. Étude de la fonction Entasser (principe algorithme

Algorithmes de tri interne (5) [tr] Méthodes par partitions

Combiner : la complexité de cette étape est celle de l'algorithme de fusion qui est de Θ(n) pour la construction d'un tableau solution de taille n. Par

La complexité des algorithmes

Algorithme 1 : le tri par sélection (2/3) minimum du sous-tableau restant à trier éléments triés éléments non triés. Étape 1 : 7 8 15 5 10.

Algorithmes de tri

Complexité du tri par sélection. Tri par sélection. Données : Un tableau de n entiers T. Résultat : Le tableau T trié pour chaque i allant de 1 `a n ? 1

Leçon 903 : Exemples dalgorithmes de tri. Correction et complexité

Ici la complexité de nos algorithmes peuvent être calculer en nombre de comparaisons effectuées. — Définition : Tri par comparaison [2 p.178] On s'autorise

Diviser pour Régner : Complexité et Tri Fusion

Par exemple pour étudier la complexité d'un algorithme de tri sur des listes

Algorithmique Trier et Trouver

Algorithme de recherche d'un élément dans un tableau Algorithme (RechDichoIt recherche dichotomique itérative) ... Complexité du tri par Fusion (1).

Algorithmes de tri interne (5) [tr] Méthodes par partitions

Par conséquent l'algorithme de fusion a une complexité en ?(h ? g). Page 5. Unisciel algoprog – tr00cours5-texte

Algorithmes de tri

4 Calcul de la mediane. 6. 5 Complexité optimale d'un algorithme de de tri. 6. 1. Page 2. Lycée Marceau. Tri. MP 2020/2021. Soit tab un tableau (à une dimension

TD 2 : Complexité et algorithmes de tri

TD 2 : Complexité et algorithmes de tri. 21 septembre 2017. 1 Le tri par tas. Le tri par tas utilise une structure de données appelée tas binaire.

ALGORITHMES DE TRIS

C'est un algorithme hybride dérivé des algorithmes tri fusion et tri par insertion que nous étudierons dans la suite de ce chapitre. La complexité

La complexité des algorithmes

Amélie Lambert

Cnam

MPRO - Mise à niveau

Amélie Lambert (Cnam)MPRO - Mise à niveau 1 / 49

1Définition d"un algorithme

2Un exemple

3Évaluation des algorithmes

4Complexité en temps

5Exemples de complexité d"algorithmes

Amélie Lambert (Cnam)MPRO - Mise à niveau 2 / 49

Définition d"un algorithme

Procédure de calcul bien définie qui prend en entrée une valeur ou un ensemble de valeurs et qui donne en sortie une valeur ou un ensemble de valeurs, c"est donc une séquence d"étapes de calculs qui transforme l"entrée en sortie. (Cormen, Leiserson, Rivert) Amélie Lambert (Cnam)MPRO - Mise à niveau 3 / 49

Etapes de conception d"un algorithme

Phase 1

Énoncé du p roblème(Sp écification)

Phase 2

Élab orationde l"algo rithme

Phase 3

Vérification

Phase 4

Mesure de l"efficacité (Complexité)

Phase 5

Mise en o euvre(Programmation)

Amélie Lambert (Cnam)MPRO - Mise à niveau 4 / 49

1Définition d"un algorithme

2Un exemple

3Évaluation des algorithmes

4Complexité en temps

5Exemples de complexité d"algorithmes

Amélie Lambert (Cnam)MPRO - Mise à niveau 5 / 49

Exemple : le tri d"un tableau

Énoncé du problèmeEntrée :Un tableau denentiersT=T[0];T[1];:::T[n1], la taille du problème est doncn.Sortie :Permutation du tableauT0=T0[0];T0[1];:::T0[n1], tel

queT0[0]T0[1]:::T0[n1](trié par ordre croissant).Amélie Lambert (Cnam)MPRO - Mise à niveau 6 / 49

Algorithme 1 : le tri par sélection (1/3)

Principe

TANT QUEil reste plus d"un élément non triéfaire 1.

Chercher le plus p etitpa rmiles non triés.

2. Échanger le p remierélément non trié avec le plus p etittrouvé. FAIT Amélie Lambert (Cnam)MPRO - Mise à niveau 7 / 49

Algorithme 1 : le tri par sélection (2/3)

minimum du sous-tableau restant à trier

éléments triés

éléments non triés

Étape 1 :7815510

Étape 2 :5815710

Étape 3 :5715810

Étape 4 :5781510

Étape 5 :5781015

Étape 6 :5781015

Amélie Lambert (Cnam)MPRO - Mise à niveau 8 / 49

Algorithme 1 : le tri par sélection (2/3)

minimum du sous-tableau restant à trier

éléments triés

éléments non triés

Étape 1 :7815510

Étape 2 :5815710

Étape 3 :5715810

Étape 4 :5781510

Étape 5 :5781015

Étape 6 :5781015

Amélie Lambert (Cnam)MPRO - Mise à niveau 8 / 49

Algorithme 1 : le tri par sélection (2/3)

minimum du sous-tableau restant à trier

éléments triés

éléments non triés

Étape 1 :7815510

Étape 2 :5815710

Étape 3 :5715810

Étape 4 :5781510

Étape 5 :5781015

Étape 6 :5781015

Amélie Lambert (Cnam)MPRO - Mise à niveau 8 / 49

Algorithme 1 : le tri par sélection (2/3)

minimum du sous-tableau restant à trier

éléments triés

éléments non triés

Étape 1 :7815510

Étape 2 :5815710

Étape 3 :5715810

Étape 4 :5781510

Étape 5 :5781015

Étape 6 :5781015

Amélie Lambert (Cnam)MPRO - Mise à niveau 8 / 49

Algorithme 1 : le tri par sélection (2/3)

minimum du sous-tableau restant à trier

éléments triés

éléments non triés

Étape 1 :7815510

Étape 2 :5815710

Étape 3 :5715810

Étape 4 :5781510

Étape 5 :5781015

Étape 6 :5781015

Amélie Lambert (Cnam)MPRO - Mise à niveau 8 / 49

Algorithme 1 : le tri par sélection (2/3)

minimum du sous-tableau restant à trier

éléments triés

éléments non triés

Étape 1 :7815510

Étape 2 :5815710

Étape 3 :5715810

Étape 4 :5781510

Étape 5 :5781015

Étape 6 :5781015

Amélie Lambert (Cnam)MPRO - Mise à niveau 8 / 49

Algorithme 1 : le tri par sélection (3/3)

static voidtri_selection(int[] T) { inti,ind_min,k; inttemp; for(i=0;iT[i] = T[ind_min];

T[ind_min] = temp;

Amélie Lambert (Cnam)MPRO - Mise à niveau 9 / 49

1Définition d"un algorithme

2Un exemple

3Évaluation des algorithmes

4Complexité en temps

5Exemples de complexité d"algorithmes

Amélie Lambert (Cnam)MPRO - Mise à niveau 10 / 49

Évaluation d"un algorithme (1/2)

Mesure d"efficacité par rapport à la taille de l"entrée, 2 critères :Temps d"exécution: nomb red"op érationsélémentaires

Taille

: mémoire o ccupée Ces mesures varient en fonction des données d"entrée de l"algorithme.

Exemple (temps d"exécution) :Déterminer si un entiernest premier?Sin=1148? non, divisible par 2Sin=1147????(3137)Amélie Lambert (Cnam)MPRO - Mise à niveau 11 / 49

Évaluation d"un algorithme (2/2)

Efficacité=

nombre d"opérations en fonction de la taille des données On peut l"évaluer dans 3 cas :Dans le meilleur des cas (peu d"intérêt),

Dans le pire des cas,

En moyenne.

Amélie Lambert (Cnam)MPRO - Mise à niveau 12 / 49

Exemples

Exemple 2 : recherche des deux villes les plus proches (N villes) I Problème :Étant donné un ensemble de villes séparées par des distances données, trouver les deux villes les plus proches. IDonnéesdistances entre chaque paire de villes :N2données.

IÉnumération et recherche du minimumN2distances possibles.Exemple 3 : le voyageur de commerce (N villes)

I Problème :Étant donné un ensemble de villes séparées par des distances données, trouver le plus court chemin qui relie toutes les villes. IDonnées :distances entre chaque paire de villes :N2données. IÉnumération et évaluation des(N1)!tournées possibles et sélection de la plus économique. Amélie Lambert (Cnam)MPRO - Mise à niveau 13 / 49

Comparaison

Temps de calcul si 10

9secondes par comparaisonNombre de villesN1020304050

Nb donnéesN210040090016002500

Min deN2nb0.1s0.4s0.9s1.6s2.5sMin de(N1)!nb363s> 3 ans10

16ans10

30ans10

45ansAmélie Lambert (Cnam)MPRO - Mise à niveau 14 / 49

1Définition d"un algorithme

2Un exemple

3Évaluation des algorithmes

4Complexité en temps

5Exemples de complexité d"algorithmes

Amélie Lambert (Cnam)MPRO - Mise à niveau 15 / 49

Complexité des algorithmes

La notion de complexité formalise la notion d"efficacité d"un programme : capacité à fournir le résultat attendu dans un temps minimalElle consite en la détermination des ressources nécéssaires en temps de calcul, mémoire.On se donne un modèle de machine avec une mémoire infinie et munie d"opérations dont le temps d"exécution (coût élémentaire) est constant

(ou majoré par une constante).On cherche à exprimer le coût de l"algorithme en fonction de la taille

des données. Amélie Lambert (Cnam)MPRO - Mise à niveau 16 / 49

Notations

L"ensembleDn=fdonnées de tailleng

L"exécution de l"algorithme sur une donnéedest modélisée par une séquence finie d"opérations élémentaires de la machine : addition, multiplication, test, ...le coût de l"exécutioncoutA(d)= nombre d"exécution de chaque opération de l"algorithmeAsur la donnéed En général, on restreint le nombre d"opérations élémentaires étudiées Amélie Lambert (Cnam)MPRO - Mise à niveau 17 / 49

Complexité dans le pire des cas

max A(n) =maxd2DncoutA(d)Borne supérieure du coût,

Assez facile à calculer,

Souvent réaliste.

Amélie Lambert (Cnam)MPRO - Mise à niveau 18 / 49

Complexité en moyenne

p (d) = probabilité de la donnée d Moy

A(n) =X

d2Dnp(d)coutA(d) I

Connaître la distribution des données,

Souvent difficile à calculer,

I Intéressant si le comportement usuel de l"algorithme éloigné du pire des cas. Amélie Lambert (Cnam)MPRO - Mise à niveau 19 / 49

Evaluation de la complexité d"un algorithme

Coût d"une instruction conditionnellemaximum des coûts de

chacune des branches de l"instruction conditionnelle;Coût d"un appel de procédure=somme du coût de l"appel (i.e. coût

du corps de la procédure);Algorithme itératif: coût d"une itération =somme des coûts de

chaque terme de l"itération;Algorithme récursif: on exp rimele coût de l"algo rithmeen fonction du

coût des appels récursifs. On obtient ainsi une équation de récurrence sur la fonction de coût. Amélie Lambert (Cnam)MPRO - Mise à niveau 20 / 49

Exemple : Le tri par sélection

static voidtri_selection(int[] T) { inti,ind_min,k; inttemp; for(i=0;iT[i] = T[ind_min];

T[ind_min] = temp;

}Pire des cas :

4(n2) +2n2X

i=0(ni1)=4(n2) +2n1X i=1i=4(n2) +n(n1)=n2+3n8Rappel n1X i=1i=n(n1)=2Amélie Lambert (Cnam)MPRO - Mise à niveau 21 / 49

Exemple 2 : produit de 2 matrices

static float[][] prod_mat(float[][] A,float[][] B) { // A[m,n] , B[n,p], résultat C[m,p] float[][] C =new float[m][p]; inti,j,k; floats; for(i=0; i< m; i++) { for(j=0; j< p; j++) { s = 0; for(k=0; j< n; j++) { s = s + A[i][k]B[k][j]; }

C[i][j] = s ;

pire cas = cas moyen = mp(2n+2) opérations Amélie Lambert (Cnam)MPRO - Mise à niveau 22 / 49

Comportement asymptotique

Ce qui nous intéresse est le comportement asymptotique en fonction denPour cela on compare la fonction de coût à des fonctions de référence Typiquement les fonctions polynomiales :na, puissancexn, exponentielles 2 nou logarithmiqueslog2(n)Pour exprimer la comparaison asymptotique on utilise la notation de

Landau

Amélie Lambert (Cnam)MPRO - Mise à niveau 23 / 49

Borne supérieure asymptotique : fonctionOf;gfonctionN!NDéfinition :Pour une fonction donnéegon noteO(g)l"ensemble des

fonctions :

O(g) =fftelles que9c0;9n00;8nn0;f(n)cg(n)g

on écritf=O(g)pourf2 O(g)et on ditfest en "grand O" deg. (intuitivement : à partir d"un certain rang,fne croît pas plus vite que g).

Exemple :

On af(n) =4n3+2n+1 opérations et8n1, 4n3+2n+17n3

Si on prendn0=1,c=7, etg(n) =n3, on montre que

f(n) =O(g(n)) =O(n3)Amélie Lambert (Cnam)MPRO - Mise à niveau 24 / 49 fonctionO: majorant du nombre d"opérations d"un algorithmef(n) =O(g(n))Amélie Lambert (Cnam)MPRO - Mise à niveau 25 / 49

Borne inférieure asymptotique : fonction

f;gfonctionN!NDéfinition :Pour une fonction donnéegon note (g)l"ensemble des fonctions : (g) =fftelles que9c0;9n00;8nn0;cg(n)f(n)g on écritf= (g)pourf2 (g)et on ditfest en Omega deg. (intuitivement : à partir d"un certain rang,fcroît plus vite queg).

Exemple :

On af(n) =4n3+2n+1 opérations et8n1,nf(n)

Si on prendn0=1,c=1, etg(n) =n, on montre que

f(n) = (g(n)) = (n)Amélie Lambert (Cnam)MPRO - Mise à niveau 26 / 49 fonction : minorant du nombre d"opérations d"un algorithmef(n) = (g(n))Amélie Lambert (Cnam)MPRO - Mise à niveau 27 / 49

Borne asymptotique approchée : fonctionf;gfonctionN!NDéfinition :Pour une fonction donnéegon note(g)l"ensemble des

fonctions : (g) =fftq9c1;c20;9n00;8nn0;c1g(n)f(n)c2g(n)g on écritf= (g)pourf2(g)et on ditfest en theta deg. (intuitivement : à partir d"un certain rang,fcroît de la même façon queg).

Exemple :Prenonsf(n) =12

n23n, on a : c 1n212 n23nc2n2)c112 3n c2et8n7 :114quotesdbs_dbs20.pdfusesText_26

[PDF] La complexité des algorithmes

La complexité des algorithmes

Amélie Lambert

MPRO - Mise à niveau

1Définition d"un algorithme

2Un exemple

3Évaluation des algorithmes

4Complexité en temps

5Exemples de complexité d"algorithmes

Définition d"un algorithme

Etapes de conception d"un algorithme

Phase 1

Énoncé du p roblème(Sp écification)

Phase 2

Élab orationde l"algo rithme

Phase 3

Vérification

Phase 4

Mesure de l"efficacité (Complexité)

Phase 5

Mise en o euvre(Programmation)

1Définition d"un algorithme

2Un exemple

3Évaluation des algorithmes

4Complexité en temps

5Exemples de complexité d"algorithmes

Exemple : le tri d"un tableau

Algorithme 1 : le tri par sélection (1/3)

Principe

Chercher le plus p etitpa rmiles non triés.

Algorithme 1 : le tri par sélection (2/3)

éléments triés

éléments non triés

Étape 1 :7815510

Étape 2 :5815710

Étape 3 :5715810

Étape 4 :5781510

Étape 5 :5781015

Étape 6 :5781015

Algorithme 1 : le tri par sélection (2/3)

éléments triés

éléments non triés

Étape 1 :7815510

Étape 2 :5815710

Étape 3 :5715810

Étape 4 :5781510

Étape 5 :5781015

Étape 6 :5781015

Algorithme 1 : le tri par sélection (2/3)

éléments triés

éléments non triés

Étape 1 :7815510

Étape 2 :5815710

Étape 3 :5715810

Étape 4 :5781510

Étape 5 :5781015

Étape 6 :5781015

Algorithme 1 : le tri par sélection (2/3)

éléments triés

éléments non triés

Étape 1 :7815510

Étape 2 :5815710

Étape 3 :5715810

Étape 4 :5781510

Étape 5 :5781015

Étape 6 :5781015

Algorithme 1 : le tri par sélection (2/3)

éléments triés

éléments non triés

Étape 1 :7815510

Étape 2 :5815710

Étape 3 :5715810

Étape 4 :5781510

Étape 5 :5781015

Étape 6 :5781015

Algorithme 1 : le tri par sélection (2/3)

éléments triés

éléments non triés

Étape 1 :7815510

Étape 2 :5815710