- Codice:
int fact (int n) {
if (n == 0)
return 1;
else
return n*fact(n-1);
}
Di seguito la definizione fornita dalla dispensa:
Ho difficoltà a capire due punti:
1.
Non possiamo però semplificare completamente le espressioni O-grande così ottenute, perchè esse in generale contengono funzioni concrete oltre a classi di funzioni. Quindi è necessario a questo punto rimpiazzare le classi di funzioni che compaiono in una espressione con funzioni concrete, anche se espresse mediante costanti simboliche.
Cosa si intende per funzioni concrete e classi di funzioni? Non capisco.
2.
il testo riporta:
Per $T(n)$ , $n>0$ , abbiamo un temp $O(1)$ complessivo per il test, la chiamata ricorsiva e la moltiplicazione più il tempo per l'esecuzione della funzione applicata a $n-1$, quindi: $T(n) = O(1)+ T(n-1)$
OK per $O(1)$ tempo per il test cioè $if (n == 0)$
OK per la chiamata ricorsiva $T(n-1)$ cioè $fact(n-1)$
a questo punto ho già esaurito i termini dell'espressione $O(1)+ T(n-1)$... allora dove si evincono i tempi per la moltiplicazione e l'esecuzione della funzione applicata a $n-1$ ? Forse sono assorbiti a $O(1)$ ?
Grazie in anticipo per il vostro contributo.