Bloccato in una ricorrenza
[tex]T(n)=\sqrt{n}T(\sqrt{n})+n[/tex]
Ho pensato di sostituire:
[tex]n=2^m[/tex]
[tex]T(2^m)=2^{\frac{m}{2}}T(2^{\frac{m}{2}})+2^m[/tex]
Ora dovrei togliermi prima di T quel [tex]2^{\frac{m}{2}}[/tex]
Potrei provare a dividere tutto proprio per questo fattore ma poi non riesco a sostituire altro...come procedereste?
Ho pensato di sostituire:
[tex]n=2^m[/tex]
[tex]T(2^m)=2^{\frac{m}{2}}T(2^{\frac{m}{2}})+2^m[/tex]
Ora dovrei togliermi prima di T quel [tex]2^{\frac{m}{2}}[/tex]
Potrei provare a dividere tutto proprio per questo fattore ma poi non riesco a sostituire altro...come procedereste?
Risposte
Ciao,
un'altra ricorrenza
guarda ho pensato solo venti secondi, e fatto anche due conti mentali, ma a me sembra banale. Gurderò meglio domani, ma se ho fatto bene è semplice. Dovrebbe forse esserci un problema di una costante, ma guarderò.
Comunque ti do solo un piccolo aiuto: cambia metodo, prova il metodo della sostituzione.
Ricordi qual'è, se no è questa:
https://www.matematicamente.it/forum/pos ... tml#466639
ipotizzi una complessità e dimostri per induzione. Ciau
un'altra ricorrenza
guarda ho pensato solo venti secondi, e fatto anche due conti mentali, ma a me sembra banale. Gurderò meglio domani, ma se ho fatto bene è semplice. Dovrebbe forse esserci un problema di una costante, ma guarderò.
Comunque ti do solo un piccolo aiuto: cambia metodo, prova il metodo della sostituzione.
Ricordi qual'è, se no è questa:
https://www.matematicamente.it/forum/pos ... tml#466639
ipotizzi una complessità e dimostri per induzione. Ciau
Allora, ieri avevo pensato di dimostrare questa equazione con complessità $O(n)$. Ma facendo i conti con carte e penna, non viene per via di una costante che fa non valere la disequazione.
Perciò un'altra strada è o ipotizzare n'altra complessità ad occhio $O(nlogn)$, o andare su quella che hai affrontato te, cioè sostituazioni di variabile.
In questo modo però ci si complica la vita, quel $2^(m/2)$ è in mezzo. Provando con il metodo dell'iterazione si può cercare di toglierlo, non è complicato. Basta ricordarsi che $sqrt(n)*sqrt(n) = n$ e $2^(m/2)*2^(m/2) = 2^m$
O al massimo usare un altro cambio di variabile.
Perciò un'altra strada è o ipotizzare n'altra complessità ad occhio $O(nlogn)$, o andare su quella che hai affrontato te, cioè sostituazioni di variabile.
In questo modo però ci si complica la vita, quel $2^(m/2)$ è in mezzo. Provando con il metodo dell'iterazione si può cercare di toglierlo, non è complicato. Basta ricordarsi che $sqrt(n)*sqrt(n) = n$ e $2^(m/2)*2^(m/2) = 2^m$
O al massimo usare un altro cambio di variabile.
Ho proseguito sulla strada della sostituzione, però ho una soluzione leggermente diversa.
La soluzione corretta è: [tex]T(n)=\theta(n\log(\log(n)))[/tex]
Continuando da dove ho lasciato allora divido tutto e:
[tex]\frac{T(2^m)}{2^\frac{m}{2}*2^\frac{m}{2}}=\frac{2^\frac{m}{2}T(2^\frac{m}{2})}{2^\frac{m}{2}*2^\frac{m}{2}}+1[/tex]
[tex]\frac{T(2^m)}{2^\frac{m}{2}*2^{\frac{m}{2}}}=S(m)[/tex]
[tex]S(m)=S(m/2)+1[/tex]
Dovrebbe essere il secondo caso del teorema Master e avrei: [tex]S(m)=\theta(\log(m))[/tex]
Quindi [tex]T(2^m)=2^mS(m)[/tex]
[tex]T(n)=\theta(n\log(\log(n)))[/tex]
La soluzione corretta è: [tex]T(n)=\theta(n\log(\log(n)))[/tex]
Continuando da dove ho lasciato allora divido tutto e:
[tex]\frac{T(2^m)}{2^\frac{m}{2}*2^\frac{m}{2}}=\frac{2^\frac{m}{2}T(2^\frac{m}{2})}{2^\frac{m}{2}*2^\frac{m}{2}}+1[/tex]
[tex]\frac{T(2^m)}{2^\frac{m}{2}*2^{\frac{m}{2}}}=S(m)[/tex]
[tex]S(m)=S(m/2)+1[/tex]
Dovrebbe essere il secondo caso del teorema Master e avrei: [tex]S(m)=\theta(\log(m))[/tex]
Quindi [tex]T(2^m)=2^mS(m)[/tex]
[tex]T(n)=\theta(n\log(\log(n)))[/tex]
come sei arrivato a $Theta(nloglogn)$ se quella è la soluzione dell'esercizio, allora si è corretta.
Non ero lontano da $O(n)$ mancava un fattore piccolo.
se provi ad usare l'induzione viene perfetta la dimostrazione, un $O(nloglogn)$ tondo.
però passando alla tua esecuzione dell'esercizo, fino al master è ok.
Sbagli nel tornare indietro nella sostituzione, devi ricordati che hai diviso per $2^m$....
Non ero lontano da $O(n)$ mancava un fattore piccolo.
se provi ad usare l'induzione viene perfetta la dimostrazione, un $O(nloglogn)$ tondo.
però passando alla tua esecuzione dell'esercizo, fino al master è ok.
Sbagli nel tornare indietro nella sostituzione, devi ricordati che hai diviso per $2^m$....
La soluzione in cui mi hai chiesto come ci sono arrivato è quella del libro 
QUel 1 che non ti spieghi è perchè il lavoro esterno sarebbe [tex]2^m[/tex]
Se ho diviso tutto quanto per lo stesso fattore avrei [tex]\frac{2^m}{2^\frac{m}{2}*2^\frac{m}{2}}[/tex]
Quindi non farebbe 1?
Poi avanti non so cosa sostituire evidentemente se S(m) non va bene.
QUel 1 che non ti spieghi è perchè il lavoro esterno sarebbe [tex]2^m[/tex]
Se ho diviso tutto quanto per lo stesso fattore avrei [tex]\frac{2^m}{2^\frac{m}{2}*2^\frac{m}{2}}[/tex]
Quindi non farebbe 1?
Poi avanti non so cosa sostituire evidentemente se S(m) non va bene.
ho capito solo dopo aver scritto il messaggio, cosa hai fatto.
ti ho scritto qualcosa sopra perchè lo ho editato mentre te scrivevi...
ti ho scritto qualcosa sopra perchè lo ho editato mentre te scrivevi...
Hai ragione ho sostituito male, risulta e come, grazie mille....sarei perduto senza di te
Una curiosità....ma se invece devo risolvere delle ricorrenze con l'albero, ogni volta mi confondo su quale è la base del logaritmo dell' altezza. Per dire se avessi, me la invento:
[tex]T(n)=2T(n/2)+3T(n/3)+1[/tex]
Come faccio a capire qual' è la base del logaritmo dell' altezza dell'albero?
Una curiosità....ma se invece devo risolvere delle ricorrenze con l'albero, ogni volta mi confondo su quale è la base del logaritmo dell' altezza. Per dire se avessi, me la invento:
[tex]T(n)=2T(n/2)+3T(n/3)+1[/tex]
Come faccio a capire qual' è la base del logaritmo dell' altezza dell'albero?
ah sei riuscito, perfetto 
Non preoccuparti non sei l'unico che sbaglia in quel punto in questo metodo, pure io tantissime volte ho sbagliato a tornare indietro, son dimenticanze, e poi se non si sceglie una variabile corretta ($2^m$ va sempre bene per sti esecizi) sono azzi
In generale, se hai un'equazione del tipo:
$aT(n/b) + n$
altezza massima $h = log_b(n)$
numero foglie totali T(1) all'altezza h: $a^(log_b(n))$
ma questo è la base della dimostrazione del Master Theorem....
In questa equazione $2T(n/2) + 3T(n/3) + 1$ non pui molto vedere le cose scritte sopra perchè fai ricorrenza su una costante,
ma cmq sei in un caso semplice che anche senza ricorrere all'albero lo risolvi.
Non preoccuparti non sei l'unico che sbaglia in quel punto in questo metodo, pure io tantissime volte ho sbagliato a tornare indietro, son dimenticanze, e poi se non si sceglie una variabile corretta ($2^m$ va sempre bene per sti esecizi) sono azzi
Come faccio a capire qual' è la base del logaritmo dell' altezza dell'albero?
In generale, se hai un'equazione del tipo:
$aT(n/b) + n$
altezza massima $h = log_b(n)$
numero foglie totali T(1) all'altezza h: $a^(log_b(n))$
ma questo è la base della dimostrazione del Master Theorem....
In questa equazione $2T(n/2) + 3T(n/3) + 1$ non pui molto vedere le cose scritte sopra perchè fai ricorrenza su una costante,
ma cmq sei in un caso semplice che anche senza ricorrere all'albero lo risolvi.
Ah ok perfetto, ma quindi se ci fosse più di una ricorrenza e avessi:
[tex]2T(\frac{n}{2})+3T(\frac{n}{3})+n[/tex]
o
[tex]2T(\frac{n}{2})+3T(\frac{n}{3})+n^2[/tex]
E' difficile determinare l'altezza dell' albero visto che ci sono due chiamate ricorsive?
[tex]2T(\frac{n}{2})+3T(\frac{n}{3})+n[/tex]
o
[tex]2T(\frac{n}{2})+3T(\frac{n}{3})+n^2[/tex]
E' difficile determinare l'altezza dell' albero visto che ci sono due chiamate ricorsive?
In questa ricorrenza sei in un caso "fortunato", se ti ricordi con la doppia ricorrenza devi fare un'analisi particolare come ti mostrai in un altro post,
devi maggiorare per ricondurti ad un'equazione più facile da maneggiare con l'albero o con il Master.
Ma l'albero in questi contesti puoi usarlo per vedere in quale parte dell'albero "pende" maggiormente l'equazione.
Cioè quale parte ha altezza maggiore (ricordati che non è completo con doppia equazione). In questo caso però non vale questa regola, ti faccio vedere:
alberto giustificato a sinistra (scusa non ho voglia di disegnare)
$n$
$2n/2 = n$ + $3n/3 = n$ $= 2n$
$2^i n/2^i = n$ + $3^i n/3^i = n$ $= 2n$
....
$T(1) = 2^(log_2(n)) = n$ + $T(1) = 3^(log_3(n)) = n$ $=2n$
puoi vedere semplicemente che anche se le altezze sono diverse, la complessità è identica, cioè $O(n)$. Ho evitato di scriverti ogni cosa, la sommatoria fino al livello $h-1$, con alla fine la somma delle foglie ecc, perchè la sommatori risulta una costante, e alla fine è una somma tra $2n + 2n = 4n in O(n)$
stesso discorso con $n^2$.
PS: mi sembra di ricordare che c'era una complicazione in queste equazioni apparentementi banali, ti dico domani però.
edit:
sistemato formule nuovo formato.
devi maggiorare per ricondurti ad un'equazione più facile da maneggiare con l'albero o con il Master.
Ma l'albero in questi contesti puoi usarlo per vedere in quale parte dell'albero "pende" maggiormente l'equazione.
Cioè quale parte ha altezza maggiore (ricordati che non è completo con doppia equazione). In questo caso però non vale questa regola, ti faccio vedere:
alberto giustificato a sinistra (scusa non ho voglia di disegnare)
$n$
$2n/2 = n$ + $3n/3 = n$ $= 2n$
$2^i n/2^i = n$ + $3^i n/3^i = n$ $= 2n$
....
$T(1) = 2^(log_2(n)) = n$ + $T(1) = 3^(log_3(n)) = n$ $=2n$
puoi vedere semplicemente che anche se le altezze sono diverse, la complessità è identica, cioè $O(n)$. Ho evitato di scriverti ogni cosa, la sommatoria fino al livello $h-1$, con alla fine la somma delle foglie ecc, perchè la sommatori risulta una costante, e alla fine è una somma tra $2n + 2n = 4n in O(n)$
stesso discorso con $n^2$.
PS: mi sembra di ricordare che c'era una complicazione in queste equazioni apparentementi banali, ti dico domani però.
edit:
sistemato formule nuovo formato.
Si la complicazione è che poi le devi dimostrare per induzione....XD
Grazie comunque, credo di aver capito adesso....
Grazie comunque, credo di aver capito adesso....
eeeh l'induzione è una palla sempre...ma bisogna farsi l'abitudine, l'informatico usa l'induzione dovunque (anche dimostrazione per assurdo)...
però come ti dicevo sopra, non ero sicuro della correttezza di ciò che ti avevo detto.
Perciò non vorrei farti capire cose sbagliate, l'albero è corretto, ma cercando una limitazione superiore puoi prendere l'altezza maggiore, cioè $log_2(n)$ e usare quella come limitazione.
Ho fatto un errore nel calcolo (imbarazzante), ma che voglio mostrarti così non sbagli te:
generalizzando per livello $i$
$(sum_{i=0}^{log_2(n)-1} 2^i*n/2^i) + (sum_{i=0}^{log_3(n)-1} 3^i*n/3^i) <= (n*sum_{i=1}^{log_2(n)} (2/2)^i) + (n*sum_{i=1}^{log_3(n)} (3/3)^i) = (n*sum_{i=1}^{log_2(n)} 1^i) + (n*sum_{i=1}^{log_3(n)} 1^i) = $
$= nlog_2(n) + nlog_3(n) <= nlog_2(n) + nlog_2(n) = 2nlog_2(n)$
sommando con le foglie:
$2n + 2nlog_2(n) in O(nlog_2(n))$
la dimostrazione con $O(n)$ non mi tornava ,per quello ho rifatto i conti. L'induzione serve proprio per capire se quello che si è fatto è corretto, in questo caso è servito
però come ti dicevo sopra, non ero sicuro della correttezza di ciò che ti avevo detto.
Perciò non vorrei farti capire cose sbagliate, l'albero è corretto, ma cercando una limitazione superiore puoi prendere l'altezza maggiore, cioè $log_2(n)$ e usare quella come limitazione.
Ho fatto un errore nel calcolo (imbarazzante), ma che voglio mostrarti così non sbagli te:
generalizzando per livello $i$
$(sum_{i=0}^{log_2(n)-1} 2^i*n/2^i) + (sum_{i=0}^{log_3(n)-1} 3^i*n/3^i) <= (n*sum_{i=1}^{log_2(n)} (2/2)^i) + (n*sum_{i=1}^{log_3(n)} (3/3)^i) = (n*sum_{i=1}^{log_2(n)} 1^i) + (n*sum_{i=1}^{log_3(n)} 1^i) = $
$= nlog_2(n) + nlog_3(n) <= nlog_2(n) + nlog_2(n) = 2nlog_2(n)$
sommando con le foglie:
$2n + 2nlog_2(n) in O(nlog_2(n))$
la dimostrazione con $O(n)$ non mi tornava ,per quello ho rifatto i conti. L'induzione serve proprio per capire se quello che si è fatto è corretto, in questo caso è servito
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo