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
e che centra con la programmazione? questo è un problema di algoritmi...
non sapevo dove postarlo...e questa mi è sembrata la sezione più adatta...Originariamente inviato da Stoicenko
e che centra con la programmazione? questo è un problema di algoritmi...
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?Originariamente inviato da AtoXx
non sapevo dove postarlo...e questa mi è sembrata la sezione più adatta...
Ciao.
"Perchè spendere anche solo 5 dollari per un S.O., quando posso averne uno gratis e spendere quei 5 dollari per 5 bottiglie di birra?" [Jon "maddog" Hall]
Fatti non foste a viver come bruti, ma per seguir virtute e canoscenza
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.
every day above ground is a good one
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: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.
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
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
non mi trovo con la parte in rosso (quella prima va bene). Provo a postare dei calcoli:F(n)=2^k *F(n/3^k) + sommatoria con i=1 fino a k di O(1)
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
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 )
every day above ground is a good one
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ì.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?
Ciao.
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...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???
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
non so se riesco a finire i calcoli )
every day above ground is a good one
Permessi di invio
Rispondi quotando
