Passa al tema normale
Discussioni su argomenti di Informatica

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

Ordine asintotico

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!!

Re: Ordine asintotico

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

Re: Ordine asintotico

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) $ (?)

Re: Ordine asintotico

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})\).
Rispondi al messaggio