Equazione di ricorrenza
Mi sembra strano il mio pensiero, è sbagliata questa soluzione?
L' equazione è:
[tex]T(n)=T(n-2)+2\log(n)[/tex]
[tex]T(n)=\sum_{i=2}^{n}2\log(i)\leq n\log(n)[/tex]
[tex]T(n)=\theta(n\log(n))[/tex]
L' equazione è:
[tex]T(n)=T(n-2)+2\log(n)[/tex]
[tex]T(n)=\sum_{i=2}^{n}2\log(i)\leq n\log(n)[/tex]
[tex]T(n)=\theta(n\log(n))[/tex]
Risposte
A me $\theta(n\log(n))$ sembra "troppo", a occhio direi si può ridurre a $\theta(n/2\log(n))$ ma non mi sembra così evidente...
ho fatto due conti veloci, la complessità quasi corretta pare essere quella di Darèios89 a meno di una costante.
Quella di rggb, la componente $n/2$ viene tolta a metà dimostrazione, se nn ho sbagliato i conti.
Per dimostrare tale complessità, il procedimento è "identico" a quello che ti mostrai tempo fà in questo post:
https://www.matematicamente.it/forum/pos ... tml#462209
per l'equazione $T(n) = T(n-1) + logn$
con questa trasformazione per la proprietà dei logaritmi: $T(n) = T(n-2) + log(n^2)$, il procedimento è simile, anche la dimostrazione per induzione finale (con qualche accorgimento).
Anche stavolta penso hai usato il Telescoping, ma vedendolo si arriva alla stessa conclusione, ma bisogna dimostralo non si può solo scriverlo.
Quella di rggb, la componente $n/2$ viene tolta a metà dimostrazione, se nn ho sbagliato i conti.
Per dimostrare tale complessità, il procedimento è "identico" a quello che ti mostrai tempo fà in questo post:
https://www.matematicamente.it/forum/pos ... tml#462209
per l'equazione $T(n) = T(n-1) + logn$
con questa trasformazione per la proprietà dei logaritmi: $T(n) = T(n-2) + log(n^2)$, il procedimento è simile, anche la dimostrazione per induzione finale (con qualche accorgimento).
Anche stavolta penso hai usato il Telescoping, ma vedendolo si arriva alla stessa conclusione, ma bisogna dimostralo non si può solo scriverlo.
Cioè dici che la soluzione sarebbe [tex]\theta(n\log(n))[/tex]
Però devo dimostrarlo o come avevi suggerito tu oppure per induzione?
Però devo dimostrarlo o come avevi suggerito tu oppure per induzione?
Ho fatto i conti con più calma, la complessità è $Theta(nlogn)$
Da come ho studiato analisi degli algoritmi, ci sono due fasi nello studio della complessità (ricorsiva o meno):
1. Cercare una limitazione asintotica con una qualche tecnica (se usi il metodo della sostituzione la limitazione la ipotizzi te).
2. Usare questa limitazione trovata per dimostrare per induzione che questa limitazione è corretta.
Perciò, te hai fatto la prima fase, hai trovato una limitazione con il metodo del Telescoping (si trova anche con il metodo dell'iterazione, sostituzione, albero, ecc...),
adesso per dire se questa limitazione è vera, basta usara l'induzione (limitazione inferiore e superiore per via di Theta) e il gioco è fatto.
Comunque anche fermarsi alla prima fase non è sbagliato, per questi esercizi basta fermasi li (ma se non hai capito perchè risulta esatta la complessità, fai tutto completamente),
ma in altri contesti meglio fare tutto alla perfezione (es: esame)
Da come ho studiato analisi degli algoritmi, ci sono due fasi nello studio della complessità (ricorsiva o meno):
1. Cercare una limitazione asintotica con una qualche tecnica (se usi il metodo della sostituzione la limitazione la ipotizzi te).
2. Usare questa limitazione trovata per dimostrare per induzione che questa limitazione è corretta.
Perciò, te hai fatto la prima fase, hai trovato una limitazione con il metodo del Telescoping (si trova anche con il metodo dell'iterazione, sostituzione, albero, ecc...),
adesso per dire se questa limitazione è vera, basta usara l'induzione (limitazione inferiore e superiore per via di Theta) e il gioco è fatto.
Comunque anche fermarsi alla prima fase non è sbagliato, per questi esercizi basta fermasi li (ma se non hai capito perchè risulta esatta la complessità, fai tutto completamente),
ma in altri contesti meglio fare tutto alla perfezione (es: esame)
L'induzione io la utilizzerei per equazioni più difficili. In casi come questi dove con una semplice sommatoria te la cavi non ce n'è bisogno. Sviluppi la serie e hai finito. De gustibus comunque.
In questo caso nella tua soluzione manca ovviamente la giustificazione della disuguaglianza che però in due passaggi (usando le proprietà dei logaritmi) la ottieni.
Piccolo appunto: se dimostri che $T(n)<=f(x)$ allora puoi solamente scrivere che $T(n) = O(f(x))$.
In questo caso nella tua soluzione manca ovviamente la giustificazione della disuguaglianza che però in due passaggi (usando le proprietà dei logaritmi) la ottieni.
Piccolo appunto: se dimostri che $T(n)<=f(x)$ allora puoi solamente scrivere che $T(n) = O(f(x))$.
@Deckard: il consiglio che hai scritto è quello che dico pure io, solo che la rendo più completa (complicata)
Infatti per dimostrare che $T(n) <= cf(n)$ devi usare l'induzione, o anche chiamato metodo della sostituzione o per tentativi. Dipende dalla strada che prendi,
ma l'induzione da una parte o dall'altra te la ritrovi ad affrontare
Infatti per dimostrare che $T(n) <= cf(n)$ devi usare l'induzione, o anche chiamato metodo della sostituzione o per tentativi. Dipende dalla strada che prendi,
ma l'induzione da una parte o dall'altra te la ritrovi ad affrontare
Emh...il problema è che proprio l' induzione non la capisco, ci sono tanti esercizi ma mi perdo, non ho ben capito cosa e come fare, mi confondo a sostituire, su quello che devo cercare, se l' ho trovato o se manca qualcosa. Non è che potreste farmi vedere voi in questo esempio il metodo di induzione così da capire?
P.S ma il metodo dell' induzione non permetteva di stabilire il limite superiore o inferiore?
Quindi se qui la soluzione è [tex]\theta[/tex] come faccio ad usarlo?
Se potessimo usare la notazione O-Grande io devo dimostrare che
[tex]T(n)\leq cn\log(n)[/tex]
P.S ma il metodo dell' induzione non permetteva di stabilire il limite superiore o inferiore?
Quindi se qui la soluzione è [tex]\theta[/tex] come faccio ad usarlo?
Se potessimo usare la notazione O-Grande io devo dimostrare che
[tex]T(n)\leq cn\log(n)[/tex]
Guarda, ti ho fatto incasinare senza motivo,
il mio modo di trovare la complessità deriva dal mio utilizzo dell'albero di ricorsione, che per me è un modo di astrazione (forse banale ma utile),
l'albero di ricorsione fornisce una stima della complessità, che bisogna dimostrare per induzione.
Se vuoi farla più facile:
- Metodo di Sostituzione/tentativi: ipotizzi una complessità, dimostri per induzione.
- Metodo dell'albero: stimi una complessità e dimostri per induzione.
Tutto il resto ti da una complessità che per i teoremi è corretta. Vedi dimostrazione del Master Theorem.
Te hai trovato una complessità, è corretta per via dei teoremi (dimostrati) che stanno sotto al metodo che utilizzi (Telescoping), perciò la dimostrazione è solo una cosa in più.
il mio modo di trovare la complessità deriva dal mio utilizzo dell'albero di ricorsione, che per me è un modo di astrazione (forse banale ma utile),
l'albero di ricorsione fornisce una stima della complessità, che bisogna dimostrare per induzione.
Se vuoi farla più facile:
- Metodo di Sostituzione/tentativi: ipotizzi una complessità, dimostri per induzione.
- Metodo dell'albero: stimi una complessità e dimostri per induzione.
Tutto il resto ti da una complessità che per i teoremi è corretta. Vedi dimostrazione del Master Theorem.
Te hai trovato una complessità, è corretta per via dei teoremi (dimostrati) che stanno sotto al metodo che utilizzi (Telescoping), perciò la dimostrazione è solo una cosa in più.
Bene...ti ringrazio. ^^
Un' ultima cosa...mentre ci sono.
Ho provato a fare quest' altra:
[tex]T(n)=2T(n/3)+2T(n/9)+n[/tex]
Ho provato ad usare l'albero di ricorsione, non so se è corretto ma ho ottenuto:
Ora le mie domande sono, ho sbagliato ad impostarlo?
Come faccio a capire per l'altezza h dell' albero qual' è la base del logaritmo e l'argomento?
Qui per come l'ho scritto io, sembrerebbe si possa dire [tex]T(n)=O(n\log(n))[/tex]
E dovrei dimostrarlo per induzione giusto?
Sempre ammesso che non sia sbagliato, e mentre ci sono ti chiedo:
In alcuni casi uso le sommatorie per determinare il costo del lavoro ad ogni livello, non è questo il caso ma a volte capita, e mi ritrovo a volte delle sommatorie come:
[tex]\sum_{i=0}^{\log(n)}[/tex] altre volte [tex]\sum_{i=0}^{\log(n)-1}[/tex]
Perchè a volte c'è il -1 e a volte no?
Grazie mille in anticipo.
Un' ultima cosa...mentre ci sono.
Ho provato a fare quest' altra:
[tex]T(n)=2T(n/3)+2T(n/9)+n[/tex]
Ho provato ad usare l'albero di ricorsione, non so se è corretto ma ho ottenuto:
Ora le mie domande sono, ho sbagliato ad impostarlo?
Come faccio a capire per l'altezza h dell' albero qual' è la base del logaritmo e l'argomento?
Qui per come l'ho scritto io, sembrerebbe si possa dire [tex]T(n)=O(n\log(n))[/tex]
E dovrei dimostrarlo per induzione giusto?
Sempre ammesso che non sia sbagliato, e mentre ci sono ti chiedo:
In alcuni casi uso le sommatorie per determinare il costo del lavoro ad ogni livello, non è questo il caso ma a volte capita, e mi ritrovo a volte delle sommatorie come:
[tex]\sum_{i=0}^{\log(n)}[/tex] altre volte [tex]\sum_{i=0}^{\log(n)-1}[/tex]
Perchè a volte c'è il -1 e a volte no?
Grazie mille in anticipo.
Ciao,
allora le equazioni di questo tipo, sono molto comode da vedere nell'albero, hai fatto bene ad utilizzarlo.
In questo modo ti faccio notare alcune cose su questo tipo di equazioni e ti rispondo alle tue ultime domande che hai scritto.
Se questa equazione la srotoli in un albero viene:
se vedi l'albero non è completo, ma ha due sottoalberi differenti di altezze differenti, $log_3(n)$ e $log_9(n)$.
Questo tipo di equazioni, di solito (ci saranno altri modi) gli si può trovare una limitazione superiore ed inferiore, completando l'albero, cioè in termini di equazioni,
maggiorare e minorare(?) l'equazione in questo modo:
Per una limitazione superiore:
$T(n) = 2T(n/3) + 2T(n/9) + n <= 2T(n/3) + 2T(n/3) + n = 4T(n/3) + n$
Per una limitazione inferiore:
$T(n) = 2T(n/3) + 2T(n/9) + n >= 2T(n/9) + 2T(n/9) + n = 4T(n/9) + n$
Sono facilmente risolvibili con il Master Theorem, ma ti mostro come risolverlo con l'albero così ti rispondo alla tua domanda di $logn -1$
Con il master, adesso non ricordo che se, si fanno queste minorazioni/maggiorazioni, bisogna usare il tipo di limitazione stretta cioè $o$ e $omega$, o-piccolo ed omega-piccolo.
O forse è il contrario, cioè con l'albero, ma son quasi sicuro che è con il master theorem per via dell'$epsilon$ che si usa nel trovare le limitazioni. Bho ti saprò dire.
Allora per la limitazione superiore di $T(n) = 4T(n/3) + n$:
All'altezza h, ci saranno le foglie. La massima altezza è dell'albero è $log_3(n)$.
In un'equazione di ricorrenza la ricorsione si ferma quando $n=1$, cioè quando arriva a $T(1$).
Le foglie dell'albero di ricorsione sono i valori $T(1)$. Questo avviene quando $i=h$, cioè quando $i = log_3(n)$.
Questo sostituito nell'albero, all'altezza $h$:
$4^h*(n/3^h) = 4^(log_3(n))*(n/(3^(log_3(n)))) = 4^(log_3(n))*(n/(n^(log_3(3)))) = 4^(log_3(n))*(n/n) = 4^(log_3(n)) = n^(log_3(4))$ queste sono il numero di foglie $T(1)$.
Adesso però bisogna calcolare in numero di nodi interni all'albero, per farlo si calcola tutti i nodi fino all'altezza $h-1$.
come prima basta sostituire $h=log_3n$:
$4^(h-1)*(n/3^(h-1)) = 4^(log_3(n)-1)*(n/(3^(log_3(n)-1)))$
Generalizziamo all'altezza $i$ e sommiamo tutto con una sommatoria:
$sum_{i=0}^(log_3(n)-1) (4^i)*(n/3^i)$
per proprietà delle potenze e delle sommatorie trasformiamo:
$n*(sum_{i=0}^(log_3(n)-1) (4/3)^i)$ che è una serie geometrica finita:
$n*((4/3)^((log_3n-1)+1)-1)/((4/3)-1) = 3n*(n^(log_3(4)) - 1) = 3n^(log_3(4)) - n <= 3n^(log_3(4))$
Sommiamo tutto quello trovato, cioè la somma dei nodi interni e il numero di foglie:
$3n^(log_3(4)) + n^(log_3(4)) = 4n^(log_3(4)) in O(n^(log_3(4)))$
Una limitazione superiore è $O(n^(log_3(4)))$.
Ti consiglio di provare a trovare la limitazione inferiore di $T(n) = 4T(n/9) + n$.
In questo caso, sarebbe da dimostrare che effettivamente $O(n^(log_3(4)))$ sia una limitazione corretta,
anzi, prova se riesci a dimostrarlo per induzione, e scrivi qua i conti, così, se non riesci come hai scritto qualche post sopra a fare i passaggi, ti si da una mano.
Spero sia chiaro, non è complicato basta imparere sti trucchetti. Ciao
allora le equazioni di questo tipo, sono molto comode da vedere nell'albero, hai fatto bene ad utilizzarlo.
In questo modo ti faccio notare alcune cose su questo tipo di equazioni e ti rispondo alle tue ultime domande che hai scritto.
Se questa equazione la srotoli in un albero viene:
se vedi l'albero non è completo, ma ha due sottoalberi differenti di altezze differenti, $log_3(n)$ e $log_9(n)$.
Questo tipo di equazioni, di solito (ci saranno altri modi) gli si può trovare una limitazione superiore ed inferiore, completando l'albero, cioè in termini di equazioni,
maggiorare e minorare(?) l'equazione in questo modo:
Per una limitazione superiore:
$T(n) = 2T(n/3) + 2T(n/9) + n <= 2T(n/3) + 2T(n/3) + n = 4T(n/3) + n$
Per una limitazione inferiore:
$T(n) = 2T(n/3) + 2T(n/9) + n >= 2T(n/9) + 2T(n/9) + n = 4T(n/9) + n$
Sono facilmente risolvibili con il Master Theorem, ma ti mostro come risolverlo con l'albero così ti rispondo alla tua domanda di $logn -1$
Con il master, adesso non ricordo che se, si fanno queste minorazioni/maggiorazioni, bisogna usare il tipo di limitazione stretta cioè $o$ e $omega$, o-piccolo ed omega-piccolo.
O forse è il contrario, cioè con l'albero, ma son quasi sicuro che è con il master theorem per via dell'$epsilon$ che si usa nel trovare le limitazioni. Bho ti saprò dire.
Allora per la limitazione superiore di $T(n) = 4T(n/3) + n$:
All'altezza h, ci saranno le foglie. La massima altezza è dell'albero è $log_3(n)$.
In un'equazione di ricorrenza la ricorsione si ferma quando $n=1$, cioè quando arriva a $T(1$).
Le foglie dell'albero di ricorsione sono i valori $T(1)$. Questo avviene quando $i=h$, cioè quando $i = log_3(n)$.
Questo sostituito nell'albero, all'altezza $h$:
$4^h*(n/3^h) = 4^(log_3(n))*(n/(3^(log_3(n)))) = 4^(log_3(n))*(n/(n^(log_3(3)))) = 4^(log_3(n))*(n/n) = 4^(log_3(n)) = n^(log_3(4))$ queste sono il numero di foglie $T(1)$.
Adesso però bisogna calcolare in numero di nodi interni all'albero, per farlo si calcola tutti i nodi fino all'altezza $h-1$.
come prima basta sostituire $h=log_3n$:
$4^(h-1)*(n/3^(h-1)) = 4^(log_3(n)-1)*(n/(3^(log_3(n)-1)))$
Generalizziamo all'altezza $i$ e sommiamo tutto con una sommatoria:
$sum_{i=0}^(log_3(n)-1) (4^i)*(n/3^i)$
per proprietà delle potenze e delle sommatorie trasformiamo:
$n*(sum_{i=0}^(log_3(n)-1) (4/3)^i)$ che è una serie geometrica finita:
$n*((4/3)^((log_3n-1)+1)-1)/((4/3)-1) = 3n*(n^(log_3(4)) - 1) = 3n^(log_3(4)) - n <= 3n^(log_3(4))$
Sommiamo tutto quello trovato, cioè la somma dei nodi interni e il numero di foglie:
$3n^(log_3(4)) + n^(log_3(4)) = 4n^(log_3(4)) in O(n^(log_3(4)))$
Una limitazione superiore è $O(n^(log_3(4)))$.
Ti consiglio di provare a trovare la limitazione inferiore di $T(n) = 4T(n/9) + n$.
In questo caso, sarebbe da dimostrare che effettivamente $O(n^(log_3(4)))$ sia una limitazione corretta,
anzi, prova se riesci a dimostrarlo per induzione, e scrivi qua i conti, così, se non riesci come hai scritto qualche post sopra a fare i passaggi, ti si da una mano.
Spero sia chiaro, non è complicato basta imparere sti trucchetti. Ciao
Si un paio di cose...nell' albero finale scrivi a destra ad esempio
[tex]4^h\frac{n}{3^h}[/tex]
Ora la frazione perchè è n fratto 3 alla h?
Penso sia una proprietà degli alberi, indica per caso il numero di nodi ad altezza h?
Poi quando hai lavorato sulla serie geometrica non ho capito:
[tex]3n(n^{\log_3(4)}-1)[/tex]
Allora credo che hai scambiato precedentemente n argomento del logaritmo con quattro terzi, ma come si arriva ad ottenere 4 come argomento del logaritmo?
Staavo provando a dimostrare per induzione...dovrei verificare che:
[tex]T(n)\leq n^\log_3(4)[/tex]
Allora considero le chiamate ricorsive per cui deve essere:
[tex]T(\frac{n}{3})=c(\frac{n}{3}^{\log_3(4)}[/tex]
[tex]4^h\frac{n}{3^h}[/tex]
Ora la frazione perchè è n fratto 3 alla h?
Penso sia una proprietà degli alberi, indica per caso il numero di nodi ad altezza h?
Poi quando hai lavorato sulla serie geometrica non ho capito:
[tex]3n(n^{\log_3(4)}-1)[/tex]
Allora credo che hai scambiato precedentemente n argomento del logaritmo con quattro terzi, ma come si arriva ad ottenere 4 come argomento del logaritmo?
Staavo provando a dimostrare per induzione...dovrei verificare che:
[tex]T(n)\leq n^\log_3(4)[/tex]
Allora considero le chiamate ricorsive per cui deve essere:
[tex]T(\frac{n}{3})=c(\frac{n}{3}^{\log_3(4)}[/tex]
Si un paio di cose...nell' albero finale scrivi a destra ad esempio
[tex]4^h\frac{n}{3^h}[/tex]
Ora la frazione perchè è n fratto 3 alla h?
Penso sia una proprietà degli alberi, indica per caso il numero di nodi ad altezza h?
Poi quando hai lavorato sulla serie geometrica non ho capito:
[tex]3n(n^{\log_3(4)}-1)[/tex]
Allora credo che hai scambiato precedentemente n argomento del logaritmo con quattro terzi, ma come si arriva ad ottenere 4 come argomento del logaritmo?
Staavo provando a dimostrare per induzione...dovrei verificare che:
[tex]T(n)\leq n^\log_3(4)[/tex]
Allora considero le chiamate ricorsive per cui deve essere:
[tex]T(\frac{n}{3})=c(\frac{n}{3}^{\log_3(4)})[/tex]
[tex]T(\frac{n}{9})=c(\frac{n}{9}^{\log_3(4)})[/tex]
Tornando all' equazione:
[tex]T(n)\leq 2c(\frac{n}{3}^{\log_3(4)})+2c(\frac{n}{9}^{\log_3(4)})[/tex]
Qui va bene come ragionamento?
Se si dovrei lavorare sulla disequazione, che non è il mio forte purtroppo
[tex]T(n)\leq 2c(\frac{n}{3}^{\log_3(4)}+\frac{n}{9}^{\log_3(4)})[/tex]
E lavorare internamente sui logaritmi?
[tex]4^h\frac{n}{3^h}[/tex]
Ora la frazione perchè è n fratto 3 alla h?
Penso sia una proprietà degli alberi, indica per caso il numero di nodi ad altezza h?
Poi quando hai lavorato sulla serie geometrica non ho capito:
[tex]3n(n^{\log_3(4)}-1)[/tex]
Allora credo che hai scambiato precedentemente n argomento del logaritmo con quattro terzi, ma come si arriva ad ottenere 4 come argomento del logaritmo?
Staavo provando a dimostrare per induzione...dovrei verificare che:
[tex]T(n)\leq n^\log_3(4)[/tex]
Allora considero le chiamate ricorsive per cui deve essere:
[tex]T(\frac{n}{3})=c(\frac{n}{3}^{\log_3(4)})[/tex]
[tex]T(\frac{n}{9})=c(\frac{n}{9}^{\log_3(4)})[/tex]
Tornando all' equazione:
[tex]T(n)\leq 2c(\frac{n}{3}^{\log_3(4)})+2c(\frac{n}{9}^{\log_3(4)})[/tex]
Qui va bene come ragionamento?
Se si dovrei lavorare sulla disequazione, che non è il mio forte purtroppo
[tex]T(n)\leq 2c(\frac{n}{3}^{\log_3(4)}+\frac{n}{9}^{\log_3(4)})[/tex]
E lavorare internamente sui logaritmi?
Bhe la parte riguardande l'albero, sono semplici passaggi matematici o collegati alle proprietà dell'albero e dei logartimi.
Ho visto adesso che nell'immagine a destra, nei primi 3 casi $4^0*n/$ sarebbe $4^0*n/3^0$.
Ho evitato di scrivere tutto nell'immagine se no pensavo non si capisse. Ma se leggi sotto ti scrivo ben tutto cercando di collegarmi all'immagine.
esatto sono proprio il numero di nodi all'altezza h, di solito in questi esercizi si scrive a destra il riassunto generico del livello.
Al livello h, le foglie sono $4^h$ con $h=log_3 n$ perciò le foglie sono $4^(log_3n)$ Infatti, la frazione $n/3^h$ viene cancellato, ti avevo scritto:
bhe è una proprietà deli logaritmi e dell'esponenziale, cioè:
$a^(log_b(n)) = n^(log_b(a))$
per il resto, hai impostato correttamente la prima parte della dimostrazione, ma dimentichi una cosa, la funzione $f(n)$
cioè viene:
$T(n) <= 2cn^(log_3(4))/3 + 2cn^(log_3(4))/9 + dn$
se te la metti così ti togli i logaritmi, ed è più facile ragionarci
$T(n) <= 2c(n^(1,26))/3 + 2c(n^(1,26))/9 + dn$
adesso sono si disequazioni ma semplici, maggiorare nulla di più, e mettere una condizione. Prova, come sempre se hai bisogno scrivi
Ho visto adesso che nell'immagine a destra, nei primi 3 casi $4^0*n/$ sarebbe $4^0*n/3^0$.
Ho evitato di scrivere tutto nell'immagine se no pensavo non si capisse. Ma se leggi sotto ti scrivo ben tutto cercando di collegarmi all'immagine.
"Darèios89":
Si un paio di cose...nell' albero finale scrivi a destra ad esempio
$4^h*n/3$
Ora la frazione perchè è n fratto 3 alla h?
Penso sia una proprietà degli alberi, indica per caso il numero di nodi ad altezza h?
esatto sono proprio il numero di nodi all'altezza h, di solito in questi esercizi si scrive a destra il riassunto generico del livello.
Al livello h, le foglie sono $4^h$ con $h=log_3 n$ perciò le foglie sono $4^(log_3n)$ Infatti, la frazione $n/3^h$ viene cancellato, ti avevo scritto:
"ham_burst":
Questo sostituito nell'albero, all'altezza h:
$4^h*(n/3^h) = 4^(log_3(n))*(n/(3^(log_3(n)))) = 4^(log_3(n))*(n/(n^(log_3(3)))) = 4^(log_3(n))*(n/n) = 4^(log_3(n)) = n^(log_3(4))$ queste sono il numero di foglie $T(1)$.
"Darèios89":
Allora credo che hai scambiato precedentemente n argomento del logaritmo con quattro terzi, ma come si arriva ad ottenere 4 come argomento del logaritmo?
bhe è una proprietà deli logaritmi e dell'esponenziale, cioè:
$a^(log_b(n)) = n^(log_b(a))$
per il resto, hai impostato correttamente la prima parte della dimostrazione, ma dimentichi una cosa, la funzione $f(n)$
cioè viene:
$T(n) <= 2cn^(log_3(4))/3 + 2cn^(log_3(4))/9 + dn$
se te la metti così ti togli i logaritmi, ed è più facile ragionarci
$T(n) <= 2c(n^(1,26))/3 + 2c(n^(1,26))/9 + dn$
adesso sono si disequazioni ma semplici, maggiorare nulla di più, e mettere una condizione. Prova, come sempre se hai bisogno scrivi
Mh non ti ho seguito...non ho capito nella parte in cui dici "che è una serie geometrica finita"
Come applichi la proprietà dei logaritmi, avremmo:
[tex]\frac{\frac{4}{3}^{(\log_3(n)-1)+1}-1}{\frac{4}{3}-1}[/tex]
Ora sullo scambio ci siamo...ma dovrei ottenre una cosa del tipo:
[tex]\frac{\frac{4}{3}^{(\log_3(n)-1)}*\frac{4}{3}-1}{\frac{4}{3}-1}[/tex]
[tex]\frac{n^{(\log_3(4)-\log_3(3)-1)}*\frac{4}{3}-1}{\frac{4}{3}-1}[/tex]
[tex]\frac{n^{(\log_3(4)-2)}*\frac{4}{3}-1}{\frac{4}{3}-1}[/tex]
Perchè log in base 3 di 3 fa 1 e quindi avrei -1 sommato a -1 che fa -2.
Come sei arrivato ad avere:
[tex]3n(n^{\log_3(4)}-1)[/tex]
Nella disequazione per induzione non ho capito perchè al posto di scrivere
[tex]\frac{n}{3}[/tex] e [tex]\frac{n}{9}[/tex] che elevano il logaritmo hai scritto il 3 e il 9 come denominatore di una frazione...
Non vorrei che non avessi capito bene la mia scrittura:
Cioè io ho n terzi elevato a qualcosa ed n noni elevato a qualcosa, quindi come fai a scrivere in quel modo il denominatore...così non hai più una frazione che eleva il log, ma hai n che eleva il log fratto qualcosa...che dovrebbe cambiare...
Come applichi la proprietà dei logaritmi, avremmo:
[tex]\frac{\frac{4}{3}^{(\log_3(n)-1)+1}-1}{\frac{4}{3}-1}[/tex]
Ora sullo scambio ci siamo...ma dovrei ottenre una cosa del tipo:
[tex]\frac{\frac{4}{3}^{(\log_3(n)-1)}*\frac{4}{3}-1}{\frac{4}{3}-1}[/tex]
[tex]\frac{n^{(\log_3(4)-\log_3(3)-1)}*\frac{4}{3}-1}{\frac{4}{3}-1}[/tex]
[tex]\frac{n^{(\log_3(4)-2)}*\frac{4}{3}-1}{\frac{4}{3}-1}[/tex]
Perchè log in base 3 di 3 fa 1 e quindi avrei -1 sommato a -1 che fa -2.
Come sei arrivato ad avere:
[tex]3n(n^{\log_3(4)}-1)[/tex]
Nella disequazione per induzione non ho capito perchè al posto di scrivere
[tex]\frac{n}{3}[/tex] e [tex]\frac{n}{9}[/tex] che elevano il logaritmo hai scritto il 3 e il 9 come denominatore di una frazione...
Non vorrei che non avessi capito bene la mia scrittura:
Cioè io ho n terzi elevato a qualcosa ed n noni elevato a qualcosa, quindi come fai a scrivere in quel modo il denominatore...così non hai più una frazione che eleva il log, ma hai n che eleva il log fratto qualcosa...che dovrebbe cambiare...
allora, te sbagli a vedere l'esponenziale, ti metto le parentesi:
$n*((4/3)^(((log_3n)-1)+1)-1)/((4/3)-1) = n*((4/3)^(log_3n)-1)/((4/3)-1)$ ok adesso?
Si, scusa, hai ragione, na svista:
$T(n) <= 2c(n/3)^(log_3(4)) + 2c(n/9)^(log_3(4)) + dn = 2c(n^(log_3(4))/3^(log_3(4)))+ 2c(n^(log_3(4))/9^(log_3(4))) + dn $
proprietà delle potenze, dei logaritmi e semplifichi...e vedi che è una costante...
adesso che vedo meglio mi sembra che non cambi molto da prima, sicuramente il fattre costante della condizione varia,
ma non penso non venga la dimostrazione per questo... ma adesso però nn ho molta voglia di fare conti....
PS: ho fatto due conti straveloci, non cambia nulla, basta ricordarsi che siamo in classi di complessità e limiti asinotici...
e si può togliere la costante $d$ da $dn$, non cambia nulla, ma ti rende la vita più facile...
$n*((4/3)^(((log_3n)-1)+1)-1)/((4/3)-1) = n*((4/3)^(log_3n)-1)/((4/3)-1)$ ok adesso?
Nella disequazione per induzione non ho capito perchè al posto di scrivere
$n/3$ e $n/9$ che elevano il logaritmo hai scritto il 3 e il 9 come denominatore di una frazione...
Si, scusa, hai ragione, na svista:
$T(n) <= 2c(n/3)^(log_3(4)) + 2c(n/9)^(log_3(4)) + dn = 2c(n^(log_3(4))/3^(log_3(4)))+ 2c(n^(log_3(4))/9^(log_3(4))) + dn $
proprietà delle potenze, dei logaritmi e semplifichi...e vedi che è una costante...
adesso che vedo meglio mi sembra che non cambi molto da prima, sicuramente il fattre costante della condizione varia,
ma non penso non venga la dimostrazione per questo... ma adesso però nn ho molta voglia di fare conti....
PS: ho fatto due conti straveloci, non cambia nulla, basta ricordarsi che siamo in classi di complessità e limiti asinotici...
e si può togliere la costante $d$ da $dn$, non cambia nulla, ma ti rende la vita più facile...
Grazie della pazienza che hai
C'è solo una piccola cosa che mi sfugge:
[tex]n*\frac{\frac{4}{3}^{\log_3(n)}-1}{\frac{4}{3}-1}[/tex]
Ora per la proprietà dei logaritmi scrivo:
[tex]n*\frac{n^{\log_3(\frac{4}{3})}-1}{\frac{4}{3}-1}[/tex]
[tex]n*\frac{n^{\log_3(4)-\log_3(3)}-1}{\frac{4}{3}-1}[/tex]
[tex]n*\frac{n^{\log_3(4)-1}-1}{\frac{4}{3}-1}[/tex]
Mi rimane quel -1 vicino al logaritmo....cosa sbaglio?
Quanto al resto da dimostrare per induzione, ho provato a fare dei conti, temo di aver sbagliato qualcosa, allora seguendo la tua strada, con le proprietà delle potenze e dei logaritmi, al denominatore scambiando l' argomento dei logaritmi ottengo come risultato nel primo denominatore 4 e al secondo 16 e quindi facendo il minimo comune multiplo avrei:
[tex]2c(\frac{4n^{\log_3(4)}+n^{\log_3(4)}}{16})+dn[/tex]
Ora se non ricordo male dato che ho due potenze n che elevano il logaritmo, nelle disequazioni si eguagliano gli argomenti...qui non so se posso sommare i logaritmi facendo una cosa come:
[tex]2c(\frac{4\log_3(4)+\log_3(4)}{16})+dn[/tex]
Non sono certo di questi passaggi...
C'è solo una piccola cosa che mi sfugge:
[tex]n*\frac{\frac{4}{3}^{\log_3(n)}-1}{\frac{4}{3}-1}[/tex]
Ora per la proprietà dei logaritmi scrivo:
[tex]n*\frac{n^{\log_3(\frac{4}{3})}-1}{\frac{4}{3}-1}[/tex]
[tex]n*\frac{n^{\log_3(4)-\log_3(3)}-1}{\frac{4}{3}-1}[/tex]
[tex]n*\frac{n^{\log_3(4)-1}-1}{\frac{4}{3}-1}[/tex]
Mi rimane quel -1 vicino al logaritmo....cosa sbaglio?
Quanto al resto da dimostrare per induzione, ho provato a fare dei conti, temo di aver sbagliato qualcosa, allora seguendo la tua strada, con le proprietà delle potenze e dei logaritmi, al denominatore scambiando l' argomento dei logaritmi ottengo come risultato nel primo denominatore 4 e al secondo 16 e quindi facendo il minimo comune multiplo avrei:
[tex]2c(\frac{4n^{\log_3(4)}+n^{\log_3(4)}}{16})+dn[/tex]
Ora se non ricordo male dato che ho due potenze n che elevano il logaritmo, nelle disequazioni si eguagliano gli argomenti...qui non so se posso sommare i logaritmi facendo una cosa come:
[tex]2c(\frac{4\log_3(4)+\log_3(4)}{16})+dn[/tex]
Non sono certo di questi passaggi...
allura: passaggi corretti, solo un ""trucchetto"" ho usato, una normale proprietà delle potenze
(si può vedere in vari modi ma te la faccio vedere come i passaggi che hai fatto te, fin dove sei arrivato è corretto, continuo da li:
$n*(n^(log_3(4)-1) -1)/((4/3)-1)$
prima cosa meglio togliersi di mezzo il denominatore:
$4/3 -1 = 1/3$
$n*(n^(log_3(4)-1) -1)/(1/3) = 3n*(n^(log_3(4)-1) -1)$ svolgo la moltiplicazione (ho commesso pure un errorino, ma con la maggiorazione sparisce:
$3n^((log_3(4)-1)+1) - 3n = 3n^(log_3(4)) - 3n <= 3n^(log_3(4))$
si poteva vedere anche come $n^(log_3(4)-1) = n^(log_3(4))/n$ e continuare togliendo il donominatore con la moltiplicazione, de gustibus
l'altro pezzo te lo spiego quando torno...stay tuned
(si può vedere in vari modi ma te la faccio vedere come i passaggi che hai fatto te, fin dove sei arrivato è corretto, continuo da li:
$n*(n^(log_3(4)-1) -1)/((4/3)-1)$
prima cosa meglio togliersi di mezzo il denominatore:
$4/3 -1 = 1/3$
$n*(n^(log_3(4)-1) -1)/(1/3) = 3n*(n^(log_3(4)-1) -1)$ svolgo la moltiplicazione (ho commesso pure un errorino, ma con la maggiorazione sparisce:
$3n^((log_3(4)-1)+1) - 3n = 3n^(log_3(4)) - 3n <= 3n^(log_3(4))$
si poteva vedere anche come $n^(log_3(4)-1) = n^(log_3(4))/n$ e continuare togliendo il donominatore con la moltiplicazione, de gustibus
l'altro pezzo te lo spiego quando torno...stay tuned
Certo benissimo, ti ringrazio, intanto questa parte l' ho capita adesso 
son contento che l'hai capita 
per la dimostrazione, secondo me ti sei complicato la vita, non ho mica capito come sei riuscito a togliere la base $n$ dell'esponenziale....
ma ti mostro molto più semplicemente, senza usare strane proprietà, tutti i passaggi così è chiaro (spero):
$T(n) <= 2c(n/3)^(log_3(4)) + 2c(n/9)^(log_3(4)) + n = 2c(n^(log_3(4))/3^(log_3(4)))+ 2c(n^(log_3(4))/9^(log_3(4))) + n =$
$2c(n^(log_3(4))/4)+ 2c(n^(log_3(4))/3^(2*(log_3(4)))) + n = c(n^(log_3(4))/2)+ 2c(n^(log_3(4))/(3^(log_3(4)))^2) + n =$
$c(n^(log_3(4))/2)+ 2c(n^(log_3(4))/4^2) + n = c(n^(log_3(4))/2)+ 2c(n^(log_3(4))/16) + n = c(n^(log_3(4))/2)+ c(n^(log_3(4))/8) + n =$
$(1/2)cn^(log_3(4))+ (1/8)cn^(log_3(4)) + n = (1/2 + 1/8)cn^(log_3(4)) + n = (5/8)cn^(log_3(4)) + n <= (1 + 5/8)cn^(log_3(4)) = (13/8)cn^(log_3(4)) <= cn^(log_3(4))$
per $n>=m=1$ e $c>=8/13$
se non ho fatto castronerie abbiamo dimostrato (il caso base lo ho lascito stare) che $T(n) in O(n^(log_3(4)))$
Ti dico anche che questa equazione ha una limitazione ancora più stretta cioè $T(n) = 2T(n/3) + 2T(n/9) + n in Theta(n)$
ti incito a dimostrare, con il metodo della sostituzione, che ha una limitazione superiore $O(n)$ ed una inferiore (che ti ho già indicato come fare) $Omega(n)$.
ti ho mostrato la strada più lunga perchè mi avevi fatto domande sull'albero di ricorsione e sull'induzione, così hai tutti i passaggi.
Spero sia utilie
EDIT: sistemato formule
per la dimostrazione, secondo me ti sei complicato la vita, non ho mica capito come sei riuscito a togliere la base $n$ dell'esponenziale....
ma ti mostro molto più semplicemente, senza usare strane proprietà, tutti i passaggi così è chiaro (spero):
$T(n) <= 2c(n/3)^(log_3(4)) + 2c(n/9)^(log_3(4)) + n = 2c(n^(log_3(4))/3^(log_3(4)))+ 2c(n^(log_3(4))/9^(log_3(4))) + n =$
$2c(n^(log_3(4))/4)+ 2c(n^(log_3(4))/3^(2*(log_3(4)))) + n = c(n^(log_3(4))/2)+ 2c(n^(log_3(4))/(3^(log_3(4)))^2) + n =$
$c(n^(log_3(4))/2)+ 2c(n^(log_3(4))/4^2) + n = c(n^(log_3(4))/2)+ 2c(n^(log_3(4))/16) + n = c(n^(log_3(4))/2)+ c(n^(log_3(4))/8) + n =$
$(1/2)cn^(log_3(4))+ (1/8)cn^(log_3(4)) + n = (1/2 + 1/8)cn^(log_3(4)) + n = (5/8)cn^(log_3(4)) + n <= (1 + 5/8)cn^(log_3(4)) = (13/8)cn^(log_3(4)) <= cn^(log_3(4))$
per $n>=m=1$ e $c>=8/13$
se non ho fatto castronerie abbiamo dimostrato (il caso base lo ho lascito stare) che $T(n) in O(n^(log_3(4)))$
Ti dico anche che questa equazione ha una limitazione ancora più stretta cioè $T(n) = 2T(n/3) + 2T(n/9) + n in Theta(n)$
ti incito a dimostrare, con il metodo della sostituzione, che ha una limitazione superiore $O(n)$ ed una inferiore (che ti ho già indicato come fare) $Omega(n)$.
ti ho mostrato la strada più lunga perchè mi avevi fatto domande sull'albero di ricorsione e sull'induzione, così hai tutti i passaggi.
Spero sia utilie
EDIT: sistemato formule
AH ok d'accordo mi ero dimenticato di alcune cose infatti.
L'unica cosa è la parte finale, non sono pratico con le maggiorazioni.
[tex](\frac{5}{8})cn^{\log_3(4)}+n\leq(1+\frac{5}{8})^\log_3(4)[/tex]
Non ci curiamo del fatto che ci fosse +n?
In teoria dovrebbe valere sempre la disuguaglianza e forse per questo l' abbiamo trascurata.
Grazie in anticipo, provo nel frattempo a fare altre dimostrazioni.
L'unica cosa è la parte finale, non sono pratico con le maggiorazioni.
[tex](\frac{5}{8})cn^{\log_3(4)}+n\leq(1+\frac{5}{8})^\log_3(4)[/tex]
Non ci curiamo del fatto che ci fosse +n?
In teoria dovrebbe valere sempre la disuguaglianza e forse per questo l' abbiamo trascurata.
Grazie in anticipo, provo nel frattempo a fare altre dimostrazioni.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo