3.2.3 Etude de la compléxité
Dans cette section, nous allons étudier la
compléxité, dans le pire des cas, de
l'algorithme GENALL. Soit O l'ensemble de transaction
d'une base, Y l'ensemble
d'attributs de la base et F l'ensemble des concepts
trouvés. L'étude de la boucle :
Pour(ligne 5) donne:
- L'instruction 6 s'effectue en O(|Y |) étant
donné que dans le pire des cas, nous
allons effectuer une intersection avec tous les attributs de la
base.
- L'instruction 7 s'effectue en O(|Y |) puisqu'on ne
peut avoir au maximum que
|Y | branches.
- L'instruction 13 peut se faire dans le pire des cas en
O(|O|).
- La recherche dans la liste L (ligne 14) est
réalisé en O(|F |
2 ) dans le pire de cas.
En effet, une iteration peut donner autant de nouveau concept
qu'il y a dans
|F |.
- La boucle Pour(ligne 18) peut se repeter au maximum deux
fois.
- Celle de la ligne 19 se répète |ImmSucc|
fois.
- La fonction Compare - concept se fait
O(|Y |)
De ce fait la complexité des instructions 5 - 23 est
O(|F | + 2|Y | + |O| + |F |
2 +
2|Y |.|ImmSucc|). L'instruction 25
s'effectue en O(|ImmSucc|), alors que la
complexité de l'instruction 28 vaut O(|Y | +
|liste - gen|). Par conséquent la
complexité du bloc des instructions (25 - 34) vaut :
O(|F |
2 * |ImmSucc|2.(|Y
| + |liste - gen|)).
Etant donné que notre algorithme se répète
|K| fois (la première boucle Pour
de la ligne 3 ). Il vient alors que la compléxité
totale de l'algorithme est :
O(|K|.|F |[1 2 *
|ImmSucc|2.(|Y | + |liste
- gen|) + |K| + |F |
2 ]).[13]
| 
