Algoritmo ricorsivo e complessità
Ciao ragazzi dovrei fare questo esercizio:
" Dare un algoritmo ricorsivo efficiente che calcoli la funzione f(n,k) così definita:
f(n,k) = 0 se n = 0 o k = 0
f(n,k) = f(n-1,k) + f(n,k-1) + n*k se n>0 e k>0
Discutere la complessità dell' algoritmo proposto."
In JAVA l' ho risolto in questo modo
public static int ricorsione(int n, int k){
if (n == 0 | k == 0){
return 0;
}
else{
return ricorsione(n-1,k) + ricorsione(n,k-1) + n*k;
}
}
però mi chiedo se questo algoritmo è efficiente(come lo chiedeva nel testo) oppure se si può migliorare.
Inoltre non so proprio come rispondere per quanto riguarda la complessità, se fosse stato un algoritmo iterativo per la complessità mi baso sui cicli for ( ad esempio se ce ne sono 2 annidati è n^2...) ma per la complessità negli algoritmi ricorsivi non so proprio come fare.
Vi ringrazio ragazzi.
" Dare un algoritmo ricorsivo efficiente che calcoli la funzione f(n,k) così definita:
f(n,k) = 0 se n = 0 o k = 0
f(n,k) = f(n-1,k) + f(n,k-1) + n*k se n>0 e k>0
Discutere la complessità dell' algoritmo proposto."
In JAVA l' ho risolto in questo modo
public static int ricorsione(int n, int k){
if (n == 0 | k == 0){
return 0;
}
else{
return ricorsione(n-1,k) + ricorsione(n,k-1) + n*k;
}
}
però mi chiedo se questo algoritmo è efficiente(come lo chiedeva nel testo) oppure se si può migliorare.
Inoltre non so proprio come rispondere per quanto riguarda la complessità, se fosse stato un algoritmo iterativo per la complessità mi baso sui cicli for ( ad esempio se ce ne sono 2 annidati è n^2...) ma per la complessità negli algoritmi ricorsivi non so proprio come fare.
Vi ringrazio ragazzi.
Risposte
Il testo dell'esercizio non è molto chiaro. La tua funzione implementa direttamente la funzione f in base alla definizione, ma non è certamente il metodo più veloce per calcolare il risultato. Si può infatti per prima cosa notare che la definizione di f è simmetrica per $n$ e $k$, scambiando infatti le due variabili si riottiene la stessa funzione. Notiamo inoltre che lo stesso valore viene calcolato più volte, sviluppando una volta entrambe le funzioni si ottiene infatti:
$f(n, k) = f(n-1, k) + f(n, k-1) + n*k = f(n-2, k) + f(n-1, k-1) + (n-1)*k + f(n-1, k-1) + f(n, k-2) + n*(k-1) + n*k$.
Come si può notare, $f(n-1, k-1)$ compare due volte e sviluppando ulteriormente i termini si otterrebbero altri doppioni. Si potrebbe allora memorizzare i valori già calcolati come descritto su wikipedia in questa pagina ricordandosi di considerare uguali $f(n,k)$ e $f(k,n)$ (per esempio scambiando $n$ e $k$ se $k > n$). È possibile che si possa fare ancora meglio di così comunque.
$f(n, k) = f(n-1, k) + f(n, k-1) + n*k = f(n-2, k) + f(n-1, k-1) + (n-1)*k + f(n-1, k-1) + f(n, k-2) + n*(k-1) + n*k$.
Come si può notare, $f(n-1, k-1)$ compare due volte e sviluppando ulteriormente i termini si otterrebbero altri doppioni. Si potrebbe allora memorizzare i valori già calcolati come descritto su wikipedia in questa pagina ricordandosi di considerare uguali $f(n,k)$ e $f(k,n)$ (per esempio scambiando $n$ e $k$ se $k > n$). È possibile che si possa fare ancora meglio di così comunque.
Ti ringrazio per la risposta, ora provo a farlo e poi, se ho problemi, lo posto.
Nel caso del mio algoritmo sapresti dirmi quant'è la complessità?
Come ho detto in precedenza, io so calcolare la complessità quando ci sono operazioni di assegnamento, operazioni di scelte e cicli vari. Però, non sono capace quando ci sono ricorsioni.Pertanto ti chiedo se puoi spiegarmelo che non riesco a capirlo
Grazie!
Nel caso del mio algoritmo sapresti dirmi quant'è la complessità?
Come ho detto in precedenza, io so calcolare la complessità quando ci sono operazioni di assegnamento, operazioni di scelte e cicli vari. Però, non sono capace quando ci sono ricorsioni.Pertanto ti chiedo se puoi spiegarmelo che non riesco a capirlo
Grazie!
fatemi capire mi piacciono problemi di questo tipo.
E' esatto dire che:
La funzione chiama se stessa 2 volte. (almeno fino a quando i parametri sono maggiori di zero).
Quindi ipotizzando parametri in ingresso uguali f(n,n) raddoppierà n volte. quindi avrà complessità pari a
O(2^n) che sarebbe esponenziale.
Tuttavia se abbiamo parametri f(m,n) o indipendentemente f(n,m) con n
.. svilupando come dice apatriarca mi sembra solo che è stato anticipata un iterazione nel codice (può essere un miglioramento alla funzione ma anche un rallentamento dipende dalla chache).. ma alla fine ci sarebbero comunque O chiamate alla funzione.. non ho tempo di spiegarlo ora ma lo aggiungerò in seguito quello che intendo devo andare ora ciao.
E' esatto dire che:
La funzione chiama se stessa 2 volte. (almeno fino a quando i parametri sono maggiori di zero).
Quindi ipotizzando parametri in ingresso uguali f(n,n) raddoppierà n volte. quindi avrà complessità pari a
O(2^n) che sarebbe esponenziale.
Tuttavia se abbiamo parametri f(m,n) o indipendentemente f(n,m) con n
.. svilupando come dice apatriarca mi sembra solo che è stato anticipata un iterazione nel codice (può essere un miglioramento alla funzione ma anche un rallentamento dipende dalla chache).. ma alla fine ci sarebbero comunque O chiamate alla funzione.. non ho tempo di spiegarlo ora ma lo aggiungerò in seguito quello che intendo devo andare ora ciao.
"DemoneRoss":
.. svilupando come dice apatriarca mi sembra solo che è stato anticipata un iterazione nel codice (può essere un miglioramento alla funzione ma anche un rallentamento dipende dalla chache).. ma alla fine ci sarebbero comunque O chiamate alla funzione.. non ho tempo di spiegarlo ora ma lo aggiungerò in seguito quello che intendo devo andare ora ciao.
Non ho mai consigliato di sviluppare la funzione, l'ho fatto solo per mostrare che la funzione viene chiamata spesso con gli stessi parametri. Era per mostrare quanto potesse essere utile memorizzare i risultati in una mappa e riutilizzarli.
"DemoneRoss":
fatemi capire mi piacciono problemi di questo tipo.
E' esatto dire che:
La funzione chiama se stessa 2 volte. (almeno fino a quando i parametri sono maggiori di zero).
Quindi ipotizzando parametri in ingresso uguali f(n,n) raddoppierà n volte. quindi avrà complessità pari a
O(2^n) che sarebbe esponenziale.
Tuttavia se abbiamo parametri f(m,n) o indipendentemente f(n,m) con n
.. svilupando come dice apatriarca mi sembra solo che è stato anticipata un iterazione nel codice (può essere un miglioramento alla funzione ma anche un rallentamento dipende dalla chache).. ma alla fine ci sarebbero comunque O chiamate alla funzione.. non ho tempo di spiegarlo ora ma lo aggiungerò in seguito quello che intendo devo andare ora ciao.
Il miglior algoritmo secondo me ha la stessa complessità del calcolo del triangolo di tartaglia
"vict85":
Il miglior algoritmo secondo me ha la stessa complessità del calcolo del triangolo di tartaglia
non l'ho capita. (comunque manco di humor penso sia normale.. P.S io lo conoscevo come il triangolo di pascal, ma d'ora in poi adotterò il nome "triangolo di tartaglia" visto che mi piace di più.)cmq si: ho verificato che il costo della versione memoizzata(evvai nuova parola imparata, il concetto l'ho pure gia usato, ma non sapevo avesse un nome che lo descrivesse) è uguale a quello della versione non memoizzata(almeno teoricamente). Però non ho voglia di spiegare il perchè
. L'unica differenza è che memoizzando troppo si incappa in ulteriori rallentamenti mentre per (n,m) piccoli è inutile memoizzare (anzi dannoso). LOL
Non avevo avuto tempo di mostrarlo... :p
Semplicemente ho calcolato che [tex]\displaystyle f(n,k) = \sum_{i = 0}^{\max\{k,n\}} \sum_{j=0}^{i}\binom{i}{j} \max\{(n-i+j)(k-j), 0\}[/tex]
Il fatto è che parti da
n*m +
f(n-1,k) + f(n,k-1)
n*m +
(n-1)k + n(k-1) +
f(n-2,k) + 2f(n-1,k-1) + f(n,k-2)
...
Non ti ricorda niente?
Semplicemente ho calcolato che [tex]\displaystyle f(n,k) = \sum_{i = 0}^{\max\{k,n\}} \sum_{j=0}^{i}\binom{i}{j} \max\{(n-i+j)(k-j), 0\}[/tex]
Il fatto è che parti da
n*m +
f(n-1,k) + f(n,k-1)
n*m +
(n-1)k + n(k-1) +
f(n-2,k) + 2f(n-1,k-1) + f(n,k-2)
...
Non ti ricorda niente?
Ma probabilmente esistono modi per scriverlo più efficaci.
Supponendo di utilizzare un array o una hash table per memorizzare i valori, la complessità dell'algoritmo è dato solo dal numero di volte che la funzione richiama se stessa. Memorizzando i valori già calcolati e sfruttando la simmetria dei due parametri si può ridurre di molto questo numero e mi chiedo quindi come puoi ritenere che la complessità rimanga la stessa. Ovviamente il discorso va fatto su valori di $n$ e $k$ sufficientemente grandi. Ma consideriamo già solo $3$ e $5$.
Nel caso in cui non si memorizzino i valori si ha:
(3, 5)
(2, 5) (3, 4)
(1, 5) (2, 4) (2, 4) (3, 3)
(0, 5) (1, 4) (1, 4) (2, 3) (1, 4) (2, 3) (2, 3) (3, 2)
(0, 4) (1, 3) (0, 4) (1, 3) (1, 3) (2, 2) (0, 4) (1, 3) (1, 3) (2, 2) (1, 3) (2, 2) (2, 2) (3, 1)
...
Nel caso in cui si memorizzano i valori si ha invece:
(3, 5)
(2, 5) (3, 4)
(1, 5) (2, 4) (3, 3)
(0, 5) (1, 4) (2, 3)
(0, 4) (1, 3) (2, 2)
(0, 3) (1, 2)
(1, 1)
(0, 1)
A me sembra evidente il vantaggio già solo per così pochi valori...
EDIT: Era ovviamente una risposta a
Nel caso in cui non si memorizzino i valori si ha:
(3, 5)
(2, 5) (3, 4)
(1, 5) (2, 4) (2, 4) (3, 3)
(0, 5) (1, 4) (1, 4) (2, 3) (1, 4) (2, 3) (2, 3) (3, 2)
(0, 4) (1, 3) (0, 4) (1, 3) (1, 3) (2, 2) (0, 4) (1, 3) (1, 3) (2, 2) (1, 3) (2, 2) (2, 2) (3, 1)
...
Nel caso in cui si memorizzano i valori si ha invece:
(3, 5)
(2, 5) (3, 4)
(1, 5) (2, 4) (3, 3)
(0, 5) (1, 4) (2, 3)
(0, 4) (1, 3) (2, 2)
(0, 3) (1, 2)
(1, 1)
(0, 1)
A me sembra evidente il vantaggio già solo per così pochi valori...
EDIT: Era ovviamente una risposta a
cmq si: ho verificato che il costo della versione memoizzata(evvai nuova parola imparata, il concetto l'ho pure gia usato, ma non sapevo avesse un nome che lo descrivesse) è uguale a quello della versione non memoizzata(almeno teoricamente). Però non ho voglia di spiegare il perchè . L'unica differenza è che memoizzando troppo si incappa in ulteriori rallentamenti mentre per (n,m) piccoli è inutile memoizzare (anzi dannoso). LOL
si hai ragione. Però io non ho raccolto i termini uguali.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo