Pagina 1 di 1

Ordine asintotico

MessaggioInviato: 18/03/2019, 18:37
da #Fede
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!!

Re: Ordine asintotico

MessaggioInviato: 23/03/2019, 21:36
da apatriarca
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)\)).

Re: Ordine asintotico

MessaggioInviato: 30/04/2019, 16:21
da #Fede
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) $ (?)

Re: Ordine asintotico

MessaggioInviato: 01/05/2019, 00:48
da apatriarca
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})\).