Complessità algoritmo delle componenti connesse

[LUCAB]

Ciao raga.Vi posto lo pseudo codice dell'algoritmo delle componenti connesse mi sapreste dier la complessità precisa??? non sono mai stato ferrato su ste cose se mi potete dare una mano vi ringrazio.Ciao

1. VAR Integer Matrice_label [N,N]
2. VAR Integer Immagine [N,N]
3. VAR Integer Label = 0
4. VAR Integer i,j = 0
5. VAR Integer Soglia

6. for i = 1… N
7. for j = 1… N
8. Matrice_label [ i , j ] = 0
9. end for
10. end for

11. for i = 1… N
12. for j = 1… N
13. if (Immagine [ i , j ] < Soglia)
14. if ( Matrice_label [ i-1 , j ] = 0 AND Matrice_label [ i , j-1 ] = 0 )
15. Label =Label + 1
16. Matrice_label [ i , j ] = Label
17. else
18. if ( Matrice_label [ i-1 , j ] != 0 )
19. Matrice_label [ i , j ] = Matrice_label [ i - 1 , j ]
20. if ( Matrice_label [ i , j-1 ] != 0 )
21. Matrice_label [ i , j ] = Matrice_label [ i , j - 1 ]
22. if ( Matrice_label [ i-1 , j ]!= 0 AND Matrice_label [ i , j-1 ]!= 0 )
23. Matrice_label [ i , j ] = Matrice_label [ i - 1 , j
24. classe_equivalenza( Matrice_label [ i - 1 , j ] , Matrice_label [ i , j - 1 ] )
25. end for
26. end for

27. for i = 1… N
28. for j = 1… N
29. aggiorna_equivalenze
30. end for
31. end for

[Dav82]

Sono un filo arrugginito da quando ho fatto Info3 e Info Teorica, cmq vediamo un po'

Ho indentato il codice, e probabilmente c'è bisogno che confermi l'indenting... non ho ben chiaro come siano le dipendenze degli if/else e i relativi blocchi di istruzioni (poi magari non cambia neppure la complessità dell'algoritmo, ma prima di far conti...). Il codice è indentato con tabulazioni dopo il numero di riga

1.	VAR Integer Matrice_label [N,N]
2.	VAR Integer Immagine [N,N]
3.	VAR Integer Label = 0
4.	VAR Integer i,j = 0
5.	VAR Integer Soglia



6.	for i = 1… N
7. 		for j = 1… N
8.			Matrice_label [ i , j ] = 0
9.		end for
10.	end for


11.	for i = 1… N
12.		for j = 1… N
13.			if (Immagine [ i , j ] < Soglia)
14.				if ( Matrice_label [ i-1 , j ] = 0 AND Matrice_label [ i , j-1 ] = 0 )
15.					Label =Label + 1
16.					Matrice_label [ i , j ] = Label
17.				else
18.					if ( Matrice_label [ i-1 , j ] != 0 )
19.						Matrice_label [ i , j ] = Matrice_label [ i - 1 , j ]
20.			if ( Matrice_label [ i , j-1 ] != 0 )
21.				Matrice_label [ i , j ] = Matrice_label [ i , j - 1 ]
22.			if ( Matrice_label [ i-1 , j ]!= 0 AND Matrice_label [ i , j-1 ]!= 0 )
23.				Matrice_label [ i , j ] = Matrice_label [ i - 1 , j
24.			classe_equivalenza( Matrice_label [ i - 1 , j ] , Matrice_label [ i , j - 1 ] )
25.		end for
26.	end for


27.	for i = 1… N
28.		for j = 1… N
29.			aggiorna_equivalenze
30.		end for
31.	end for

Ci sono poi due funzioni, classe_equivalenza e aggiorna_equivalenze, che non si sa bene cosa siano e, cosa che interessa, che complessità abbiano


Al momento so dirti solo questo:


Righe 6-10: due cicli 1..N innestati, complessità N*N = N^2.

Righe 27-31: due cicli 1..N innestati, complessità N^2 * complessità(aggiorna_equivalenze)

Righe: 11-26: due cicli 1..N innestati, complessità N^2 * complessità(Righe 13..24)

Complessità intero algoritmo: massimo delle tre complessità calcolate sopra.



(componenti connesse di un grafo... ricerca operativa eh )

[Sbavi]

Bravo Dav (Y)

[shadowDK]

Bravo Dav ma questa non era molto difficile...

[Thor]

vero. ma la prox volta rispondi prima tu, allora

[shadowDK]

Inviato da Thor

vero. ma la prox volta rispondi prima tu, allora

A quell'ora sono già nel mondo dei sogni...comunque, invece, mi ha impressionato il calcolo delle probabilità per il passaggio del girone dell'italia (sempre Dav) in off topic...un mostro!

[LUCAB]

Grazie 1000 sei stato gentilissimo....
Per quanto riguarda la funzione classe_equivalenza() assegna solamente due valori in un vettore... quindi è una costante...
Mentre aggiorna_equivalenze() dovrebbe scorrere nuovamente la matrice delle label per aggiornare nuovamente le label in base alle classi di ecquivalenze settata prima...
Dovrebbe essere un N^4 più o meno giusto????
Dunque potremmo dire che la complessità totale è di tipo polinomiale ... giusto??? si dice così???
Grazie ancora

[shadowDK]

Inviato da LUCAB

Grazie 1000 sei stato gentilissimo....
Per quanto riguarda la funzione classe_equivalenza() assegna solamente due valori in un vettore... quindi è una costante...
Mentre aggiorna_equivalenze() dovrebbe scorrere nuovamente la matrice delle label per aggiornare nuovamente le label in base alle classi di ecquivalenze settata prima...
Dovrebbe essere un N^4 più o meno giusto????
Dunque potremmo dire che la complessità totale è di tipo polinomiale ... giusto??? si dice così???
Grazie ancora

Esatto...se le cose (aggiorna e classe_equivalenza) stanno come hai detto tu dovrebbe essere:
N^4 + 2*N^2, ossia N^4...
Anche la denominazione (complessità polinomiale) dovrebbe essere corretta!

[Dav82]

Direi proprio di sì (Y)