Qu’apportent comme résultats les algorithmes de recherche ? Comment les classer et déterminer leur application ? Parlons-en !
I. Introduction
A. Qu’est-ce que l’algorithmie ?
Je ne prétendrai pas avoir une définition définitive et complète de ce qu’est un algorithme, mais je vais essayer de donner une définition qui cadre avec les différentes situations auxquelles j’ai fait face et qui m’ont permis d’appliquer le concept d’algorithme.
Un algorithme est une suite ordonnée et finie d’étapes ou d’instructions pour réaliser un objectif. Il ressort de cette définition que les algorithmes se trouveraient un peu partout. Du domaine scientifique à la vie de tous les jours.
Nous sommes souvent confrontés à des situations qui font appel à des algorithmes dans tous les domaines de nos vies. Mais ce qui est encore plus important, c’est le besoin de mieux faire les choses, de faire mieux qu’avant. Les interrogations qui en découlent nous poussent à faire de l’optimisation de ces mêmes algorithmes. Mais hélas dans nos vies quotidiennes, nous ne sommes pas portés à faire des études approfondies de cet outil et nous tenterons dans cet article de détailler les subtilités de ce dernier.
B. Qu’est-ce qu’une structure de données ?
D’une manière simple, je peux définir une structure de données comme un récipient, un objet qui est sensé recevoir d’autres données (en informatique), un contenant.
Ce genre d’objet est courant dans notre vie. De nos maisons à nos lieux de travail, en passant par de nombreuses autres étapes, nous sommes souvent amenés à utiliser des structures qui doivent contenir quelque chose.
En informatique, nous avons aussi de nombreuses structures qui jouent pratiquement le même rôle que dans la vie de tous les jours et surtout permettent d’organiser des données en entrée et en sortie d’un algorithme.
II. Les Algorithmes
Les algorithmes constituent tout un domaine en informatique et fait l’objet de nombreuses études. C’est un domaine qui mobilise un nombre important de chercheurs, car il existe autant d’algorithmes à étudier qu’il existe de manières de faire les choses.
Nous n’avons pas la prétention de détailler de manière très approfondie les types d’algorithmes et leurs implications, tant le sujet est large. Mais nous parlerons des grandes lignes concernant les algorithmes et resterons sur des applications assez courantes des algorithmes.
A. Les différentes sortes d’algorithmes et leurs applications
Pour fonctionner, les algorithmes ont besoin des ressources de l’ordinateur. Ces ressources sont : le temps CPU et la mémoire. Le temps CPU pour permettre d’exécuter les instructions d’un algorithme et la mémoire pour contenir ou manipuler les données consommées ou produites par l’algorithme.
Nous introduisons un outil très puissant qui s’appelle l’analyse de la complexité. En effet cet outil permet de quantifier les deux grandeurs décrites précédemment : le temps et la mémoire, afin de comparer les algorithmes entre eux pour les classifier.
Nous n’allons pas dans cet article faire une étude approfondie sur l’analyse de la complexité d’un algorithme, mais nous allons plutôt récupérer les résultats d’analyse des différents algorithmes enfin de les classer et de déterminer leurs applications.
La classification se basera principalement sur le critère temps.
- Les algorithmes de complexité en temps constant : ce sont des algorithmes qui ne consomment qu’une unité de temps CPU. Nous avons énormément de cas où la complexité d’un algorithme est de 1.
Pour écrire dans une case mémoire, la complexité est d’une unité. De même pour lire une case mémoire.
Dans le cas où nous traitons un tableau d’objet, la lecture et l’écriture ne consomment qu’une unité de temps CPU. Cela veut dire aussi que l’algorithme ne contient qu’une seule étape dans son déroulement.
Nous avons là les grandes lignes des complexités des algorithmes. Mais nous souhaitons avoir des cas pratique où l’on pourrait ressortir ces différents algorithmes.
B. Quelques exemples d’optimisation des algorithmes
La classification se basera principalement sur le critère temps.
- Les algorithmes de complexité en temps constant : ce sont des algorithmes qui ne consomment qu’une unité de temps CPU. Nous avons énormément de cas où la complexité d’un algorithme est de 1.
Pour écrire dans une case mémoire, la complexité est d’une unité. De même pour lire une case mémoire.
Dans le cas où nous traitons un tableau d’objet, la lecture et l’écriture ne consomment qu’une unité de temps CPU. Cela veut dire aussi que l’algorithme ne contient qu’une seule étape dans son déroulement.
- Les algorithmes de complexité en temps logarithmique ( log2 n ) : les algorithmes sont souvent mis en œuvre dans le cas des recherches dichotomiques, des parcours d’arbres binaires ou toute autre opération sur ces arbres binaires de recherches.
- Les algorithmes linéaires (n) : ces algorithmes sont mis en œuvre dans la recherche séquentielle d’un élément dans un tableau non trié.
- Les algorithmes en (n log n) : ce sont de bons algorithmes mis en œuvre dans les tris (nous verrons quelques exemples).
- Les algorithmes en n^k : ces algorithmes ne sont vraiment utilisables que lorsque k < 2.
Si 2 ≤ k ≤ 3, alors l’algorithme est utilisable que pour des problèmes de taille moyenne. Et lorsque k dépasse 3, on ne peut traiter que des petits problèmes.
- Les algorithmes en temps exponentiel (2n) : ces algorithmes sont peu utilisables sauf pour des problèmes de très petites tailles. Ces sont des algorithmes qualifiés d’inefficaces
Nous allons nous intéresser à des cas simples de l’étude de complexité et de l’optimalité. Les deux cas à étudier sont les algorithmes de recherche et les algorithmes de tris.
Algorithmes de recherche
Une des utilisations les plus communes de l’informatique est le stockage de collections de données présentant des caractéristiques communes, et la recherche parmi ces données, d’éléments satisfaisants certains critères. Si le nombre de données est important, comme c’est souvent le cas, les opérations de recherche, de tris et de stockage ne doivent pas être réalisés en consommant beaucoup de temps.
D’où la nécessité de connaitre la complexité de l’algorithme et son optimalité.
Il existe pour les algorithmes de recherche ceux qui sont naïfs avec une grande complexité et ceux un peu plus intelligents.
Algorithmes de Recherche séquentielle
La recherche séquentielle s’applique à une collection de données représentée par une liste. La recherche séquentielle convient à des situations où il y a peu d’éléments et elle est aussi utile dans des situations où il existe beaucoup d’éléments, mais dans ce cas nous cherchons toujours les mêmes éléments.
Nous distinguons deux cas : la recherche dans une liste non triée et la recherche dans une liste triée
Recherche dans une liste non triée :
Posons de façon naïve cette solution pour la recherche d’un élément dans une liste λ :
Pour i compris entre 1 et longueur(λ), comparer X et ième(λ, i)
« longueur » et « ième » sont des opérations de la collection (liste) et λ est la collection de données.
Nous allons étudier sa complexité en moyenne pour déterminer sa complexité dans le pire de cas.
Supposons qi la probabilité que l’élément X apparaisse dans la liste à la place i de la liste (i = 1, … ,n) et p est la probabilité pour que l’élément n’appartienne pas à la liste.
Nous déduisons une relation simple : p + q1 +…+ qn = 1
Alors le nombre moyen de comparaisons pour une recherche dans une liste est :
Moy(n) = 1.q1 + 2.q2 +…+ n.qn + (n+1).p
Supposons que l’élément que l’on cherche, est toujours dans la liste cela implique : p = 0
Alors l’équation devient Moy(n) = 1.q1 + 2.q2 +…+n.qn
Cette quantité est grande lorsque nous avons un ordre suivant qn ≥…≥ q2 ≥ q1 , c’est-à-dire que les éléments à chercher sont en fin de liste.
Elle est petite dans le cas où q1 ≥ q2 ≥…≥ qn , c’est-à-dire que les éléments à chercher sont en début de liste.
Donc pour une recherche séquentielle, la complexité dans le pire de cas est de Θ(n), elle est linéaire. Mais pour les éléments se trouvant au début de la liste, la recherche peut aller encore plus vite.
C’est pour cela que, pour un grand nombre de recherches, il est intéressant de réorganiser la liste à chaque recherche. Alors dans ce cas on parle de la recherche auto-adaptative.
Algorithmes de Recherche séquentielle dans une liste triée :
Supposons qu’il existe un ordre total sur les éléments de la liste. Supposons que les éléments de la liste sont triés en ordre croissant. Pour chercher X, il nous faudra parcourir séquentiellement les éléments du tableau jusqu’à ce que l’on trouve X ou un élément strictement supérieur à X (dans ce cas on sait que l’élément X ne se trouve pas dans la liste, puisque les éléments sont triés dans l’ordre croissant).
Dans le pire de cas, il faut faire n ou (n + 1) comparaisons, comme pour une recherche séquentielle.
Mais examinons la complexité en moyenne de cet algorithme, comme nous l’avions fait avec la recherche séquentielle dans une liste non triée.
Notons qi la probabilité que X (l’élément recherché) soit égale au iième de la liste, pour i = 1, …, n ; Notons pj la probabilité que X soit strictement compris ente le jième et le (j + 1)ième élément de la liste, pour j = 1, …, n – 1
Enfin p0 (et pn ), la probabilité que X soit strictement inférieur (resp. supérieur) au premier (resp. dernier) élément de la liste.
Les deux événements étant disjoints, nous avons clairement : p0 + p1 + … + pn + q1 + … + qn = 1.
De cette relation, nous déduisons le nombre de relation tel que :
Plaçons-nous dans l’hypothèse d’équiprobabilité p0 = p1 = … = pn et q1 = q2 = … = qn et considérons quelques cas de figures.
Recherche d’éléments présents dans la liste : tous les pj sont nuls.
Alors q1 = q2 = … = qn = 1/n , d’où le Moy(n) = (n + 1)/2
Dans ce cas on obtient le même nombre moyen de comparaisons que pour la recherche séquentielle dans une liste non triée.
Recherche d’éléments qui ne sont pas dans la liste : tous les qi sont nuls.
Alors p0 = p1 = … = pn = 1/n+1, d’où Moy(n) = (n + 2)/2
Lorsque l’élément recherché ne se trouve pas dans la liste, on diminue de moitié le nombre de comparaisons par rapport à la recherche séquentielle dans une liste non triée. Tout simplement parce que l’algorithme s’arrête lorsqu’il rencontre un élément strictement supérieur à l’élément recherché.
Recherche d’éléments qui ont une chance sur deux d’appartenir à la liste : c’est le cas où Σ qi = Σ pj = 1/2
Ce qui est un résultat légèrement meilleur que celui que l’on obtient dans les mêmes conditions pour une liste non triée.
Malgré des légères différences de complexité dans les deux méthodes de recherche séquentielle, nous constatons qu’elle tient très peu compte du fait que la liste soit triée dans l’ordre croissant. Et sa complexité est en Θ(n) comme lorsque les éléments ne sont pas triés.
Algorithmes de Recherche dichotomique
La recherche dichotomique ou la recherche par dichotomie est une façon très efficace d’effectuer la recherche d’un élément X dans une liste.
Cette méthode de recherche utilise pleinement le fait qu’une liste soit triée.
Le principe de la recherche par dichotomie d’un élément X dans une liste triée L consiste à comparer X avec l’élément M du milieu de la liste L :
- Si X = M, on a trouvé une solution, la recherche s’arrête
- Si X > M, il est impossible que X se trouve avant M dans la liste L, et il ne reste à traiter que la moitié (droite) de la liste L
- Si X<M, X ne peut se trouver que dans la moitié gauche de L.
La recherche continue ainsi en diminuant de moitié le nombre d’éléments de la liste après chaque comparaison. Si en recherchant X dans toutes les partitions de la liste, aucun résultat n’est retourné alors nous concluons que X n’est pas dans la liste.
Nous allons étudier deux versions des algorithmes de recherche dichotomique : une version récursive et une version itérative.
La version récursive de la recherche par dichotomie
En suivant le principe de la dichotomie, nous sommes naturellement conduits à écrire la procédure récursive suivante :
procedure dicho (X: Element; t: array [1…n] of Element; g, d: 0…n+1; var res:0…n)
{ cette procédure récursive recherche par dichotomie l’élément X dans le tableau t dont les éléments sont triés en ordre croissant ; le résultat de la procédure est contenu dans la variable res : c’est 0 si X n’appartient pas au tableau , et c’est i ϵ {1, …, n} si X se trouve à l’indice du tableau. g et d étant des indices placés en début et en fin du tableau}
var m : 1…n
begin if g ≤ d then begin
m := (g + d) div 2
if X = t[m] then res := m
else if X < t[m] then dicho(X, t, g, m-1, res)
else dicho(X, t, m+1, d, res)
end
else res := 0;
end dicho;
Pour réaliser cette recherche sur une liste de n éléments, on appelle cette procédure avec les paramètres g = 1 et d = n.
Ici la structure de la liste représentée par un tableau est très importante tout simplement parce que les algorithmes de recherche dichotomique ont besoin d’un accès direct aux éléments de la liste.
Avec une procédure récursive, nous avons besoin de prouver que l’algorithme est correct. Alors nous avons un point principal à vérifier pour tirer une conclusion :
* On doit montrer que l’algorithme termine toujours (soit avec res > 0, soit avec res = 0)
Nous devons prouver que les appels récursifs sont toujours en nombre fini, c’est-à-dire que la suite (gi, di) qui sont les bornes des différents sous-tableaux avec lesquels on appelle récursivement la procédure dicho, est finie.
Supposons que les (gi , di) construits pour 0 ≤ i ≤ k, avec g0 = 1 et d0 = n et mk = (gk + dk) div 2. Plusieurs cas sont à considérer :
- Si gk > dk , ou si X = t[mk] alors la procédure termine et il n’y a plus d’appel récursif.
- Si gk ≤ dk et X < t[mk], il y a un appel récursif et gk+1 = gk et dk+1 = mk – 1 ;
On a alors dk+1 – gk+1 < dk – gk
- Si gk ≤ dk et X > t[mk], il y un appel récursif et gk+1 = mk + 1 et dk+1 = dk, on a encore
dk+1 – gk+1 < dk – gk
Ainsi la suite des écarts (di – gi) est strictement décroissante. Il existe donc un entier p tel que :
- Soit gp > dp ,et dans ce cas la procédure termine avec res = 0 ;
- Soit X = t[mp] avec mp = (gp + dp) div 2, et dans ce cas la procédure termine avec res = mp > 0.
Analyse et calcul du nombre de comparaisons
Dans toute recherche d’élément dans une liste, l’opération fondamentale reste la comparaison entre l’élément cherché et les éléments de la liste.
Nous allons par la suite analyser puis calculer la complexité au pire, au mieux et en moyenne de la procédure dicho.
Nous allons prendre comme exemple une liste triée de 12 éléments. Or la recherche dichotomique sur une telle liste est (ou peut-être) décrite par un arbre binaire.
Nous avons sur cette image les t[i] pour i = 1, …, 12 et fj pour j = 1, …, 12.
Les feuilles f0, f1, …, f12 représentent les cas de terminaison sans succès et les nœuds internes représentent les comparaisons de l’élément cherché avec les éléments t[i].
Voici de quelle façon on parcourt cet arbre :
- Si X = t[i] on arrête la procédure
- Si X > t[i] (resp. X < t[i]), la procédure se poursuit en comparant X et le fils droit (resp. gauche) de t[i]
Or le parcours en profondeur d’un arbre binaire, dans le pire de cas lorsque nous atteignons les feuilles, se fait en log (n).
Nous admettons sans démonstration que les algorithmes de recherche par dichotomie ont une complexité dans le pire de cas de l’ordre de Θ(log n).
Algorithmes de Tris
Les méthodes de tri sont très importantes dans le monde informatique dans l’informatique de gestion où un grand nombre d’applications consistent à trier les fichiers.
Mais intéressons-nous à son formalisme. La question fondamentale est qu’est-ce qu’un Tri ?
La spécification du tri
Supposons une liste de taille n (soit n éléments) ; à chaque élément est associé une clé qui appartient à un ensemble totalement ordonné ;
Le tri est alors une permutation de cette liste d’origine telle que les clés sont croissantes quand on parcourt la liste séquentiellement.
Décrivons plus formellement notre définition.
Le tri peut être vu comme un enrichissement du type abstrait Liste, c’est-à-dire comme une opération en plus dans la liste des opérations que l’on peut effectuer sur le type Abstrait Liste.
Alors nous avons : tri : Liste -> Liste
Nous avions constaté qu’il existe une relation étroite entre les clés des éléments de la liste et le tri de la liste.
Or les clés peuvent être spécifiées de cette manière :
Sorte : Clé
Utilise : Booléen
opération _≤_ (inferieur à): Clé x Clé -> Booléen
Axiomes :
x ≤ x = vrai
(x ≤ y = vrai) & (y ≤ x = vrai) → x = y
(x ≤ y = vrai) & (y ≤ z = vrai) → x ≤ z = vrai
avec
x, y, z : Clé
Nous venons au travers de ces quelques lignes de formaliser que les clés appartiennent bien à un ensemble totalement ordonné.
Nous nous munissons d’une nouvelle opération clé, tel que :
Clé : Element -> Clé
A tout élément d’une Liste, l’opération rend sa clé.
Donc une liste triée sera formalisée de cette manière :
Opération
triée : Liste -> Booleen
Axiomes
triée(liste-vide) = vrai
triée(cons(e, liste-vide)) = vrai
λ ≠ liste-vide → triée(cons(e, λ)) = (clé(e) ≤ clé(premier(λ))) Ʌ triée(λ)
avec
e : Element ; λ : Liste ; cons : un opérateur qui construit une liste
Donc nous arrivons à la conclusion suivante : le tri d’une liste λ consiste à trouver une liste λ’, dont les éléments sont une permutation des éléments de λ.
Qu’est-ce qu’une permutation : deux listes λ et λ’ sont des permutations l’une de l’autre, si et seulement si, le nombre d’occurrences de tout élément est égal dans les deux listes.
D’une manière un peu plus formelle, définissons la notion de permutation et de nombre d’occurrences.
Opérations
perm : Liste x Liste → Booléen
nb-occ : Elément x List → Entier
Axiomes
nb-occ(x, liste-vide) = 0
x = y → nb-occ(x, cons(y, λ)) = nb-occ(x, λ) + 1
x ≠ y → nb-occ(x, cons(y, λ)) = nb-occ(x, λ)
perm(liste-vide, liste-vide) = vrai
perm(liste-vide, cons(x, λ)) = faux
nb-occ(x, u) = 0 → perm(cons(x, λ), u) = faux
perm(cons(x, λ), concat(u, cons(x, u’))) = perm(λ, concat(u, u’))
avec
x, y : Elément ; λ, u, u’ = Liste ;
L’opération de tri dans une liste doit satisfaire les axiomes (définition formelle) suivante :
perm(λ, tri(λ)) = vrai
triée(tri(λ)) = vrai
Nous allons par la suite exposer deux méthodes de tri seulement, sachant qu’il y en a une plus.
Méthodes de tri par sélection
Le principe de cette méthode est simple : on cherche le minimum de la liste à trier. On le met à la première place, et on recommence sur le prochain élément de la liste à trier.
Voici une illustration de ce qui se passe pour ces algorithmes de recherche :
Passons à une définition formelle (spécification formelle) de cette méthode :
Opérations
tri-select : Liste → Liste
Axiomes
tri-select(liste-vide) = liste-vide
λ ≠ liste-vide → tri-select(λ) = cons(min(λ), tri-select(supprimer-min(λ)))
Nous avons introduit deux nouvelles opérations sur la liste abstraite λ, ces opérations sont min et supprimer-min.
Ces opérations définies par :
Opérations
min : Liste → Liste
supprimer-min : Liste → Liste
Préconditions
min(λ) est défini si λ ≠ liste-vide
supprimer-min est défini si λ liste-vide
Axiomes
est-présent(min(λ), λ) = vrai
est-présent(e, λ) = vrai → min(λ) ≤ e = vrai
nb-occ(min(λ), supprimer-min(λ)) = nb-occ(min(λ), λ) – 1
e ≠ min(λ) → nb-occ(e, supprimer-min(λ)) = nb-occ(e, λ)
avec
e : Elément ; λ : Liste
On peut aisément vérifier que la spécification formelle de la méthode tri-select respecte bien la définition globale de tri.
Il est important de savoir qu’il existe deux méthodes de tri par sélection : la sélection ordinaire et le tri à bulles.
Les deux sont assez proches avec quelques différences spécifiques. Mais nous allons plus développer la première méthode.
Sélection Ordinaire
Si on cherche séquentiellement le minimum, et que l’on échange à chaque fois ce minimum avec le premier élément, on fait de la sélection ordinaire.
Nous allons programmer dans un pseudo code le tri-select récursif
procedure tri-select(var t : array[1 … n] of integer ; i : integer)
var j, k : integer;
begin
if i < n then begin
{recherche séquentielle du minimum entre les indices i et n}
j := I;
for k := i+1 to n do if t[k] < t[j] then j := k;
{placement du minimum}
t[j] ↔ t[i];
tri-select(t, I + 1);
end
end tri-select
Il existe aussi une version itérative, mais nous nous intéressons uniquement à l’analyse de la version récursive. Tout simplement parce que la réflexion est la même pour les deux méthodes de programmation du tri-select.
Analyse de la sélection ordinaire
L’algorithme décrit ci-dessus effectue deux types d’opérations fondamentales : les comparaisons entre les clés et les transferts d’éléments.
Nombre de comparaisons :
Pour une liste de taille n, on effectue n – 1 comparaisons pour trouver le minimum : en effet, on exécute n – 1 itérations dans la boucle interne et à chaque itération il y a une comparaison. Cette recherche du minimum est suivie de l’exécution de l’algorithme pour une liste de n-1 éléments.
On a donc l’équation de récurrence :
MaxC = n – 1 + MaxC(n – 1) pour n > 1 et
MaxC(1) = 0
Sachant que le nombre de comparaisons ne dépend pas de la liste :
MoyC(n) = MaxC(n)
L’équation de récurrence sur Max se résout selon une méthode directe :
Les complexités en nombre de comparaisons pour la sélection ordinaire sont donc :
Nombre d’échanges
La complexité au pire est égale à la complexité en moyenne dans ce cas aussi puisque on fait un échange à chaque appel de la procédure. D’où pour le nombre d’échanges :
MaxE(n) = MoyE(n)
MaxE(n) = 1 + MaxE(n – 1) pour n > 1 et
MaxE(1) = 0
On obtient donc :
MaxE(n) = MoyE(n) = n – 1
Donc la complexité en nombre d’échanges pour une liste de taille n est de Θ(n)
Méthodes de tri par insertion
Cette méthode, comme nous allons le voir par la suite, est optimale par rapport à la première tout simplement à cause de sa complexité quasi-linéaire.
Cette méthode fonctionne comme suite : on trie successivement les premiers éléments de la liste ; à la iième étape on insère le iième élément à son rang parmi les i – 1 éléments précédents qui sont déjà triés entre eux. Nous illustrons cette méthode par la figure suivante :
Toujours à l’aide des outils mathématique, nous pouvons formaliser le tri-insert (donner une spécification fonctionnelle)
opérations
tri-insert : Liste → Liste
insérer : Elément x Liste → Liste
précondition
insérer(e, λ) est défini ssi triée(λ) = vrai
axiomes
tri-insert(liste-vide) = liste-vide
λ ≠ liste-vide → tri-insert(λ) = insérer(dernier(λ), tri-insert(début(λ)))
triée(insérer(e, λ)) = vrai
perm(cons(e, λ), insérer(e, λ)) = vrai
avec λ : liste ; perm : permutation ;
Nous allons programmer une version récursive (uniquement) du tri-insert pour notre algorithmes de recherche.
Retenons une chose, il existe deux sortes de tri-insert : l’insertion séquentielle et l’insertion dichotomique.
Des deux méthodes, seule la méthode d’insertion dichotomique est optimale. C’est même elle qui une complexité quasi-linéaire.
Donc on comprend vite qu’elle est la plus utilisée.
procedure tri-insert-dicho(var t : array[1 …n] of integer ; i : integer);
var j, k, x : integer;
begin
if i > 1 then begin
tri-insert-dicho(t, i - 1);
if t[I - 1] > t[i] then begin
{la fonction “rang” est donnée plus loin; elle rend l’indice où doit être inséré t[i]
entre les indices 1 et i – 1, si t[i] < t[i – 1]}
k := rang(t, 1, i – 1, t[i]) ;
{il reste à faire les transferts}
x := t[i] ;
for j := i – 1 downto k do t[j + 1] := t[j];
t[k] := x
end
end
end tri-select-dicho
La fonction rang donne l’indice où doit être inséré l’élément x entre les indices p et q de t quand x est inférieur à t[q] :
function rang(t : array[1 …n] of integer ; p, q, x : integer) : integer;
var mil : integer;
begin
if p = q then return (p)
else begin
mil := (p + q) div 2;
if x < t[mil] then return (rang(t, p, mil, x))
else return (rang(t, mil + 1, q, x))
end
Analyse de l’insertion dichotomique
Intéressons-nous au nombre de comparaisons pour établir une complexité au pire des algorithmes de recherche.
En effet, nous savons que la méthode d’insertion dichotomique pour trier une liste de n élément, commence par trier les n – 1 premiers éléments, puis fait une comparaison entre t[n-1] et t[n] qui entraine, dans le pire de cas un appel à la fonction rang sur une liste de n – 1 éléments.
Et en nous référant à ce qui a été fait avec les algorithmes de recherche dichotomique, l’appel de la fonction rang sur une liste de n éléments implique log n comparaisons entre élément au pire.
En effet nous avons :
Maxrang(n) = 1 + Maxrang(log n) pour n > 1 et Maxrang(1) = 0
Pour le tri insertion dichotomique :
MaxC(n) = 1 + MaxC(n – 1) + Maxrang(n – 1)
On a donc finalement :
MaxC(n) = MaxC(n – 1) + 1 + log(n – 1) et MaxC (1) = 0
Après simplification nous avons :
Or en utilisant l’outil de l’encadrement des sommes discrètes, tel que :
log i ≤ born_sup(log i) ≤ (log i) +1
avec : born_sup : borne supérieure
Il en résulte après différente démonstration que le nombre de comparaison au pire de cas est :
MaxC(n) = Θ(n log n)
Conclusion
Nous venons de voir d’une manière condensée les algorithmes de recherche et de tri avec surtout des notations empruntées aux mathématiques pour démontrer de manière formelle les idées que l’on soupçonne vaguement.
Dans une seconde partie, nous parlerons des structures de données, des notions que nous connaissons et acceptons sans démonstration. L’objectif sera de présenter de manière formelle les notions déjà vues et de présenter certaines applications particulières des structures de données.
