Altra equazione di ricorrenza...come si continua?
Stavo facendo questa ricorrenza:
[tex]T(n)=2T(n/2)+n/\log(n)[/tex]
Mi blocco.....ho sostituito [tex]n=2^m[/tex]
[tex]T(2^m)=2T(2^m/2)+2^m/\log(2^m)[/tex]
Ho pensato di porre [tex]S(m)=T(2^m)[/tex]
[tex]S(m)=2S(m/2)+2^m/\log(2^m)[/tex]
Ma mi sa che non funziona, o sbaglio o conviene fare qualcos' altro....
Al massimo arrivo a:
[tex]S(m)=2S(m/2)+2^m/m[/tex]
Ma mi manca qualcosa....non so come continuare.
Ho dimenticato nelle equazioni come:
[tex]T(n)=T(n/2)+T(n/4)+T(n/8)+n[/tex]
L' albero lo costruisco così?
n
/ \ \
n/2 n/4 n/8
/ \
n/4 n/8 n/16 ..........................................................
Cioè devo passare di volta in volta ad ogni nodo n/2. e moltiplico tutto per n/2, poi un altro figlio lo ottengo moltiplicando per n/4 e così via?
In questo caso il costo ad ogni livello dovrebbe essere [tex]\frac{7}{8}^in[/tex]
E per ogni livello i il numero di nodi è [tex]3^i[/tex]. Se non sbaglio il costo diventa 1 quando [tex]3^i=1[/tex] dove i è l' altezza dell' albero, ma qui dove ho tre valori oltre al costo esterno come faccio a stabilire quanto vale l' altezza?
[tex]T(n)=2T(n/2)+n/\log(n)[/tex]
Mi blocco.....ho sostituito [tex]n=2^m[/tex]
[tex]T(2^m)=2T(2^m/2)+2^m/\log(2^m)[/tex]
Ho pensato di porre [tex]S(m)=T(2^m)[/tex]
[tex]S(m)=2S(m/2)+2^m/\log(2^m)[/tex]
Ma mi sa che non funziona, o sbaglio o conviene fare qualcos' altro....
Al massimo arrivo a:
[tex]S(m)=2S(m/2)+2^m/m[/tex]
Ma mi manca qualcosa....non so come continuare.
Ho dimenticato nelle equazioni come:
[tex]T(n)=T(n/2)+T(n/4)+T(n/8)+n[/tex]
L' albero lo costruisco così?
n
/ \ \
n/2 n/4 n/8
/ \
n/4 n/8 n/16 ..........................................................
Cioè devo passare di volta in volta ad ogni nodo n/2. e moltiplico tutto per n/2, poi un altro figlio lo ottengo moltiplicando per n/4 e così via?
In questo caso il costo ad ogni livello dovrebbe essere [tex]\frac{7}{8}^in[/tex]
E per ogni livello i il numero di nodi è [tex]3^i[/tex]. Se non sbaglio il costo diventa 1 quando [tex]3^i=1[/tex] dove i è l' altezza dell' albero, ma qui dove ho tre valori oltre al costo esterno come faccio a stabilire quanto vale l' altezza?
Risposte
ma tutto ciò non lo avevo già scritto in risposta proprio a delle tue domande?
prova ad utilizzare "cerca" sui tuoi messaggi...
prova ad utilizzare "cerca" sui tuoi messaggi...
@ Darèios89: non è la prima volta che apri una nuova discussione invece di continuare a discutere nella tua vecchia discussione. Facendo in questo modo rendi solo più difficile risponderti o di ripetersi inutilmente.
Mi scuso, andrò a ricercare la mia discussione, ormai vecchia.....ma la cercherò.
Per questa volta lascia pure stare.. Ma per il futuro cerca di non creare se possibile discussioni sullo stesso argomento.
Ok, grazie, se poteste darmi una dritta ve ne sarò grato.
"Darèios89":
Stavo facendo questa ricorrenza:
[tex]T(n)=2T(n/2)+n/\log(n)[/tex]
Mi blocco.....ho sostituito [tex]n=2^m[/tex]
[tex]T(2^m)=2T(2^m/2)+2^m/\log(2^m)[/tex]
Ho pensato di porre [tex]S(m)=T(2^m)[/tex]
[tex]S(m)=2S(m/2)+2^m/\log(2^m)[/tex]
Ma mi sa che non funziona, o sbaglio o conviene fare qualcos' altro....
Al massimo arrivo a:
[tex]S(m)=2S(m/2)+2^m/m[/tex]
Ma mi manca qualcosa....non so come continuare.
al momento non mi ricordo questo metodo delle sostituzioni di variabili, è da un po' che non lo utilizzo...
guarda qua se è di aiuto: bloccato-in-una-ricorrenza-t66520.html
Ho dimenticato nelle equazioni come:
[tex]T(n)=T(n/2)+T(n/4)+T(n/8)+n[/tex]
L' albero lo costruisco così?
n / \ \ n/2 n/4 n/8 / \ n/4 n/8 n/16 ..........................................................
Cioè devo passare di volta in volta ad ogni nodo n/2. e moltiplico tutto per n/2, poi un altro figlio lo ottengo moltiplicando per n/4 e così via?
In questo caso il costo ad ogni livello dovrebbe essere [tex]\frac{7}{8}^in[/tex]
E per ogni livello i il numero di nodi è [tex]3^i[/tex]. Se non sbaglio il costo diventa 1 quando [tex]3^i=1[/tex] dove i è l' altezza dell' albero, ma qui dove ho tre valori oltre al costo esterno come faccio a stabilire quanto vale l' altezza?
per queste ti consiglio di rivederti (come ti avevo consigliato) la risposta che ti diedi:
post466730.html#p466730
la particolarità è che hai 3 ricorrenze differenti e 3 valori di dimezzamento differenti. Se vuoi utilizzare l'albero ti devi mettere in condizioni più comode, o fai una media o fai un limite superiore, es:
[tex]T(n)=T(n/2)+T(n/4)+T(n/8)+n[/tex]
media: $T(n)=3T(n/4)+ n$
sup: $T(n)=3T(n/2)+n$
inf: $T(n)=3T(n/8)+n$
così è banale come le altre, e l'albero è più facile da creare.
Se vuoi una limitazione precisa vai di induzione (metodo per tentativi) o iterazione (metodo algebrico)
Ma in quel modo non è come avere tre ricorrenze? Cioè le risolvo separatamente e considerando che l' albero è unico faccio la sommatoria di quello che ottengo in tutte e 3?
Io avevo pensato, al posto di scomporle in 3 equazioni, rappresentando l' albero avrei i costi del tipo:
[tex]n[/tex]
[tex]\frac{7n}{8}[/tex]
.
.
.
[tex]{\frac{7}{8}}^in[/tex]
Quindi per conoscere l' altezza non basterebbe considerare che il sottoproblema di dimensione 1 si trova per n=1 cioè quando [tex]{\frac{7}{8}}^in=1[/tex]?
Solo che mi risulterebbe [tex]\log_\frac{7}{8}(\frac{1}{n})[/tex]
Io avevo pensato, al posto di scomporle in 3 equazioni, rappresentando l' albero avrei i costi del tipo:
[tex]n[/tex]
[tex]\frac{7n}{8}[/tex]
.
.
.
[tex]{\frac{7}{8}}^in[/tex]
Quindi per conoscere l' altezza non basterebbe considerare che il sottoproblema di dimensione 1 si trova per n=1 cioè quando [tex]{\frac{7}{8}}^in=1[/tex]?
Solo che mi risulterebbe [tex]\log_\frac{7}{8}(\frac{1}{n})[/tex]
leggi bene la frase che ho scritto, c'è una "o"... fa una media oppure un sup o inf.
Cioè con un'equazione di ricorrenza del genere, con ben 3 valori di ricorsione ti cerchi un valore e utilizzi quello, gli altri li arrotondi...per quello ti ho scritto tre equazioni differenti ne scegli una e gardi quella che si avvicina di più, sostituendo alla fine dei calcoli alla equazione originale con tre valori diversi...
non ho fatto conti... da dove esce $7n/8$, da una di quelle che ho scritto o hai calcolato dall'originale?
Cioè con un'equazione di ricorrenza del genere, con ben 3 valori di ricorsione ti cerchi un valore e utilizzi quello, gli altri li arrotondi...per quello ti ho scritto tre equazioni differenti ne scegli una e gardi quella che si avvicina di più, sostituendo alla fine dei calcoli alla equazione originale con tre valori diversi...
non ho fatto conti... da dove esce $7n/8$, da una di quelle che ho scritto o hai calcolato dall'originale?
\[ T(n) = T(n/2) + T(n/4) + T(n/8) + n = 2T(n/4) + 2T(n/8) + T(n/16) + n + n/2 = 4T(n/8) + 3T(n/16) + 2T(n/32) + n + n/2 + n/2 = .. \]
Se si riuscisse a stabilire con una qualche formula il coefficiente del termine con la più bassa potenza di 2 si potrebbero stabilire i termini della serie e quindi risolvere l'equazione di ricorrenza. Ma così a occhio non mi viene in mente molto se non un'altra equazione di ricorrezza. Ma forse non è neanche necessario.. Dopotutto ogni termine aggiunge sempre un n moltiplicato per una qualche costante e ci sono circa \(\log n\) termini nella somma. Per cui secondo me è semplicemente \(O(n \log n) \). Ma forse è sparata troppo grossa.
Se si riuscisse a stabilire con una qualche formula il coefficiente del termine con la più bassa potenza di 2 si potrebbero stabilire i termini della serie e quindi risolvere l'equazione di ricorrenza. Ma così a occhio non mi viene in mente molto se non un'altra equazione di ricorrezza. Ma forse non è neanche necessario.. Dopotutto ogni termine aggiunge sempre un n moltiplicato per una qualche costante e ci sono circa \(\log n\) termini nella somma. Per cui secondo me è semplicemente \(O(n \log n) \). Ma forse è sparata troppo grossa.
"apatriarca":
\[ T(n) = T(n/2) + T(n/4) + T(n/8) + n = 2T(n/4) + 2T(n/8) + T(n/16) + n + n/2 = 4T(n/8) + 3T(n/16) + 2T(n/32) + n + n/2 + n/2 = .. \]
Se si riuscisse a stabilire con una qualche formula il coefficiente del termine con la più bassa potenza di 2 si potrebbero stabilire i termini della serie e quindi risolvere l'equazione di ricorrenza. Ma così a occhio non mi viene in mente molto se non un'altra equazione di ricorrezza. Ma forse non è neanche necessario.. Dopotutto ogni termine aggiunge sempre un n moltiplicato per una qualche costante e ci sono circa \(\log n\) termini nella somma. Per cui secondo me è semplicemente \(O(n \log n) \). Ma forse è sparata troppo grossa.
come detto più volte, non serve calcolare algebricamente questo mostro
basta ipotizzare, o aprossimare una limitazione e poi dimostrare per induzione.
se si calcolano si scopre (ne basta anche una sola):
sup: \[\displaystyle{3T(\frac{n}2) + n\ :=\ \sum_{i=0}^{\log_{2}(n)-1} (\frac{3}2)^{i}n + O(n^{\log_{2}(3)})\ \in O(n^{\log_{2}(3)})}\]
media: \[\displaystyle{3T(\frac{n}4) + n\ :=\ \sum_{i=0}^{\log_{4}(n)-1} (\frac{3}4)^{i}n + O(n^{\log_{4}(3)})\ \in O(n)}\]
inf: \[\displaystyle{3T(\frac{n}8) + n\ :=\ \sum_{i=0}^{\log_{8}(n)-1} (\frac{3}8)^{i}n + O(n^{\log_{8}(3)})\ \in O(n)}\]
da queste tre limitazioni si può capire che l'equazione originale:
$T(n) = T(n/2) + T(n/4) + T(n/8) + n in O(n)$
che si dimostra per induzione (secondo me si può dimostrare essere $\theta(n)$)
@Daréio89: ti consiglio di rifarti tutti i calcoli e capire come trattere tutto questo
EDIT:
precisazione, mettendo in relazione le maggiorazioni/minorazioni fatte, la loro classe di complessità e l'equazione originale, si avrà:
\[\displaystyle{T(\frac{n}2) + T(\frac{n}4) + T(\frac{n}8) + n \in o(n^{\log_{2}(3)})}\]
\[\displaystyle{T(\frac{n}2) + T(\frac{n}4) + T(\frac{n}8) + n \in \omega(n)}\]
l'ipotesi da dimostrare è perciò $T(n) in Theta(n)$
Ma non sono convinto che si possa calcolare in questo modo una equazione di ricorrenza. Forse mi sbaglio.
"apatriarca":
Ma non sono convinto che si possa calcolare in questo modo una equazione di ricorrenza. Forse mi sbaglio.
Come no!?
Forse intendi che non è correto il calcolo algebrico o legato alla matematica (che in un vecchio post ho capito che sono equazioni differenziali) perchè è un'approssimazione. Ma qua si cerca una limitazione asintotica (superiore) non un valore preciso. Questo perchè:
\(3T(\frac{n}2) + n \geq T(\frac{n}2) + T(\frac{n}4) + T(\frac{n}8) + n \geq 3T(\frac{n}8) + n\)
E' un'ipotesi, poi biosgnerebbe sempre dimostrare per induzione che tale limitazione è corretta (metodo della sostituzione), soprattutto in questi casi di maggiorazioni/minorazioni.
Poi il valore preciso è calcolabile come hai fatto te, ed è quella la tecnica corretta (metodo dell'iterazione), cioè reiterazione dell'equazione fino a valori di $n=1$, ma alle volte è complicato (come in questo caso) perciò ci si accontenta con queste approssimazioni...
Il ragionamento di humburst è fantastico, e mi quadra, però ho ancora una perplessità, nello scomporre la ricorrenza, caso base, medio e superiore hai messo davanti alla T un 3, come mai? Semplicemente perchè al secondo livello ho 3 nodi e quindi nel caso inferiore medio e superiore metti davanti a T un 3?
Quindi devo procedere facendo questa media, non si può dedurre un' altezza unica per l' albero mettendo tutto insieme come avevo iniziato io? Io avevo pensato fosse [tex]h=\log_2(n)[/tex].
Comunque si è [tex]\theta(n)[/tex].
Quindi devo procedere facendo questa media, non si può dedurre un' altezza unica per l' albero mettendo tutto insieme come avevo iniziato io? Io avevo pensato fosse [tex]h=\log_2(n)[/tex].
Comunque si è [tex]\theta(n)[/tex].
@ham_burst: non avevo capito bene il procedimento che seguivi e quindi non sapevo neanche dire se fosse corretto o meno. Adesso mi è più chiaro.
"Darèios89":
Il ragionamento di humburst è fantastico, e mi quadra, però ho ancora una perplessità, nello scomporre la ricorrenza, caso base, medio e superiore hai messo davanti alla T un 3, come mai? Semplicemente perchè al secondo livello ho 3 nodi e quindi nel caso inferiore medio e superiore metti davanti a T un 3?
Quindi devo procedere facendo questa media, non si può dedurre un' altezza unica per l' albero mettendo tutto insieme come avevo iniziato io? Io avevo pensato fosse [tex]h=\log_2(n)[/tex].
Comunque si è [tex]\theta(n)[/tex].
aspetta aspetta...fai un passo indietro, che hai capito sì e no il procedimento fatto (se leggevi il post che ti ho consigliato forse evitati la fuorviatura
).Abbiamo una equazione di ricorrenza: \[\displaystyle{T(n) = T(\frac{n}2)+T(\frac{n}4)+T(\frac{n}8)+n}\] che ha tre diversi fattori di ricorsione.
Un metodo per trovare una limitazione più precisa possibile è utilizzare l'apatriarca's rule (
), cioè il metodo algebrico, ma dato che risulta "complicato" risolverla si preferisce metodo più abbordabili.Il metodo dell'albero permette di approssimare una limitazione superiore sull'equazione e rappresentare il tutto graficamente.
In questo caso l'albero non sarà completo (quasi completo), avrà cammini radice-foglia di lunghezza diverse rispetto al valore di ricorsione.
$T(n/2)$ produce cammini di altezza massima $h_1=log_2(n)$
$T(n/4)$ produce cammini di altezza massima $h_2=log_4(n)$
$T(n/8)$ produce cammini di altezza massima $h_3=log_8(n)$
con questi valori "di solito" si scegle il cammino più lungo come base per la limitazione superiore (stretta) ed una maggiorazione sull'equazione, cioè (il sup di prima):
\[\displaystyle{T(\frac{n}2)+T(\frac{n}4)+T(\frac{n}8)+n \leq T(\frac{n}2) + T(\frac{n}2) + T(\frac{n}2) + n = 3T(\frac{n}2) + n}\]
poi se si vuole si può calcolare un limite inferiore (stretto) (che è un limite superiore rispetto l'equazione derivata), minorando l'equazione con il cammino più corto, così da vedere il gup della classe di complessità, cioè (l'inf di prima):
\[\displaystyle{T(\frac{n}2)+T(\frac{n}4)+T(\frac{n}8)+n \geq T(\frac{n}8) + T(\frac{n}8) + T(\frac{n}8) + n = 3T(\frac{n}8) + n}\]
in questo e solo in questo caso, si ha un terzo valore che è in mezzo ai due limiti, se si calcola pure quell'equazione si può avere una visuale maggiore, non è una cosa standard come pensi te...
Facendo queste maggiorazioni/minorazioni si aggiungono o tolgono nodi dall'albero (cioè valori costanti dall'equazione) per questo sono limitazioni strette.
Perciò, avendo tutti questi dati si possono fare limitazioni più strette possibili senza calcolare veramente l'equazione originale. Il calcolo dell'equazioni derivati può essere fatto anche con il Master Theorem (entrando nella formulazione $aT(n/b) + f(n)$) semplificando ancora di più i conti. Tutte queste limitazioni sono IPOTESI da dimostrare (v. grassetto) per induzione.
Se hai dubbi chiedi pure
@apatriarca:
non hai studiato ad un qualche corso di algoritmica queste tecniche, oltre il metodo algebrico/matematico?
Io non ho mai seguito un vero e proprio corso di algoritmica. È più che altro studio personale. Ma anche l'avessi seguito quando stavo ad ingegneria, sono parecchi anni che seguo corsi solo matematici. Programmo attivamente per un progetto open-source e continuo a tenermi un po' in allenamento su questo genere di cose attraverso forum e altro, ma sono un matematico (un geometra)... Non analizzo algoritmi molto spesso.
Ma più che altro avevo letto male il tuo post e non avevo capito quello che stavi facendo. Avevo frainteso i tuoi obiettivi e il tuo metodo insomma.
Ma più che altro avevo letto male il tuo post e non avevo capito quello che stavi facendo. Avevo frainteso i tuoi obiettivi e il tuo metodo insomma.
Aaaaah! Credo di avere capito, quindi dalla ricorrenza considero che ci sono quelle 3 chiamate, e devo prendere sostanzialmente quella con il cammino più lungo, cioè quella che asintoticamente è più lenta delle altre per determinare una limitazione superiore (cioè significa ordine [tex]O[/tex]). In questi giorni mi cimento sulla dimostrazione per induzione, preparatevi al peggio ragazzi... 
"Darèios89":
Aaaaah! Credo di avere capito, quindi dalla ricorrenza considero che ci sono quelle 3 chiamate, e devo prendere sostanzialmente quella con il cammino più lungo, cioè quella che asintoticamente è più lenta delle altre per determinare una limitazione superiore (cioè significa ordine [tex]O[/tex]).
mmm c'è sempre qualcosa che manca nei tuoi discorsi. Non è proprio "prendo il cammino più lungo" ma "dipende" dall'equazione.
Ti posso dare una regola generale di prendere l'altezza più lunga (sempre parlando di "metodo dell'albero") o di massimo valore di ricorsione, ma dipende dalla situazione.
Comunque sì il metodo dell'albero crea solo limitazioni superiori, che a seconda dei casi può essere una limitazione anche inferiore per un'equazione maggiore.
Ad esempio se te prendessi solo la ricorsione $n/2$ e la maggiori con il resto, avresti una limitazione, ma non è la più stretta, che si trova studiando e guardando il resto dell'equazione, per questo "dipende".
Consiglio: rileggiti per bene tutta la discussione con il vecchio post linkato. C'è scritto tutto e oltre.
Se avrai ancora dubbi son lieto di chiarirteli
In questi giorni mi cimento sulla dimostrazione per induzione, preparatevi al peggio ragazzi...
yuppie yeh
"apatriarca":
ma sono un matematico (un geometra)... Non analizzo algoritmi molto spesso.
ah mi pareva di aver letto che tu avessi fatto alla triennale una qualche Ingegneria con un qualche indirizzo di informatica sperimentale, ma sempre di informatica, per questo pensavo avessi fatto algoritmica, anche perchè risolvi e utilizzi metodi di ragionamenento di Algoritmi senza problemi. Ma questo penso derivi dall'esperienza
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo