3.3.2 Etude de la compléxité
Le bloc 1 de l'algorithme calcule la borne
supérieur entre xi et ses successeurs. Pour tout successeur
z de xi on a : xi ? z = z.. Ainsi la
compléxité de ce bloc vaut O(|U|)
Le bloc 2 de l'algorithme calcule la borne
supérieur entre xi et les éléments qui lui sont
incomparables. L'algorithme calcule l'ensemble W des bornes
supérieures entre les successeurs immédiats de xi et
l'élément z qui lui est incomparable. Ensuite,
l'algorithme teste si cet ensemble possède un élément
minimum. Ainsi le calcul de W coûte
O(|ImmSucc(xi)|) et la vérification qu'il
possède un élément minimum revient à
vérifier si l'élément le plus petit de W est un
élément minimum.
Le test de comparabilité se fait en O(1) en
utilisant les bornes supérieurs déjà calculées, la
compléxité totale est alors de l'ordre de
O(|X|.|ImmSucc(xi)|) soit
O(|X|.|U|).[5]
Exemple 4 Soit le diagramme figure(3.6)
ci-dessus, essayons d'appliquer l'algo-rithme à cet exemple pour
bien comprendre les différentes étapes et instructions
utilisées dans celui-ci. On pose :
Succ(xi) : L'ensemble de tous les successeurs de
xi dans G.
Inc(xi) : L'ensemble de tous les successeurs de
xi dans r qui lui sont incomparables
38
dans G.
ImmSucc(xi) : L'ensemble des successeurs
immédiats de xi.
B(a) = {a V y tel que y E ImmSucc(xi)}
avec a = Inc(xi)
Soit r = a, b, c, d, e, f, g une extension lineaire.
L'algorithme demarre à partir de f
avant dernier élément de l'extension
linéaire.
Pour f :
Succ(f) = {g};
Inc(f) = Ø;
Pour e :
Succ(e) = {g};
Inc(e) = {f};
ImmSucc(e) = {g};
B(f) = f V g = {g};
minB(f) = g ;
Pourd :
Succ(d) = {g};
Inc(d) = {e, f};
ImmSucc(d) = {g};
B(e) = e V g = {g};
minB(e) = g ;
B(f) = f V g = {g};
minB(f) = g ;
Pourc :
Succ(c) = {d,e,g};
Inc(c) = {f};
ImmSucc(c) = {d, e};
B(f) = f V d,f V e = {g};
minB(f) = g ;
Pourb :
Succ(b) = {d,e,f,g};
Inc(b) = {c};
ImmSucc(b) = {d, e, f};
B(c) = {c V d,c V e,c V f} = {d,e,g};
minB(c) n'existe pas, car d et e sont
incomparables. D'où G n'est pas le graphe
de couverture d'un treillis.
| 
