Forum Informatica Unict » LAUREA TRIENNALE (D.M. 270/04) » II anno » Algoritmi, 9 CFU (Moderator: Domenico Cantone) » Domanda grafi
Pages: [1]   Go Down
« precedente successivo »
Print
Author Topic: Domanda grafi  (Read 1204 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
RobyP
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 111
« on: 19-12-2010, 14:43:47 »
Salve, mi sfugge
1-quale è il tempo per cambiare rappresentazione di un grafo da lista a matrice e viceversa...

2-di conseguenza anche il tempo per costruire un grafo con lista e uno con matrice

(credo che non abbiano a che fare con lo spazio di memoria che occupano rispettivamente)

Grazie per le risposte  ciao bye
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #1 on: 19-12-2010, 19:58:36 »
io credo che sia O(E) 
Logged
RobyP
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 111
« Reply #2 on: 19-12-2010, 20:25:44 »
Ma cosa?
Logged
Naive
Matricola
*
Offline Offline

Posts: 57


Impossible is Nothing
« Reply #3 on: 19-12-2010, 20:33:43 »
Io avrei risposto per la prima e per la seconda
da lista a matrice O(V^2) e da matrice a lista O(V+E) ora non so...ho molti dubbi su questa parte...non prendere per certa la mia risposta Sad
Logged
Crasher
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417
« Reply #4 on: 19-12-2010, 21:56:10 »
Quote from: Sfregio on 19-12-2010, 20:33:43
Io avrei risposto per la prima e per la seconda
da lista a matrice O(V^2) e da matrice a lista O(V+E) ora non so...ho molti dubbi su questa parte...non prendere per certa la mia risposta Sad
Boh per come la penso io dovrebbe essere al contrario.
Da matrice a lista O(V^2) in quanto dovrà scandire ogni elemento della matrice (quindi 2 for) e inserirlo nella lista (se lo inserirà sempre in testa alla lista richiederà O(1) o sbaglio?)
Da lista a matrice O(E) o O(2E) se è orientato o meno...
cool
Logged
Diventa ciò che sei nato per essere
Naive
Matricola
*
Offline Offline

Posts: 57


Impossible is Nothing
« Reply #5 on: 19-12-2010, 22:03:32 »
per la prima hai ragione ho invertito...invece non capisco perchè la seconda ti viene O(E)
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.
« Reply #6 on: 19-12-2010, 22:26:53 »
Si forse ha ragione Crasher...in teoria da matrice a lista O(v^2), ma a questo punto da lista a matrice dovrebbe scorrere sia i vertici che la lista di adiacenza, quindi non dovrebbe essere O(V+E) ?
Logged
"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422
« Reply #7 on: 18-01-2011, 17:58:17 »
sono daccordo... più precisamente |V| per scorrere la lista e 2|E| per visitare tutte le liste delle adiacenze quindi |V|+ 2|E| =O (|V|+|E|)
credo che daréios abbia fatto questo ragionamento
Logged
Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
Pages: [1]   Go Up
Print
« precedente successivo »
Jump to: