[Algoritmi] Complessità asintotica in un grafo denso

[minato91]

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?

[apatriarca]

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\).

[minato91]

esatto, n rappresenta i nodi ed m gli archi. m però non viene utilizzata nelle risposte, per questo non capisco

[apatriarca]

\(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\).

[minato91]

Però continuo a non capire perchè la risposta corretta nella seconda domanda è la b

[apatriarca]

Sinceramente non ricordo la complessità dei due algoritmi e quindi la risposta corretta. Qual'è la complessità in funzione delle due variabili nei due algoritmi?

[minato91]

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

[minato91]

Mi correggo, la complessità dell'algoritmo GHS è $O(m+nlogn)$

[apatriarca]

Che succede quindi se scrivi \(n^2\) all posto di \(m\)?

[minato91]

ho $O(n^2+nlogn)$ . Ma come possono essere f(n) e g(n) in $f(n)=Θ(g(n))$ asintoticamente uguali?