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 : Sélectionner tout - Visualiser dans une fenêtre à part
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.