Telefonino.net network
 
| HOMEPAGE | INDICE FORUM | REGOLAMENTO | ::. NEI PREFERITI .:: | RSS Forum | RSS News | NEWS web | NEWS software |
| PUBBLICITA' | | ARTICOLI | WIN XP | VISTA | WIN 7 | REGISTRI | SOFTWARE | MANUALI | RECENSIONI | LINUX | HUMOR | HARDWARE | DOWNLOAD | | CERCA nel FORUM » |

Torna indietro   WinTricks Forum > Software > Programmazione

Notices

Rispondi
 
Strumenti discussione
Vecchio 11-06-2008, 00.56.27   #1
LUCAB
Junior Member
 
Registrato: 16-09-2004
Messaggi: 118
LUCAB promette bene
Complessità algoritmo delle componenti connesse

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

Codice:
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
LUCAB non è collegato   Rispondi citando
Vecchio 11-06-2008, 01.15.05   #2
Dav82
Gold Member
Top Poster
 
Registrato: 18-07-2002
Messaggi: 6.399
Dav82 promette bene
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

Codice:
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 )
Dav82 non è collegato   Rispondi citando
Vecchio 11-06-2008, 07.20.12   #3
Sbavi
Gold Member
Top Poster
 
L'avatar di Sbavi
 
Registrato: 04-09-2004
Loc.: لثلاثم عفمشةشف
Messaggi: 5.467
Sbavi promette bene
Bravo Dav (Y)
___________________________________

SOS ABRUZZO
Sbavi non è collegato   Rispondi citando
Vecchio 11-06-2008, 08.57.56   #4
shadowDK
Senior Member
 
Registrato: 21-03-2008
Loc.: From Lugano (CH)...finally!
Messaggi: 330
shadowDK promette bene
Bravo Dav ma questa non era molto difficile...
shadowDK non è collegato   Rispondi citando
Vecchio 11-06-2008, 09.48.51   #5
Thor
Il re di bastoni
Top Poster
 
L'avatar di Thor
 
Registrato: 26-04-2001
Loc.: Milàn
Messaggi: 23.413
Thor promette bene
vero. ma la prox volta rispondi prima tu, allora
___________________________________

Un giorno in cui voleva fare il cattivo, Mister Coniglietto sbirciò oltre la siepe e vide che l'orto del Contadino Fred era pieno di lattuga fresca e verde; Mister Coniglietto, invece, non era pieno di lattuga per niente. E ciò gli parve un'ingiustizia.
Sono un Vampiro! I am a Vampire!
Thor non è collegato   Rispondi citando
Vecchio 11-06-2008, 10.30.40   #6
shadowDK
Senior Member
 
Registrato: 21-03-2008
Loc.: From Lugano (CH)...finally!
Messaggi: 330
shadowDK promette bene
Quota:
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!
shadowDK non è collegato   Rispondi citando
Vecchio 11-06-2008, 11.00.54   #7
LUCAB
Junior Member
 
Registrato: 16-09-2004
Messaggi: 118
LUCAB promette bene
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
LUCAB non è collegato   Rispondi citando
Vecchio 11-06-2008, 11.12.15   #8
shadowDK
Senior Member
 
Registrato: 21-03-2008
Loc.: From Lugano (CH)...finally!
Messaggi: 330
shadowDK promette bene
Quota:
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!
shadowDK non è collegato   Rispondi citando
Vecchio 11-06-2008, 16.48.15   #9
Dav82
Gold Member
Top Poster
 
Registrato: 18-07-2002
Messaggi: 6.399
Dav82 promette bene
Direi proprio di sì (Y)
Dav82 non è collegato   Rispondi citando
Rispondi


Utenti attualmente attivi che stanno leggendo questa discussione: 1 (0 utenti e 1 ospiti)
 
Strumenti discussione

Regole di scrittura
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is ON
Gli smilies sono ON
[IMG] è ON
Il codice HTML è OFF

Vai al forum

Discussioni simili
Discussione Autore discussione Forum Risposte Ultimo messaggio
Solo 3% (non 44%) le perdite delle Major dovute al P2P Macao Segnalazioni Web 0 24-01-2008 05.04.51
La musica gode con il P2P Macao Segnalazioni Web 0 04-10-2007 00.44.07
(FG) Sped. --- Vendo componenti hardware PC, prezzi da capogiro... --- GAE81 Mercatino Usato 1 06-12-2006 18.13.20
Problema con il comando Apri delle cartelle Maximus Windows 7/Vista/XP/ 2003 1 07-02-2005 11.26.26
Che ne pensate delle nuove tariffe Enel? handyman Chiacchiere in libertà 5 13-01-2005 20.14.57

Orario GMT +2. Ora sono le: 10.25.49.


E' vietata la riproduzione, anche solo in parte, di contenuti e grafica.
Copyright © 1999-2017 Edizioni Master S.p.A. p.iva: 02105820787 • Tutti i diritti sono riservati
L'editore NON si assume nessuna responsabilità dei contenuti pubblicati sul forum in quanto redatti direttamente dagli utenti.
Questi ultimi sono responsabili dei contenuti da loro riportati nelle discussioni del forum
Powered by vBulletin - 2010 Copyright © Jelsoft Enterprises Limited.