PDA

Visualizza versione completa : Complessità algoritmo delle componenti connesse


LUCAB
11-06-2008, 00.56.27
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
11-06-2008, 01.15.05
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 :mm: e, cosa che interessa, che complessità abbiano :p


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 :D)

Sbavi
11-06-2008, 07.20.12
Bravo Dav (Y)

shadowDK
11-06-2008, 08.57.56
Bravo Dav ma questa non era molto difficile...

Thor
11-06-2008, 09.48.51
vero. ma la prox volta rispondi prima tu, allora ;)

shadowDK
11-06-2008, 10.30.40
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
11-06-2008, 11.00.54
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
11-06-2008, 11.12.15
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
11-06-2008, 16.48.15
Direi proprio di sì (Y) :)