Complessita' computazionale funzione

[AtoXx]

perfetto, ho capito...e c'hai ragione ..adesso pranzo appena finisco torno subito e faccio i calcoli, auguri per domani

[AtoXx]

allora usando quella formula ottengo questo:


F(n)= O(2^(logbase3 di n)) + 3n - 3(2/3)^(logbase3 di n)

[YuYevon]

Ciao AtoXx, ora ho un po' di tempo per completare il discorso di ieri (spero ti serva ancora).

Allora innanzitutto mi trovo esattamente come te anche se tu commetti un'imprecisione, dovuta all'errato utilizzo della notazione "O grande".

F(n)= O(2^(logbase3 di n)) + 3n - 3(2/3)^(logbase3 di n)

questa scrittura non ha senso, perché tu in sostanza dici che F(n) è nell'ordine di 2 elevato a ecc... + una certa cosa. Questo non è corretto, perché nel momento in cui tu stabilisci il limite asintotico superiore ("O grande", appunto) della complessità di tempo, non hai bisogno di aggiungere altro. In sostanza lì avresti dovuto scrivere

F(n)= O(2^(logbase3 di n)) (e basta)

quello che forse volevi dire tu è questo:

F(n)= 2^(logbase3 di n) + 3n - 3(2/3)^(logbase3 di n)

e comunque c'è un piccolo errore... è:

F(n)= 2^(logbase3 di n) + 3n - 3n(2/3)^(logbase3 di n)

giunti a questo punto, abbiamo determinato la forma analitica della complessità di tempo. Se vogliamo stabilire l'ordine di grandezza (quindi il limite asintotico superiore) di tale complessità, dobbiamo vedere quale di quei termini prevale (trattandosi di una somma di termini).

Innanzitutto, dobbiamo giocare un po' con le proprietà dei logaritmi, in particolare ci serviranno queste (indico "logaritmo in base a di x" così: log_a(x)) molto probabilmente le conosci, ma le riporto per chiarezza

1) x^(log_a(z)) = z^(log_a(x)) (in sostanza scambiamo x e z)

2) log(x) + log(y) = log(xy)

e anche questa abbastanza nota (relativa alle funzioni espsonenziali)

3) (x^a)(x^b) = x^(a+b)

a questo punto procediamo.

F(n)= 2^(logbase3 di n) + 3n - 3n(2/3)^(logbase3 di (n))

possiamo scriverlo (per la proprietà 1) come

F(n)= n^(logbase3 di 2) + 3n - 3n(n)^(logbase3 di 2/3)

poi, consideriamo questo termine qui

3n(n)^(logbase3 di 2/3)

abbiamo n "elevato a 1" per n elevato a quella-roba-lì, quindi possiamo fare un'unica potenza in base n e come esponente la somma degli esponenti (proprietà 3)

3n^(1 + logbase3 di 2/3)

ora 1 all'esponente possiamo scriverlo come logaritmo nella stessa base dell'altro, quindi

3n^(logbase3 di 3 + logbase3 di 2/3)

per la proprietà 2, questo è

3n^(logbase3 di 3*(2/3)) ossia 3n^(logbase3 di 2)

ritorniamo alla F(n). Sarà diventata

F(n)= 2^(logbase3 di n) + 3n - 3n^(logbase3 di 2)

sommiamo il primo e il terzo termine e abbiamo

F(n)= -2n^(logbase3 di 2) + 3n

il termine di grado superiore è il secondo, perché logbase3 di 2 è minore di 1... quindi possiamo felicemente concludere che

F(n) = O(n)

A ulteriore garanzia, il teorema dell'esperto di cui ti dicevo sopra da esattamente lo stesso risultato in un paio di passaggi... quindi direi che la soluzione è corretta

(se proprio la vogliamo dire tutta, il metodo dell'esperto dice in questo caso che F(N) è "TETA" di n... in pratica dovremmo dimostrare che n è anche limite inferiore oltre che superiore, ma penso conti ben poco).

[AtoXx]

ah ok...ti ringrazio.... non ho avuto linea e t'ho potuto risp solo adesso....