Esercizio ricorrenze

[jJjjJ1]

Scrivere un algoritmo che calcoli il valore $T_n$ definito dalla seguente ricorrenza:

$T_n = 1$ se $ n <= 3 $
$T_n = T_{n-1}T_{n-2} + T_{n-3} + 1$ altrimenti

e analizzarne il tempo di esecuzione.

Sto iniziando ora a studiare questa materia quindi scusate la domanda banale, l'esercizio è quello sopra, per la parte dell'algoritmo è facile scrivere:

algoritmo ricorrenza( intero n )
       if( n <= 3 ) then return 1
       return ricorrenza( n-1)*ricorrenza(n-2) + ricorrenza(n-3) + 1

Per l'ultima parte non so se ho fatto bene, potreste aiutarmi?

Io ho pensato che il metodo migliore sia studiare l'albero delle ricorrenze, osservo che il ramo più lungo dell'albero è quello a sinistra e si ha che l'altezza dell'albero è $ k = n - 3 $
Inoltre, ad ogni livello $t$ l'albero ha massimo $3^t$ nodi, infine osservo che ad ogni livello il costo delle chiamate è $O(n)$ dunque si ha che l'algoritmo ha costo di esecuzione $O(n^2)$ Giusto?

[apatriarca]

Un modo per verificare sperimentalmente se una particolare ricorrenza rispetta il tempo di esecuzione che hai calcolato è quello di scrivere un piccolo programma che calcola il numero di volte in cui richiami la ricorrenza. In questo caso si tratta di restituire 1 nel caso in cui n sia minore di 3 e la somma delle ripetizioni della ricorrenza con n=n-1,n-2 e n-3 altrimenti. Qualcosa come segue insomma:

function ricorrenza(n)
    if (n <= 3) then 
        return 1
    else
        return ricorrenza(n-1) + ricorrenza(n-2) + ricorrenza(n-3)
    end
end

Il risultato, per n che varia da 1 a 30 è il seguente:

1
1
1
3
5
9
17
31
57
105
193
355
653
1201
2209
4063
7473
13745
25281
46499
85525
157305
289329
532159
978793
1800281
3311233
6090307
11201821
20603361

Come vedi sale molto più velocemente del quadrato di n.. Il tempo di esecuzione è almeno esponenziale, come si può facilmente osservare notando che \(O(T_n) \ge O( 3 T_{n-3} ) = O( 3^k T_{n-k} ) = O( 3^{n/3} ). \)

[jJjjJ1]

EDIT

Vediamo se ho capito, partiamo da capo. Ogni chiamata della funzione mi costa $O(1)$ più le chiamate ricorsive. Mi faccio l'albero delle ricorrenze ed osservo che il ramo più lungo è il sinistro, dunque l'albero ha $k = n - 3$ livelli. Per ogni livello $t$ l'albero ha al più $3^t$ nodi che hanno costo $O(1)$. Perciò si ha:

$T(n) <= O(1) + 3O(1) + ... + 3^( n - 3 ) O( 1 ) = O( 3^n )$

giusto?

[apatriarca]

Perché il ramo di sinistra ha \( k = n - 3 \) nodi secondo te? Il percorso più lungo dalla radice alle foglie si avrà sempre quando scegli di percorrere il ramo corrispondente a ricorrenza(n-1) e quindi si avrà un'altezza di \(n\).. Credo dovresti in generale argomentare di più i tuoi passaggi..

[jJjjJ1]

Dico questo perché come dici te il ramo più lungo è quello che si trova percorrendo le chiamate con ricorrenza(n - 1). Dunque ogni chiamata agisce sul numero precedente diminuito di uno, la chiamata k-esima sarà in generale effettuata sul numero $n-k$ Osservo ora che il caso base della ricorrenza si ha per $n <= 3$ dunque se $k = n - 3$ lo si raggiunge, da cui l'altezza dell'albero è $n-3$ Io ragionavo così poi ho sbagliato di sicuro ahahah