Algorithmique et structures de donnees cours complet
Téléchargement: Algorithmique et structures de donnees cours complet
Si le téléchargement ne démarre pas après 5 secondes, veuillez cliquer sur le lien "Télécharger"
Télécharger-
Algorithmique et structures de données cours complet
Tris : contexte
tri interne : le tri s’effectue en mémoire centrale. Les tris externes ne sont pas abordés dans ce cours tri de tableau : un tri qui trie un tableau. Extensible à toute structure de données offrant un accès en temps (quasi)constant à ses éléments (par exemple les Vectors en Java) tri générique : tous les tris présentés ici sont écrits pour trier des tableaux d’objets à clef mais peuvent aisément s’adapter pour des objets totalement ordonnés quelconques
Tris : propriétés
tri comparatif : fondé sur la comparaison entre les clefs des éléments
tri itératif : basé sur un ou plusieurs parcours itératifs du tableau tri récursif : basé sur une méthode récursive tri en place : ne nécessite qu’une quantité constante de mémoire supplémentaire tri stable : conserve l’ordre relatif des éléments de même clef
ASD 2 – p.3/73
Tris : méthodes quadratiques
Propriétés
basées sur le parcours itératif du tableau à trier en général deux boucles imbriquées complexité en Pn − 1
i=0
i = n(n−1)
2 = Θ(n2) dans le pire des cas, mais aussi en moyenne implémentation triviale
optimal pour les tableaux de petite taille (< 25 )
Tris : méthodes quasi-linéaires
Les tris comparatifs optimaux
tri par tas (ou heapsort) : complexité en Θ( n lg n) (pire des cas et en moyenne)
tri rapide (ou quicksort) : complexité en Θ(n lg n) (en moyenne) mais peut dégénérer (Θ(n2 ) dans le pire des cas)
tri fusion : complexité en Θ(n lg n) (pire des cas et en moyenne) mais nécessite un tableau auxiliaire (le tri n’est plus en place)
Tri par tas : introduction heapsort en anglais inventé par Williams en 1964 basé sur une structure de donnée très utile, la file de priorité complexité bornée par Θ( n lg n) quelle que soit la configuration initiale du tableau tri en place mise en œuvre très simple
Tri par tas : tri par sélection
1. Prendre le plus grand élément parmi les taille premiers éléments d’un tableau.
2. L’échanger avec le tailleième élément du tableau.
3. Retour à l’étape 1 en ne considérant que les taille
−
1 premiers éléments du tableau.
0 T.length
T Taille < max
Tri par tas : tri par sélection 0 T.length
T taille < max
Complexité de la recherche du plus grand élément : Θ(taille).
Complexité globale du tri : Θ(n2).
Optimiser la recherche du plus grand élément
ASD 2 – p.8/73
Tas : arbre parfait
A est un arbre parfait si
A est arbre binaire de hauteur H une feuille de
A a la profondeur h ou h − 1
A possède 2 h − 1 nœuds de profondeur h − 1 tous les nœuds de profondeur h sont regroupés le plus à gauche possible
- Evaluation :
-
Total des Votes : 0 -
Soyez le premier à écrire un commentaire sur ce fichier!
Veuillez vous identifier ou vous enregistrer.