LaDissertation.com - Dissertations, fiches de lectures, exemples du BAC
Recherche

Tri des programmes sur ordinateur

Synthèse : Tri des programmes sur ordinateur. Recherche parmi 297 000+ dissertations

Par   •  5 Mai 2022  •  Synthèse  •  561 Mots (3 Pages)  •  182 Vues

Page 1 sur 3

                                                                                                                                                               

Projet Tri population en France

Complexité du tri :  Pour les deux tris auxquels on a affaire, nous allons calculer la complexité. Si on veut calculer le temps que met un algorithme lors de son exécution du début à la fin, il faut compter le nombre d’opérations effectuées, dont on connait de temps d’exécution, plus précisément on prend en compte les opérations fondamentales.

Il faut appliquer ce que nous venons de dire numériquement. Le tri par sélection, effectue (n*(n-1))/2 comparaisons, avec n le nombre d’éléments d’une liste, en comptant les opérations fondamentales de notre algorithme. On en déduit le calcul (n² -n)/2 (simple distributivité) et que sa complexité est O(n 2 ), quadratique. Pour le tri par insertion il y a plusieurs cas possibles, elle peut être quadratique dans certains cas, de l’ordre de n2/4 ou encore il peut y avoir n-1 dans le meilleur des cas. La complexité (dans le pire des cas)  est quadratique, on retrouve le calcul (n² -n)/2.

Comptage d’opérations fondamentales : Nous avons précédemment dit que les opérations fondamentales prises en compte sont les comparaisons. Dans nos deux algorithmes « tri_par_selection » et « tri_par_insertion »  nous avons ajouté une variable compteur :    

[pic 1]

Population de l’Ain

Population 5 departements

Population de 10 départements

Population de la France

Tri par selection

83028

1785105

6499815

625960653

Tri par insertion

40807

1003206

3727196

286290672

Mesure du temps :

Population de l’Ain

Population 5 departements

Population de 10 départements

Population de la France

Tri par selection

0.0378

0.5705

1.9834

78.059

Tri par insertion

0,0781

0.6706

2.5380

74.482

Pour mesurer le temps, on importe le module « time » et on applique la fonction.

[pic 2]

Bilan : On prend le nombre d’éléments par lignes, ce qui correspond au nombres d’éléments à trier. Pour l’Ain, 407. Pour les 5 départements, 1849. Pour les 10 départements, 3604 et pour la population de la France, 35382.

On peut alors vérifier les calculs de complexité en remplaçant n par le nombre d’éléments à trier (comparer).

...

Télécharger au format  txt (3.6 Kb)   pdf (111 Kb)   docx (64.4 Kb)  
Voir 2 pages de plus »
Uniquement disponible sur LaDissertation.com