Ricorrenza corretta in parte
[tex]T(n)=4T(n/2)+n\log(n)[/tex]
Si può fare con il teorema Master e come soluzione si trova [tex]T(n)=\theta(n^2)[/tex]
Provando a farla con l' albero ottengo dei costi ai vari livelli che sono:
[tex](2^i)n\log(\frac{n}{2^i})[/tex]
Il numero di foglie è [tex]n^2[/tex] e quindi sommando i vari costi si ottiene:
[tex]\sum_{i=0}^{\log_2(n)-1}(2)^in\log_2(\frac{n}{2^i})+\theta(n^2)[/tex]
[tex]\sum_{i=0}^{\log_2(n)-1}(2)^in\log_2(n)-\sum_{i=0}^{\log_2(n)-1}(2)^in\log_2(2^i)+..[/tex]
La prima serie è:
[tex]n\log_2(n)\sum_{i=0}^{\log_2(n)-1}(2)^i[/tex]
Ottenendo [tex]n^2\log(n)-n\log(n)[/tex]
L' altra diventa [tex]\sum_{i=0}^{\log_2(n)-1}2^ii[/tex]
Qui come faccio? L' unica cosa che devo calcolare è:
[tex]\sum_{i=0}^{\log_2(n)-1}i[/tex]
Non so come vederla visto che arriva a log, se fosse stato n sarebbe stata la somma dei primi n naturali...
Si può fare con il teorema Master e come soluzione si trova [tex]T(n)=\theta(n^2)[/tex]
Provando a farla con l' albero ottengo dei costi ai vari livelli che sono:
[tex](2^i)n\log(\frac{n}{2^i})[/tex]
Il numero di foglie è [tex]n^2[/tex] e quindi sommando i vari costi si ottiene:
[tex]\sum_{i=0}^{\log_2(n)-1}(2)^in\log_2(\frac{n}{2^i})+\theta(n^2)[/tex]
[tex]\sum_{i=0}^{\log_2(n)-1}(2)^in\log_2(n)-\sum_{i=0}^{\log_2(n)-1}(2)^in\log_2(2^i)+..[/tex]
La prima serie è:
[tex]n\log_2(n)\sum_{i=0}^{\log_2(n)-1}(2)^i[/tex]
Ottenendo [tex]n^2\log(n)-n\log(n)[/tex]
L' altra diventa [tex]\sum_{i=0}^{\log_2(n)-1}2^ii[/tex]
Qui come faccio? L' unica cosa che devo calcolare è:
[tex]\sum_{i=0}^{\log_2(n)-1}i[/tex]
Non so come vederla visto che arriva a log, se fosse stato n sarebbe stata la somma dei primi n naturali...
Risposte
forse intendi: $4T(n/2) + nlog(n)$?
Si scusami, ho corretto, non so perchè è successo due volte che scrivo meno al posto di fratto....
Manca l' ultima serie, come trattarla?
"Darèios89":
[tex](2^i)n\log(\frac{n}{2^i})[/tex]
Il numero di foglie è [tex]n^2[/tex] e quindi sommando i vari costi si ottiene:
[tex]\sum_{i=0}^{\log_2(n)-1}(2)^in\log_2(\frac{n}{2^i})+\theta(n^2)[/tex]
ok mi sembra corretto, non ho valutato l'equazione (mi fido
)$\sum_{i=0}^{\log_2(n)-1}(2)^i\n\log_2(\frac{n}{2^i}) = n\sum_{k=1}^{\log_2(n)}(2)^k(\log_2(n) - k)$
$n\sum_{k=1}^{\log_2(n)}2^kk$ vedi = $... = 2n(2^{log_{2}(n)}(log_{2}(n) - 1) + 1) = 2n(n(log_{2}(n)-1)+1) = 2n(nlog_{2}(n) - n +1) = 2n^2log_{2}(n) - 2n^2 + 2n $
$2n^2log_{2}(n) - 2n^2 + 2n + O(n^2) in O(n^2log_{2}(n))$
se non ho sbagliato qualcosa questo è tutto
EDIT:
come detto in un altro post, non ero sicuro di questa uguaglianza. Perciò:
$sum x^i(n-i) != sum x^ii$
l'unica strada è calcolare l'intera sommatoria.
Mh....la soluzione dovrebbe essere [tex]\theta(n^2)[/tex].
Io ho la soluzione di questa ricorrenza ma non l' ho capita. Se mi dai la mail via pm, ti invio un pdf dove non sono riuscito a capire l' ultimo pezzo. Sempre se hai tempo
Io ho la soluzione di questa ricorrenza ma non l' ho capita. Se mi dai la mail via pm, ti invio un pdf dove non sono riuscito a capire l' ultimo pezzo. Sempre se hai tempo
come dissi più vollte l'albero riporta limitazioni superiori, che siano strette o meno bisogna sempre dimostrarlo, perchè sono ipotesi.
Poi ad occhio non capisco come possa essere $n^2$... ci sarà qualche passaggio sballato, ricontrollerò.
Poi ad occhio non capisco come possa essere $n^2$... ci sarà qualche passaggio sballato, ricontrollerò.
Si scrivo qui la formula, la limitazione [tex]\theta(n^2)[/tex] deriva da alcune semplificazioni che si hanno con quelle serie alla fine dei conti, se invece intendi quella che metto all' inizio della ricorrenza è perchè ho calcolato il costo delle foglie.
L' albero ha altezza [tex]\log_2(n)[/tex] quindi i nodi ad altezza h sarebbero [tex]4^{\log(n)}[/tex] da cui [tex]\theta(n^2)[/tex] se non erro.
La prima delle serie l' ho svolta nel primo post è risulta [tex]n^2\log(n)-n\log(n)[/tex] l' altra è:
[tex]\sum_{i=0}^{\log(n)-1}2^i*n\log_2(2^ì)[/tex]
E cioè:
[tex]n\sum_{i=0}^{\log(n)-1}2^i*i[/tex]
Poi nel pdf trovo scritto:
[tex]n(2^{\log(n)}\log(n)-2*2^{\log(n)}+2)[/tex]
Non capisco come arrivare qui....
E' la stessa che effettivamente è spuntata nel precedente post....lo sto ristudiando.
Mi sa che il mio problema sono le derivate, intanto nel tuo post mi sono dimenticato di una cosa:
ricorrenze-e-domande-t80600.html
Fai questa derivata: [tex]\frac{2^{n+1}-1}{2-1}[/tex] a me risulta [tex]2^{n+1}[/tex] non capisco perchè risulta [tex]2^n(n-1)+1[/tex].
Provando a fare quella di questo post.....non sono riuscito a farla bene: diventerebbe
[tex]2n\sum 2^{i-1}i[/tex]
Derivare
[tex]\frac{2^{\log(n)}-1}{2-1}[/tex]
E' la derivata di un quoziente, e al numeratore ho una funzione composta, quindi alla fine mi ritrovo [tex]\frac{2^{\log(n)}}{n}[/tex]
Però andando a sostituire non ottengo lo stesso prodotto...[tex]n(2^{\log(n)}\log(n)-2*2^{\log(n)}+2)[/tex]
L' albero ha altezza [tex]\log_2(n)[/tex] quindi i nodi ad altezza h sarebbero [tex]4^{\log(n)}[/tex] da cui [tex]\theta(n^2)[/tex] se non erro.
La prima delle serie l' ho svolta nel primo post è risulta [tex]n^2\log(n)-n\log(n)[/tex] l' altra è:
[tex]\sum_{i=0}^{\log(n)-1}2^i*n\log_2(2^ì)[/tex]
E cioè:
[tex]n\sum_{i=0}^{\log(n)-1}2^i*i[/tex]
Poi nel pdf trovo scritto:
[tex]n(2^{\log(n)}\log(n)-2*2^{\log(n)}+2)[/tex]
Non capisco come arrivare qui....
E' la stessa che effettivamente è spuntata nel precedente post....lo sto ristudiando.
Mi sa che il mio problema sono le derivate, intanto nel tuo post mi sono dimenticato di una cosa:
ricorrenze-e-domande-t80600.html
Fai questa derivata: [tex]\frac{2^{n+1}-1}{2-1}[/tex] a me risulta [tex]2^{n+1}[/tex] non capisco perchè risulta [tex]2^n(n-1)+1[/tex].
Provando a fare quella di questo post.....non sono riuscito a farla bene: diventerebbe
[tex]2n\sum 2^{i-1}i[/tex]
Derivare
[tex]\frac{2^{\log(n)}-1}{2-1}[/tex]
E' la derivata di un quoziente, e al numeratore ho una funzione composta, quindi alla fine mi ritrovo [tex]\frac{2^{\log(n)}}{n}[/tex]
Però andando a sostituire non ottengo lo stesso prodotto...[tex]n(2^{\log(n)}\log(n)-2*2^{\log(n)}+2)[/tex]
ok. Cercherò di esporti con le sotto-operazioni, penso non ti siano chiare quelle.
La semplificazione che ho fatto, proprio non ti garba
mettiamo tutto per esteso, prendendo per buoni i tuoi conti sull'albero e le tue sommatorie (senza la mia semplificazione).
A livello $i$ si avrà che: $2^i\nlog_{2}(n/2^i)$
semplifichiamoci la vita con le proprietà dei logaritmi:
\[2^in\log_{2}(\frac{n}{2^i}) = 2^in(log_{2}(n) - log_{2}(2^i)) = 2^in(log_{2}(n) - i\log_{2}(2)) =\]
(*) \[= 2^in(log_{2}(n) - i) = 2^in\log_{2}(n) - 2^in*i\]
Ora calcoliamo i nodi interni, con le semplificazioni sopra:
\[\sum_{i=0}^{log_{2}(n)-1}2^in\log_{2}(n) - 2^in*i = \sum_{i=0}^{log_{2}(n)-1}2^in\log_{2}(n) - \sum_{i=0}^{log_{2}(n)-1}2^in*i\]
suddividiamolo in:
\[n\log_{2}(n)\sum_{i=0}^{log_{2}(n)-1}2^i = \frac{2^{log_{2}(n)-1+1}-1}{2-1} = n^2log_{2}(n) - nlog_{2}(n) \]
e (qua si c'è un piccolo errore che non avevo notato prima, ma non cambia molto vedi l'indice della sommatoria)
\[-n*\sum_{i=0}^{log_{2}(n)-1}2^i*i = -2n\sum_{i=1}^{log_{2}(n)-1}2^{i-1}*i = -2n\sum_{i=1}^{log_{2}(n)-1}2^{i-1}*i\]
se noti:
\[D(\sum_{i=0}^{log_{2}(n)-1}2^{i}) = \sum_{i=1}^{log_{2}(n)-1}2^{i-1}*i\]
equivalentemente:
\[D(\frac{2^{log_{2}(n)-1+1}-1}{2-1}) = ... = 2^{log_{2}(n)-1}((log_{2}(n)-1)-1) + 1 = \frac{n}2log_{2}(n) - n + 1 \]
perciò per sostituzione:
\[-2n\sum_{i=1}^{log_{2}(n)-1}2^{i-1}*i = -2n(\frac{n}2log_{2}(n) - n + 1) = -n^2log_{2}(n) + 2n^2 - 2n\]
sommando: \(n^2log_{2}(n) - nlog_{2}(n) - n^2log_{2}(n) + 2n^2 - 2n = - nlog_{2}(n) + 2n^2 - 2n \in O(n^2)\).
Ora avendo notato l'indice, mi torna un altro risultato. Provo a chiedere in Analisi, chissà cosa sbaglio. Mi dispice un po' a far le cose di fretta si commetton errori
Ho visto che hai modificato il post:
qua non devi derivare il valore finito che trovi, ma devi sostituire al valore generale della derivata della sommatoria generale, che trovi qui: http://it.wikipedia.org/wiki/Serie_geometrica (questa cosa te la ho già linkata, perchè non guardi ciò che ti si consiglia per comprendere i passaggi??)
Se hai dubbi chiedi pure
La semplificazione che ho fatto, proprio non ti garba
mettiamo tutto per esteso, prendendo per buoni i tuoi conti sull'albero e le tue sommatorie (senza la mia semplificazione).
A livello $i$ si avrà che: $2^i\nlog_{2}(n/2^i)$
semplifichiamoci la vita con le proprietà dei logaritmi:
\[2^in\log_{2}(\frac{n}{2^i}) = 2^in(log_{2}(n) - log_{2}(2^i)) = 2^in(log_{2}(n) - i\log_{2}(2)) =\]
(*) \[= 2^in(log_{2}(n) - i) = 2^in\log_{2}(n) - 2^in*i\]
Ora calcoliamo i nodi interni, con le semplificazioni sopra:
\[\sum_{i=0}^{log_{2}(n)-1}2^in\log_{2}(n) - 2^in*i = \sum_{i=0}^{log_{2}(n)-1}2^in\log_{2}(n) - \sum_{i=0}^{log_{2}(n)-1}2^in*i\]
suddividiamolo in:
\[n\log_{2}(n)\sum_{i=0}^{log_{2}(n)-1}2^i = \frac{2^{log_{2}(n)-1+1}-1}{2-1} = n^2log_{2}(n) - nlog_{2}(n) \]
e (qua si c'è un piccolo errore che non avevo notato prima, ma non cambia molto vedi l'indice della sommatoria)
\[-n*\sum_{i=0}^{log_{2}(n)-1}2^i*i = -2n\sum_{i=1}^{log_{2}(n)-1}2^{i-1}*i = -2n\sum_{i=1}^{log_{2}(n)-1}2^{i-1}*i\]
se noti:
\[D(\sum_{i=0}^{log_{2}(n)-1}2^{i}) = \sum_{i=1}^{log_{2}(n)-1}2^{i-1}*i\]
equivalentemente:
\[D(\frac{2^{log_{2}(n)-1+1}-1}{2-1}) = ... = 2^{log_{2}(n)-1}((log_{2}(n)-1)-1) + 1 = \frac{n}2log_{2}(n) - n + 1 \]
perciò per sostituzione:
\[-2n\sum_{i=1}^{log_{2}(n)-1}2^{i-1}*i = -2n(\frac{n}2log_{2}(n) - n + 1) = -n^2log_{2}(n) + 2n^2 - 2n\]
sommando: \(n^2log_{2}(n) - nlog_{2}(n) - n^2log_{2}(n) + 2n^2 - 2n = - nlog_{2}(n) + 2n^2 - 2n \in O(n^2)\).
Ora avendo notato l'indice, mi torna un altro risultato. Provo a chiedere in Analisi, chissà cosa sbaglio. Mi dispice un po' a far le cose di fretta si commetton errori
Ho visto che hai modificato il post:
qua non devi derivare il valore finito che trovi, ma devi sostituire al valore generale della derivata della sommatoria generale, che trovi qui: http://it.wikipedia.org/wiki/Serie_geometrica (questa cosa te la ho già linkata, perchè non guardi ciò che ti si consiglia per comprendere i passaggi??)
Se hai dubbi chiedi pure
Si ci sono quasi, ho capito cosa intendi adesso, il mio problema allora, purtroppo, è non sapere calcolare la derivata 
Poi sbagliavo perchè io eliminavo direttamente quei -1+1, al posto di derivare l' intera espressione.
Allora io guardando da wikipedia vedo che tratta la ragione della serie come una potenza, quindi devo considerare la derivata di una potenza che è [tex]x^a=..ax^{a-1}[/tex]. Avendo [tex]2^{\log(n)}[/tex] devo trattarla come derivata di una funzione composta?
A me la derivata risulterebbe [tex]2^{\log_2(n)-1}(\log_2(n)-1+1)[/tex]
Non riesco a trovare quei [tex]...-1)-1)+1[/tex].
"ham_burst":
equivalentemente:
\[D(\frac{2^{log_{2}(n)-1+1}-1}{2-1}) = ... = 2^{log_{2}(n)-1}((log_{2}(n)-1)-1) + 1 = \frac{n}2log_{2}(n) - n + 1 \]
Poi sbagliavo perchè io eliminavo direttamente quei -1+1, al posto di derivare l' intera espressione.
Allora io guardando da wikipedia vedo che tratta la ragione della serie come una potenza, quindi devo considerare la derivata di una potenza che è [tex]x^a=..ax^{a-1}[/tex]. Avendo [tex]2^{\log(n)}[/tex] devo trattarla come derivata di una funzione composta?
A me la derivata risulterebbe [tex]2^{\log_2(n)-1}(\log_2(n)-1+1)[/tex]
Non riesco a trovare quei [tex]...-1)-1)+1[/tex].
non serve calcolarla ogni volta la derivata, è calcolata UNA volta per il caso generale $(x^(n+1) - 1)/(x-1)$ poi si va di sostituzione, trovi il tutto su wiki (non ho voglia di ricopiarlo).
guarda che c'è una priorità di parentesi, nel caso:
$sum_{i=1}^n 2^(i-1)i = [2^n(n-1)]+1$ (*)
secondo te cosa è uguale $2^(log_{2}(n))$ io direi $n^(log_{2}(2))$
Poi prova a sostituire $n$ di (*) $log_{2}(n)-1$ vedrai comparire -1)-1)+1 magicamente
Una seconda cosa, la "semplificazione" che dissi di non sapere se fosse corretta, confermo che non è corretta, cioè:
$sum x^i(n-i) != sum x^ii$ mi dispiace, bisogna calcolare tutto come abbiamo fatto, non c'è via di scampo
Poi sbagliavo perchè io eliminavo direttamente quei -1+1, al posto di derivare l' intera espressione.
guarda che c'è una priorità di parentesi, nel caso:
$sum_{i=1}^n 2^(i-1)i = [2^n(n-1)]+1$ (*)
secondo te cosa è uguale $2^(log_{2}(n))$ io direi $n^(log_{2}(2))$
Poi prova a sostituire $n$ di (*) $log_{2}(n)-1$ vedrai comparire -1)-1)+1 magicamente
Una seconda cosa, la "semplificazione" che dissi di non sapere se fosse corretta, confermo che non è corretta, cioè:
$sum x^i(n-i) != sum x^ii$ mi dispiace, bisogna calcolare tutto come abbiamo fatto, non c'è via di scampo
Non so, ormai sono sicuro che sei troppo irritato, ma non ci sono, se io devo sostituire all' intera espressione di derivata da wikipedia:
[tex]\frac{(n+1)x^n(x-1)-x^{n+1}+1}{(x-1)^2}[/tex]
Io ottengo:
[tex][\log_2(n)-1)+1](2^{\log_2(n)-1})-2^{[\log_2(n)-1)+1]}+1[/tex]
E non riesco ad arrivare alla forma corretta...è che sono cocciuto e queste cose forse....non riescono bene su forum quando uno come me...è proprio a terra..
Ora ad esempio guardando il tuo suggerimento su quelle proprietà dei logaritmi non capisco da dove derivata quella derivata [tex]2^n(n-1)+1[/tex] non riesco ad ottenere nemmeno quella....temo che non riuscirò mai a capirla...immagino che giustamente hai perso la voglia di perder tempo con me....
[tex]\frac{(n+1)x^n(x-1)-x^{n+1}+1}{(x-1)^2}[/tex]
Io ottengo:
[tex][\log_2(n)-1)+1](2^{\log_2(n)-1})-2^{[\log_2(n)-1)+1]}+1[/tex]
E non riesco ad arrivare alla forma corretta...è che sono cocciuto e queste cose forse....non riescono bene su forum quando uno come me...è proprio a terra..
Ora ad esempio guardando il tuo suggerimento su quelle proprietà dei logaritmi non capisco da dove derivata quella derivata [tex]2^n(n-1)+1[/tex] non riesco ad ottenere nemmeno quella....temo che non riuscirò mai a capirla...immagino che giustamente hai perso la voglia di perder tempo con me....
"Darèios89":
Non so, ormai sono sicuro che sei troppo irritato,
no problem
ma non ci sono, se io devo sostituire all' intera espressione di derivata da wikipedia:
[tex]\frac{(n+1)x^n(x-1)-x^{n+1}+1}{(x-1)^2}[/tex]
Io ottengo:
[tex][\log_2(n)-1)+1](2^{\log_2(n)-1})-2^{[\log_2(n)-1)+1]}+1[/tex]
oooh finalmente, sei arrivato ad una forma corretta, ed hai capito che bisogna derivare la forma generale (forse chissà si può usare anche la forma speicifica con $x=2$ ma, visto che l'indice della sommatoria è $log_{2}(n)-1$, consiglio di non complcarsi la vita)
ora è solo matematica spicciola, te la suddivido così è più chiaro:
$[(\log_2(n)-1)+1] = \log_2(n)$
$(2^{\log_2(n)-1}) = (n^(\log_2(2)))/2$ proprietà delle potenze (precorsi)
$-2^{(\log_2(n)-1)+1} = -n$
$+1 = +1$
$\log_2(n)*n/2 -n +1$ ti ricorda qualcosa? poi basta moltiplicare per $-2n$ visto che è la seconda sommatoria.
questa forma: $2^n(n-1) + 1$ è solo il raggruppamento con indice $n$ invece che $log_{2}(n)-1$, è equivalente a quella sopra, solo che i conti sono molto meno (ovviamente funziona solo con $x=2$).
Eureka.
Eh si.....si. Io mi stavo scervellando a fare comparire quel -1)-1)+1 o com' era, certo se avessi usato direttamente le proprietà avrei trovato la soluzione.
Benissimo, ho continuato a vedere il resto e ovviamente quadra tutto, almeno le sottrazioni le so fare
.
ham, come sempre, il migliore...
. Scusa negli altri post non avevo capito questo discorso, cioè di dovere tenere presente la derivata principale e sostituire i valori, io sbagliavo perchè essendoci al denominatore [tex]2-1[/tex] lo consideravo costante nella derivata del quoziente e non poteva risultare mai, ora ci siamo, devo rifarlo e fare qualche altro esercizio dove devo riflettere di più sui calcoli.
Grazie, non smetterò mai di ringraziarti, dopodomani ho l' esame.....ancora non penso di farcela, a meno che non spuntino ricorrenze così...particolari (per me) e domande sul programma strambe, comunque.....grazie
Eh si.....si. Io mi stavo scervellando a fare comparire quel -1)-1)+1 o com' era, certo se avessi usato direttamente le proprietà avrei trovato la soluzione.
Benissimo, ho continuato a vedere il resto e ovviamente quadra tutto, almeno le sottrazioni le so fare
.ham, come sempre, il migliore...
. Scusa negli altri post non avevo capito questo discorso, cioè di dovere tenere presente la derivata principale e sostituire i valori, io sbagliavo perchè essendoci al denominatore [tex]2-1[/tex] lo consideravo costante nella derivata del quoziente e non poteva risultare mai, ora ci siamo, devo rifarlo e fare qualche altro esercizio dove devo riflettere di più sui calcoli.Grazie, non smetterò mai di ringraziarti, dopodomani ho l' esame.....ancora non penso di farcela, a meno che non spuntino ricorrenze così...particolari (per me) e domande sul programma strambe, comunque.....grazie
great. di nulla
Mi ci son messo d'impegno pure io a render le cose complicate (forse ci son errori sugli indici della sommatoria, ma che sulla complessità ricadono nella costante $c$), con una proprietà che non avevo verificato ho fatto un po' di casino.
Comunque, in bocca al lupo per l'esame
PS: Se vuoi un altro esercizio c'è da correggere questa, anche se le parti che ho scritto le ricontrollerò per i "posteri", ti consiglio di ricalcolare la sommatoria, visto che comunque rintroverai la stessa proprietà vista fino adesso (derivata).
Mi ci son messo d'impegno pure io a render le cose complicate (forse ci son errori sugli indici della sommatoria, ma che sulla complessità ricadono nella costante $c$), con una proprietà che non avevo verificato ho fatto un po' di casino.
Comunque, in bocca al lupo per l'esame
PS: Se vuoi un altro esercizio c'è da correggere questa, anche se le parti che ho scritto le ricontrollerò per i "posteri", ti consiglio di ricalcolare la sommatoria, visto che comunque rintroverai la stessa proprietà vista fino adesso (derivata).
Comunque, in bocca al lupo per l'esame
Crepi!!!!
Si certo l' altra ricorrenza si deve rifare con lo stesso metodo, oggi provo a rifarla
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo