Complexité d'un algorithme
Bonsoir à tous et à toutes,
Je viens vers vous pour une question assez bebete il me semble mais, ça fait quelques heures que je bûche dessus et j'ai mal à la tête...
Ma vie est sûrement le dernier de vos soucis donc je me lance :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void Inserer(B : batière, x : entier) :
i, j : entiers ;
b : boolean ;
b = faux ;
tant que (b == faux) faire :
pour i de 1 à B.n faire :
pour j de 1 à B.m faire :
si (B[i][j] == + l'infini) :
B[i][j] = x ; // insère l element x dans la case vide
b = vrai ;
fin si.
fin pour
fin pour
fin tant que
pour i de 1 à B.n faire :
pour j de 1 à B.m faire :
Retablir(B,i,j); // retablit le bordel causé par l insertion
fin pour
fin pour
fin algo |
Que vous ne me traitiez pas de martien, il s'agit d'une batiere (tableau de n lignes * m colonnes triées par ordre croissant dans laquelle les cases vides sont identifiées par + l infini).
B.n et B.m correspondent aux dimensions de la batière.
Le code de la fonction Retablir est ici inutile car ma question est : quelle est la complexité de l'algorithme Insérer ?
Je ne saurais vous donner ma réponse car je bloque sur le while(!b)...sinon pour les 2 doubles boucles "pour" je vois du O(2*n*m) ~~ O(n*m).
Une deuxième chose tant que je vous tiens... concernant l'algorithme en lui même : il y a surement beaucoup plus simple mais je vous donne ma vision des choses :
Il y a un élément à insérer dans la batière (supposée non pleine) et seules les cases "+l'infini" sont vides... seulement il peut y avoir plus d'une case vide, d'où l'emploi du boolean... et à fortiori de la boucle while.
Par contre pour la 2ème double boucle "pour", j'ai pensé que étant donné la triple boucle (while / pour / pour) faites avant , la complexité de ma 2eme double boucle serait "avalé" dans la 1ere [O(2*n*m) ~~ O(n*m)].
Le post est long à lire, je m'en excuse à l'avance et remercie ceux qui voudront bien m'aider.
Cordialement.
