Discussion :

[larchicha]

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.

[Franck Dernoncourt]

J'ai lu rapidement, je me trompe ou la boucle "tant que" (tant que (b == faux) faire) n'a qu'une seule itération ?

EDIT: une seule ou bien une infinité.

[larchicha]

Bah elle a.autant d iteration qu il faut pour trouver une case qui soit vide... donc pas qu une seule...
ps : pas de ponctuation sur le telephone. desole.

[Franck Dernoncourt]

Mais avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
pour i de 1 à B.n faire :
   pour j de 1 à B.m faire :

tu parcours déjà toute la matrice B non ?

[larchicha]

En effet mais.que.se.passerait il si il y avait plus d une case.vide dans.mon tableau ? L algorithme est supposé inserer l element x une seule fois... mais pour repondre a ta question oui les 2 boucles pour parcourt l integralite du tableau

[Franck Dernoncourt]

En effet mais.que.se.passerait il si il y avait plus d une case.vide dans.mon tableau ?

Par vide tu veux dire "== + l'infini" ?

L algorithme est supposé inserer l element x une seule fois... mais pour repondre a ta question oui les 2 boucles pour parcourt l integralite du tableau

A quoi sert la boucle tant que alors ?