Analisi algoritmo ricorsivo

Messaggioda david9310 » 12/02/2020, 12:11

Salve, ho difficoltà a risolvere il costo asintotico della funzione f() del seguente algoritmo

Codice:
static int f(int q) {
if(q <= 1) return q;
if((q % 2) == 0) return g(q>>1);
else return f(q-1);
}
static int g(int r) {
if(r <= 1) return f(r);
if((r % 3) == 0) return f(r/3);
else return f(r+1);
}


Ho pensato che il caso peggiore è quello in cui q>>1 non è mai divisibile per 3 e che il numero di chiamate di g siano logaritmiche in funzione di q, ma non riesco ad andare avanti.Qualcuno potrebbe spiegarmi come ci si muove quando mi trovo davanti ad algoritmi simili?
Grazie per le eventuali risposte
david9310
Starting Member
Starting Member
 
Messaggio: 1 di 1
Iscritto il: 12/02/2020, 11:22

Re: Analisi algoritmo ricorsivo

Messaggioda apatriarca » 13/02/2020, 01:58

Di solito avere due funzioni è abbastanza scomodo ed è meglio riportarsi ad una sola. In questo caso hai che \(f(q) = g\bigl( \lfloor q/2 \rfloor \bigr)\) usando il fatto che se \(q\) è pari \( \lfloor q/2 \rfloor = q/2, \) e se è dispari allora \( q - 1 \) sarà pari e \( \lfloor q/2 \rfloor = (q - 1)/2. \) Puoi a questo punto sostituire questa funzione al posto di \(f\) nella \(g\) ottenendo
\[
g(r) =
\begin{cases}
r & \text{ se } r \leq 1 \\
g\left( \left\lfloor \frac{r/3}{2} \right\rfloor \right) = g \bigl( \lfloor r/6 \rfloor \bigr) & \text{ se $r$ divisibile per $3$} \\
g\left( \left\lfloor \frac{r + 1}{2} \right\rfloor \right) = g \bigl( \operatorname{rpi}(r/2) \bigr) & \text{altrimenti}
\end{cases}
\]
dove \( \operatorname{rpi} \) è la funzione che arrotonda all'intero più vicino (con il valore intermedio che va all'intero più grande). Per la funzione \(g\) il caso peggiore è quindi quello in cui non hai mai un numero divisibile per \(3\) e la funzione verrà eseguita \( log_2(r) \) volte. Nel caso migliore verrà eseguita solo \( \log_6(r) \) volte. Nota comunque che da punto di vista della complessità asintotica tutti i logaritmi sono uguali.. Differiscono infatti da una costante positiva come si può vedere usando il cambiamento di base dei logaritmi. Per cui alla fine la differenza non è così grossa.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5369 di 5389
Iscritto il: 08/12/2008, 20:37
Località: Londra


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 7 ospiti