Ordine asintotico

Messaggioda #Fede » 18/03/2019, 19:37

Ciao ragazzi, qualcuno saprebbe aiutarmi con il seguente esercizio?

Siano date le relazioni di ricorrenza

$ { ( H(n)=W(n/2) ),( W(n)=2H(n/4)+Theta (1) ):} $

con $ H(1)=Theta (1), W(1)=Theta(1) $ . Trovare l'ordine asintotico di A(n)=H(n)*W(n).

Grazie mille!!
#Fede
Starting Member
Starting Member
 
Messaggio: 12 di 14
Iscritto il: 20/04/2017, 16:33

Re: Ordine asintotico

Messaggioda apatriarca » 23/03/2019, 22:36

Il metodo classico per risolvere questo tipo di equazioni di ricorrenza consiste nel fare una sostituzione in modo da ottenere due equazioni di ricorrenza con una sola funzione. Nel tuo caso hai quindi
\[
\begin{cases}
H(n) = W\big(\frac{n}{2}\big) = 2H\big(\frac{n}{8}\big) + \Theta(1) \\
W(n) = 2H\big(\frac{n}{4}\big) + \Theta(1) = 2W\big(\frac{n}{8}\big) + \Theta(1)
\end{cases}
\]

Le due funzioni rispettano insomma la stessa equazione di ricorrenza. Per quanto riguarda il prodotto hai che la complessità asintotica è moltiplicativa (devi insomma risolvere l'equazione di ricorrenza e prenderne il quadrato per \(A(n)\)).
apatriarca
Moderatore
Moderatore
 
Messaggio: 5205 di 5222
Iscritto il: 08/12/2008, 21:37
Località: Londra

Re: Ordine asintotico

Messaggioda #Fede » 30/04/2019, 17:21

Grazie mille,
quindi per trovare l'ordine asintotico di A(n) risolvo l'equazione di ricorrenza con il master theorem, dove trovandomi nel 2 caso ottengo che W(n) è $ Theta (0) $ (?)
#Fede
Starting Member
Starting Member
 
Messaggio: 13 di 14
Iscritto il: 20/04/2017, 16:33

Re: Ordine asintotico

Messaggioda apatriarca » 01/05/2019, 01:48

Ti trovi nel primo caso, non nel secondo. Se \(c_{crit} = \log_8\,2 = 1/3,\) hai infatti che \(O(1) = O(n^0)\) e \(0 < 1/3\). Il risultato in questo caso è dato da \(\Theta(n^{c_{crit}}) = \Theta(\sqrt[3]{n})\).
apatriarca
Moderatore
Moderatore
 
Messaggio: 5215 di 5222
Iscritto il: 08/12/2008, 21:37
Località: Londra


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 4 ospiti