[Algoritmi] Complessità asintotica in un grafo denso
Ciao a tutti, sto cercando di capire la differenza tra un grafo sparso e un grafo denso. Analizzando le seguenti domande sembra che nel caso del grafo sparso la procedura è semplice e basta applicare le regole generali. Per il grafo denso non riesco a capire come procedere.
Siano f(n) e g(n) la message complexity dell'algoritmo di Prim e l'algoritmo GHS asincroni, rispettivamente, quando eseguiti su un grafo sparso, i.e., con $m = Θ(n)$. Quali delle seguenti relazioni asintotiche è corretta?
a) $f(n) = Θ(g(n) * n) $
b) $f(n) = Θ(g(n)) $
c) $f(n) = o(g(n)) $
d) $f(n) = w(g(n))$ corretta
Siano f(n) e g(n) la message complexity dell'algoritmo di Prim e l'algoritmo GHS asincroni, rispettivamente, quando eseguiti su un grafo denso, i.e., con $m = Θ(n^2)$. Quali delle seguenti relazioni asintotiche è corretta?
a) $f(n) = Θ(g(n) * n) $
b) $f(n) = Θ(g(n))$ corretta
c) $f(n) = o(g(n)) $
d) $f(n) = w(g(n))$
Applicando le regole generali, io ottengo come risposta la d, poichè $f(n) = O(n^2)$ e $g(n) = O(n log n)$.
Dove sbaglio? Qual è la differenza con i grafi densi?
Siano f(n) e g(n) la message complexity dell'algoritmo di Prim e l'algoritmo GHS asincroni, rispettivamente, quando eseguiti su un grafo sparso, i.e., con $m = Θ(n)$. Quali delle seguenti relazioni asintotiche è corretta?
a) $f(n) = Θ(g(n) * n) $
b) $f(n) = Θ(g(n)) $
c) $f(n) = o(g(n)) $
d) $f(n) = w(g(n))$ corretta
Siano f(n) e g(n) la message complexity dell'algoritmo di Prim e l'algoritmo GHS asincroni, rispettivamente, quando eseguiti su un grafo denso, i.e., con $m = Θ(n^2)$. Quali delle seguenti relazioni asintotiche è corretta?
a) $f(n) = Θ(g(n) * n) $
b) $f(n) = Θ(g(n))$ corretta
c) $f(n) = o(g(n)) $
d) $f(n) = w(g(n))$
Applicando le regole generali, io ottengo come risposta la d, poichè $f(n) = O(n^2)$ e $g(n) = O(n log n)$.
Dove sbaglio? Qual è la differenza con i grafi densi?
Risposte
Sinceramente non mi è del tutto chiara la tua notazione. Che cosa rappresentano in questo contesto \(n\) ed \(m\)? Quando si lavora con i grafi si scrive spesso la complessità in funzione del numero di nodi, del numero di archi e nel caso di algoritmi concorrenti il numero di processi. Di solito ho visto usare le lettere \(V\), \(E\) e \(P\) per queste quantità. L'impressione è che \(m\) sia il numero di archi e che \(n\) il numero di nodi. È corretto?
Non so cosa siano le regole generali di cui parli, la complessità dovrebbe essere scritta in funziona delle due variabili \(n\) ed \(m\) nel tuo caso e a seconda del tipo di grafo, e quindi della relazione tra le due variabili, calcoli la complessità nella sola \(n\).
Non so cosa siano le regole generali di cui parli, la complessità dovrebbe essere scritta in funziona delle due variabili \(n\) ed \(m\) nel tuo caso e a seconda del tipo di grafo, e quindi della relazione tra le due variabili, calcoli la complessità nella sola \(n\).
esatto, n rappresenta i nodi ed m gli archi. m però non viene utilizzata nelle risposte, per questo non capisco
\(m\) non è presente nelle risposte perché vengono usate le relazioni \(m = \Theta(n)\) o \(m = \Theta(n^2\,)\) per eliminarla. In pratica sostituisci \(n\) o \(n^2\) nella tua complessità al posto di \(m\).
Però continuo a non capire perchè la risposta corretta nella seconda domanda è la b
Sinceramente non ricordo la complessità dei due algoritmi e quindi la risposta corretta. Qual'è la complessità in funzione delle due variabili nei due algoritmi?
Purtroppo so so solo che la complessità è $f(n) = O(n^2)$ per prim e $g(n) = O(n log n)$ per GHS. Ma non ho idea di come questa cambi in funzione di m
Mi correggo, la complessità dell'algoritmo GHS è $O(m+nlogn)$
Che succede quindi se scrivi \(n^2\) all posto di \(m\)?
ho $O(n^2+nlogn)$ . Ma come possono essere f(n) e g(n) in $f(n)=Θ(g(n))$ asintoticamente uguali?
Perché a questo punto il termine quadratico è quello che domina in entrambi gli algoritmi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo