Si parla di complessità nelle funzioni ricorsive, p.e. prendiamo il fattoriale:
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 tempo 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.