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{cases} O(1) \\ T(n-1) + T(n-2) + 1 \end{cases} $$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) |