Relazioni di Ricorrenza

Iterazione

Questo metodo semplicemente consiste di calcolare tutte le operazioni e scriverlo con una notazione asintotica.

• slide

  

Sostituzione (induzione)

• slide

  

Analisi della relazione di ricorrenza di fibonacci

Si può dimostrare utilizzando l'induzione che una relazione di questo tipo

$$T(n)=\{\begin{array}{l}O(1)\\ T(n-1)+T(n-2)+1\end{array}$$

Si trova che è $O(2^n),\Omega (2^{n/2})$

Analisi finale.

Si può creare una stima corretta, utilizzando la formula per il calcolo di fibonacci (che dimostri facendo osservazioni su una funzione generatrice di essa, una serie infinita).

Albero di ricorsione

• slide

  

Teorema dell’esperto (master)

Questo teorema permette di stabilire subito la stima asintotica per tutte le ricorrenze nella forma

$T(n)=aT(n/b)+f(n)$ ed è diviso in tre casi:

23/03	Ricordo tutto come se fosse ieri
09/04	Non ti ricordi esattamente tutto (teoricamente albero di ricorsione, ma in pratica non lo so se lo fa)
in tre casi:

23/03	Ricordo tutto come se fosse ieri
09/04	Non ti ricordi esattamente tutto (teoricamente albero di ricorsione, ma in pratica non lo so se lo fa)