View
105
Download
1
Category
Preview:
Citation preview
Structures de donnéesIFT-10541
Abder AlikacemAbder Alikacem
Semaine 7 Les algorithmes de recherche
Département d’informatique et de génie logiciel
Édition septembre 2009
! +
Plan
• Les algorithmes de recherche• La recherche séquentielle• La recherche dichotomique
• Complexité des algorithmes de recherche• Recherche dichotomique et arborescence
La recherche séquentielle
3 1 4 2 8 14 12 11 6 9 10
• recherche(3) =• recherche(10) =• recherche(12) =• recherche(13) = • meilleur cas =• pire cas =• en moyenne =• absences =
Données pas triées
La recherche séquentielle
3 1 4 2 8 14 12 11 6 9 10
• recherche(3) = 1 comparaison• recherche(10) =• recherche(12) =• recherche(13) =• meilleur cas =• pire cas =• en moyenne =• absences =
Données pas triées
La recherche séquentielle
3 1 4 2 8 14 12 11 6 9 10
• recherche(3) = 1 comparaison• recherche(10) = 11 comparaisons• recherche(12) =• recherche(13) =• meilleur cas =• pire cas =• en moyenne =• absences =
Données pas triées
La recherche séquentielle
3 1 4 2 8 14 12 11 6 9 10
• recherche(3) = 1 comparaison• recherche(10) = 11 comparaisons• recherche(12) = 7 comparaisons• recherche(13) =• meilleur cas =• pire cas =• en moyenne = • absences =
Données pas triées
La recherche séquentielle
3 1 4 2 8 14 12 11 6 9 10
• recherche(3) = 1 comparaison• recherche(10) = 11 comparaisons• recherche(12) = 7 comparaisons• recherche(13) = 11 comparaisons• meilleur cas =• pire cas =• en moyenne =• absences =
Données pas triées
La recherche séquentielle
3 1 4 2 8 14 12 11 6 9 10
• recherche(3) = 1 comparaison• recherche(10) = 11 comparaisons• recherche(12) = 7 comparaisons• recherche(13) = 11 comparaisons• meilleur cas = O(1)• pire cas =• en moyenne =• absences =
Données pas triées
La recherche séquentielle
3 1 4 2 8 14 12 11 6 9 10
• 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 = • absences =
Données pas triées
La recherche séquentielle
3 1 4 2 8 14 12 11 6 9 10
• 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 =
Données pas triées
La recherche séquentielle
3 1 4 2 8 14 12 11 6 9 10
• 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)
Données pas triées
La recherche séquentielle
1 2 3 4 6 8 9 10 11 12 14
• recherche(1) =• recherche(14) =• recherche(8) =• recherche(13) =• meilleur cas =• pire cas =• en moyenne = • absences =
Données triées
La recherche séquentielle
1 2 3 4 6 8 9 10 11 12 14
• recherche(1) = 1 comparaison• recherche(14) =• recherche(8) =• recherche(13) =• meilleur cas =• pire cas =• en moyenne = • absences =
Données triées
La recherche séquentielle
1 2 3 4 6 8 9 10 11 12 14
• recherche(1) = 1 comparaison• recherche(14) = 11 comparaisons• recherche(8) =• recherche(13) =• meilleur cas =• pire cas =• en moyenne = • absences =
Données triées
La recherche séquentielle
1 2 3 4 6 8 9 10 11 12 14
• recherche(1) = 1 comparaison• recherche(14) = 11 comparaisons• recherche(8) = 6 comparaisons• recherche(13) =• meilleur cas =• pire cas =• en moyenne = • absences =
Données triées
La recherche séquentielle
1 2 3 4 6 8 9 10 11 12 14
• recherche(1) = 1 comparaison• recherche(14) = 11 comparaisons• recherche(8) = 6 comparaisons• recherche(13) = 11 comparaisons• meilleur cas =• pire cas =• en moyenne = • absences =
Données triées
La recherche séquentielle
1 2 3 4 6 8 9 10 11 12 14
• recherche(1) = 1 comparaison• recherche(14) = 11 comparaisons• recherche(8) = 6 comparaisons• recherche(13) = 11 comparaisons• meilleur cas = O(1)• pire cas =• en moyenne = • absences =
Données triées
La recherche séquentielle
1 2 3 4 6 8 9 10 11 12 14
• 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 = • absences =
Données triées
La recherche séquentielle
1 2 3 4 6 8 9 10 11 12 14
• 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 =
Données triées
La recherche séquentielle
1 2 3 4 6 8 9 10 11 12 14
• 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)
Données triées
La recherche séquentielle
données non triées :• données présentes : O(n/2)• données absentes : O(n)
données triées :• données présentes : O(n/2)• données absentes : O(n/2)
coût pour trier et maintenir triées !
Modèles d’implantation
tableau :
liste chaînée :
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
La 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
1 2 3 4 6 8 9 10 11 12 14
La recherche binaire
1 2 3 4 6 8 9 10 11 12 14
100
La recherche binaire
1 2 3 4 6 8 9 10 11 12 14
100 5
La recherche binaire
1 2 3 4 6 8 9 10 11 12 14
100 5
La recherche binaire
1 2 3 4 6 8 9 10 11 12 14
100 5
La recherche binaire : 10 ?
1 2 3 4 6 8 9 10 11 12 14
100 5
La recherche binaire : 10 ?
1 2 3 4 6 8 9 10 11 12 14
100 5
La recherche binaire : 10 ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 10
La recherche binaire : 10 ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 108
La recherche binaire : 10 ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 108
La recherche binaire : 10 ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 108
La recherche binaire : 10 ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 108
6 7
La recherche binaire : 10 ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 108
6 7
La recherche binaire : 10 ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 108
6 7
La recherche binaire : 10 ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 108
6 7
1 2 3 4 6 8 9 10 11 12 14
7
La recherche binaire : 10 ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 108
6 7
1 2 3 4 6 8 9 10 11 12 14
7
La recherche binaire : 9.5 ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 108
6 7
1 2 3 4 6 8 9 10 11 12 14
7
La recherche binaire : 9.5 ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 108
6 7
1 2 3 4 6 8 9 10 11 12 14
7
11
5
2
1
La recherche binaire : 9.5 ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 108
6 7
1 2 3 4 6 8 9 10 11 12 14
7
11
5
2
1
n
n/2
n/4
n/8
Algorithme récursif
• récursion ?
• conditions d’arrêt ?
• convergence ?
1 2 3 4 6 8 9 10 11 12 14
100 5
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
100 5
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
100 5
Convergence
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100 5
6 108
6 7
1 2 3 4 6 8 9 10 11 12 14
7
Template <typename T>
int rechercheBinRec(T * tab, T val, int debut, int fin)
{ int milieu;
/*A: tab est correctement initialisé*/
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));
}
}
}
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.
Remarque sur les algorithmes récursifs
Tableau comparatif
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)
Modèles d’implantation
tableau :
liste chaînée ?
1 2 3 4 6 8 9 10 11 12 14
1 2 3 4 6 8 9 10 11 12 14
100
Structures pointées
1 2 3 4 6 8 9 10 11 12 14
0 1 2 3 4 5 6 7 8 9 10
Structures pointées
1 2 3 4 6 8 9 10 11 12 14
0 1 2 3 4 5 6 7 8 9 10
Structures pointées
1 2 3 4 6 8 9 10 11 12 14
0 1 2 3 4 5 6 7 8 9 10
Structures pointées
1 2 3 4 6
8
9 10 11 12 14
0 1 2 3 4 6 7 8 9 10
Structures pointées
1 2 3 4 6
8
9 10 11 12 14
0 1 2 3 4 6 7 8 9 10
Structures pointées
1 2 3 4 6
8
9 10 11 12 14
0 1 2 3 4 6 7 8 9 10
Structures pointées
1 2
3
4 6
8
9 10
11
12 14
0 1 3 4 6 7 9 10
Structures pointées
1 2
3
4 6
8
9 10
11
12 14
0 1 3 4 6 7 9 10
Structures pointées
1 2
3
4 6
8
9 10
11
12 14
0 1 3 4 6 7 9 10
Structures pointées
1
2
3
4
6
8
9
10
11
12
14
Structures pointées
1
2
3
4
6
8
9
10
11
12
14
Structures pointées
1
2
3
4
6
8
9
10
11
12
14
Structures pointées
1
2
3
4
6
8
9
10
11
12
14
Arbre binaire !
1
2
3
4
6
8
9
10
11
12
14
Arbre binaire !
1
2
3
4
6
8
9
10
11
12
14
≤≤
≤≤
≤
≤≤
≤ ≤ ≤
Arbre binaire
racine
sous-arbre de gauchesous-arbre de droite
nœuds internes
feuilles
Arbre = graphe
1
2
3
4
6
8
9
10
11
12
14
Arbre = graphe
1
2
3
4
6
8
9
10
11
12
14
Arbre = graphe
1
2
3
4
6
8
9
10
11
12
14
Arbre = graphe
• graphe connexe, orienté, acyclique• 1 seul nœud source = racine• nœuds puits = feuilles• ordre d ’entrée de tout nœud = 1, sauf racine• un chemin de la racine à tout autre nœud
Arbre = index
1
2
3
4
6
8
9
10
11
12
14
Arbre = index
1
2
3
4
6
8
9
10
11
12
14
Index sur sommet d’un graphe
4
25
3
1
1
2
3
4
5
1 2 3 4 5
1
1 1
1 1
1
...
Index sur sommet d’un graphe
4
25
3
1
1
2
3
4
5
1 2 3 4 5
1
1 1
1 1
1
...
3
5
4
2
1
Recommended