[Algoritmi, complessità nel fattoriale]

Messaggioda zio_mangrovia » 11/09/2019, 08:15

Si parla di complessità nelle funzioni ricorsive, p.e. prendiamo il fattoriale:

Codice:
int fact (int n) {
if (n == 0)
   return 1;
else
   return n*fact(n-1);
}


Di seguito la definizione fornita dalla dispensa:
Immagine

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.
zio_mangrovia
Advanced Member
Advanced Member
 
Messaggio: 981 di 2074
Iscritto il: 13/06/2016, 17:42

Re: [Algoritmi, complessità nel fattoriale]

Messaggioda apatriarca » 12/09/2019, 02:06

In generale, data una relazione di equivalenza \(\sim\) tra elementi di un insieme, una classe di equivalenza \([f]\) è il sottoinsieme degli elementi \(g\) tali che \(g \sim f\). \(\mathcal O(f)\) è una classe di equivalenza per la relazione
\[ g \sim f \; \Longleftrightarrow \; \exists\, k,\, x_0 \in \mathbb R \quad g(x) \leq k\,f(x) \quad \forall x \geq x_0. \]
Quando si scrive una classe di equivalenza in una espressione di solito si sta dicendo che l'espressione vale per ogni funzione nella classe di equivalenza o che esiste una funzione di questa classe di equivalenza per cui l'espressione è valida. Sfortunatamente quale delle due interpretazioni si sta scegliendo dipende un po' dal contesto.

Con funzione concreta si riferisce semplicemente ad una delle funzioni della classe di equivalenza.

La moltiplicazione è inclusa nel termine \(\mathcal O(1)\) insieme alla selezione.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5295 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Algoritmi, complessità nel fattoriale]

Messaggioda zio_mangrovia » 12/09/2019, 08:05

apatriarca ha scritto:Con funzione concreta si riferisce semplicemente ad una delle funzioni della classe di equivalenza.

La moltiplicazione è inclusa nel termine \(\mathcal O(1)\) insieme alla selezione.


Tutto perfettamente chiaro.
Grazie 1000
zio_mangrovia
Advanced Member
Advanced Member
 
Messaggio: 982 di 2074
Iscritto il: 13/06/2016, 17:42


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite