PDA

Visualizza la versione completa : Complessita' computazionale funzione


AtoXx
04-02-2009, 11:44
SAlve a tutti, ho un piccolo dubbio: ho fatto un compito e ho dei dubbi sulla complessità della funzione che avevo nel compito.
Vi allego la foto del testo.
A me la complessità è venuta 2^(log in base3 di n)
se qualcuno può darmi una mano ne sarei felice

Stoicenko
04-02-2009, 11:48
e che centra con la programmazione? questo è un problema di algoritmi...

AtoXx
04-02-2009, 12:18
Originariamente inviato da Stoicenko
e che centra con la programmazione? questo è un problema di algoritmi...

non sapevo dove postarlo...e questa mi è sembrata la sezione più adatta...

LeleFT
04-02-2009, 12:50
Originariamente inviato da AtoXx
non sapevo dove postarlo...e questa mi è sembrata la sezione più adatta...
La sezione può andare anche bene... ma era più difficile scrivere direttamente il testo dell'esercizio o scannerizzare, salvare e uploadare un'immagine, non permettendo, quindi, ad altri di risalire al tuo stesso problema tramite la ricerca e rendendo più difficoltosa la lettura dello stesso?

:dhò:

Ciao. :ciauz:

YuYevon
04-02-2009, 12:55
Come hai impostato la relazione di ricorrenza? Hai usato il metodo dell'esperto (o "principale")? Se sì, in quale dei tre casi ti ritrovi? Dal risultato che hai scritto direi che hai verificato il primo... ma a me non sembra che siano soddisfatte le ipotesi di quest'ultimo...

la relazione di ricorrenza dovrebbe essere

F(N) = 1 se N<=1
e
F(N) = 2[F(N/3)] + N se N>1

direi piuttosto che siamo nel terzo caso del teorema e non nel primo.

AtoXx
04-02-2009, 13:02
Originariamente inviato da YuYevon
Come hai impostato la relazione di ricorrenza? Hai usato il metodo dell'esperto (o "principale")? Se sì, in quale dei tre casi ti ritrovi? Dal risultato che hai scritto direi che hai verificato il primo... ma a me non sembra che siano soddisfatte le ipotesi di quest'ultimo...

la relazione di ricorrenza dovrebbe essere

F(N) = 1 se N<=1
e
F(N) = 2[F(N/3)] + N se N>1

direi piuttosto che siamo nel terzo caso del teorema e non nel primo.

la funzione di ricorrenza è quella lì...non so come si chiami il metodo(il prof nn ce l'ha detto) cmq ho iterato più volte la funzione di ricorrenza per N>1, fino a trovare una generalizzazione, che è la seguente:
F(n)=2^k *F(n/3^k) + sommatoria con i=1 fino a k di O(1)

A questo punto impongo la condizione d'uscita, che è: n=3^k. Adesso sosituisco a k=log inbase3 di n.
F(n)=2^(logbase3 di n)+ sommatoria con i=1 fino a logbase3 di n di O(1)
il tutto si riduce ad
2^(logbase3 di n) dato che la sommatoria è di O(1)...
Spero di farmi capire :S

YuYevon
04-02-2009, 13:40
Ah ok, quindi non conoscete il metodo dell'esperto... è un teorema (ovviamente con una signora dimostrazione) che ti consente di risolvere alcune relazioni di ricorrenza semplicemente verificando delle ipotesi iniziali. Vabbè comunque leggo che hai usato il metodo iterativo - sul quale non sono molto pratico, quindi correggimi se sbaglio - però provando a sviluppare i calcoli non mi trovo esattamente con te quando dici



F(n)=2^k *F(n/3^k) + sommatoria con i=1 fino a k di O(1)


non mi trovo con la parte in rosso (quella prima va bene). Provo a postare dei calcoli:

F(n) = 2[F(n/3)] + n

calcoliamo F(N/3):

F(n/3) = 2[F(n/9)] + n/3

quindi F(n) diventa

F(n) = 2{2[F(n/9)] + n/3]} + n

alias

F(n) = 4[F(n/9)] + (2/3)n + n

ora, calcolando ancora F(n/9) abbiamo:

F(n/9) = 2[F(n/27)] + n/9

per cui F(N) diventa

F(n) = 4{2[F(n/27)] + n/9} + (2/3)n + n

che, facendo i calcoli, è

F(n) = 8[F(n/27)] + (4/9)n + (2/3)n + n

praticamente hai dimenticato i termini con n...

se continuassimo avremmo in sostanza che quei termini con n sono:

... (16/81)n (8/27)n + (4/9)n + (2/3)n + n

quindi i coefficienti sono un rapporto tra potenze di 2 (sopra) e di 3 (sotto), con esponenti uguali (0, 1, 2, 3...)

mettiamoli in evidenza. Abbiamo

n(16/81 + 8/27 + 4/9 + 2/3 + 1)

cioè n per sommatoria per i che va da 0 a k di 2^i / 3^i

la generalizzazione - secondo questi calcoli - è

F(N) = 2^k [F(n/3^k)] (e ci siamo) + n*"sommatoria i=0,...,k-1 di 2^i / 3^i"

a questo punto non ho continuato ma ricordando che

http://upload.wikimedia.org/math/9/7/6/976ad563054115e91ab2e7c1c61ea078.png

forse dovresti riuscire a venirne fuori...

NB: quella serie che ho ricavato va da 0 a k-1, infatti se k (ad esempio) è 2, tu hai

F(n) = 4[F(n/9)] + (2/3)n + n, e cioè

F(n) = 2^k[F(n/3^k)] + n(2/3)^(k-1) + n(2/3)^(k-2)

dove quindi k-1 vale 1 ( e infatti hai 2/3 elevato a 1 ) e k-2 vale 0 ( e infatti 2/3 elevato a 0 fa 1, e cioè il coefficiente dell'ultima n )

AtoXx
04-02-2009, 13:52
Originariamente inviato da LeleFT
La sezione può andare anche bene... ma era più difficile scrivere direttamente il testo dell'esercizio o scannerizzare, salvare e uploadare un'immagine, non permettendo, quindi, ad altri di risalire al tuo stesso problema tramite la ricerca e rendendo più difficoltosa la lettura dello stesso?

:dhò:

Ciao. :ciauz:

scusa leggo ora....+ tardi trascrivo la funzione....cmq non l'ho scritta a mano perchè mi sembra difficile che si vada a cercare proprio la complessità di questa funzione quindi mi sembrava una scelta migliore scrivere nel titolo complessità computazionale funzione,dato che la gente credo cercherebbe così.

AtoXx
04-02-2009, 13:54
YuYevon intanto ti ringrazio per la pazienza, il fattore di cui parli,cioè n n/3 n/9 ecc, l'avevo scritto come serie dato che ha costo O(1). quindi sbaglio???

YuYevon
04-02-2009, 14:11
Originariamente inviato da AtoXx
YuYevon intanto ti ringrazio per la pazienza, il fattore di cui parli,cioè n n/3 n/9 ecc, l'avevo scritto come serie dato che ha costo O(1). quindi sbaglio???

Occhio che è n, (2/3)n, (4/9)n e non n, n/3, n/9...

Comunque, in che senso



l'avevo scritto come serie dato che ha costo O(1)


?

Va scritto come serie, ma non ha di certo costo O(1)... se fosse una somma di costanti (quindi senza la n) allora avrebbe senso dire che quella serie ha un costo O(1), ma in questo cado dipende da N...

devi risolvere quella serie con termine ennesimo (2/3)^i usando quella formula che ti ho postato, in pratica nel tuo caso avrai che quella sommatoria è

[ (2/3)^(log_base3 di n ) - 1 ] / [ (2/3) - 1 ]

ovviamente tutto moltiplicato per N che sta fuori la sommatoria...

Prova a finire i calcoli... se hai difficoltà posta pure (purtroppo ho un esame di mat II da prepararmi per domani
:zizi: non so se riesco a finire i calcoli )

Loading