[Algoritmi]Svolgimento ricorrenza
Ciao a tutti..
Qualcuno potrebbe spiegarmi e farmi vedere tutti i vari passaggi per risolvere questa equazione di ricorrenza con l'albero di ricorsione?
T(n)= T(n/3)+T(n/4)+n
Grazie.
Qualcuno potrebbe spiegarmi e farmi vedere tutti i vari passaggi per risolvere questa equazione di ricorrenza con l'albero di ricorsione?
T(n)= T(n/3)+T(n/4)+n
Grazie.
Risposte
Ciao,
se noti questa ricorrenza a due punti di espansione $T(n/3)$ e $T(n/4)$; per risolverlo con l'albero ci sono degli accorgimenti da seguire.
I passaggi li descrissi in parecchi post con svolgimento e tutto il resto, prova a cercarli con "Cerca"
se avrai problemi, dopo aver letto quei post, scrivili pure qui.
PS: di solito in questo forum si preferisce che l'utente cerchi di svolgere un esercizio e chiedere aiuto sui punti non chiari, non che venga svolto da qualcun'altro
se noti questa ricorrenza a due punti di espansione $T(n/3)$ e $T(n/4)$; per risolverlo con l'albero ci sono degli accorgimenti da seguire.
I passaggi li descrissi in parecchi post con svolgimento e tutto il resto, prova a cercarli con "Cerca"
se avrai problemi, dopo aver letto quei post, scrivili pure qui.
PS: di solito in questo forum si preferisce che l'utente cerchi di svolgere un esercizio e chiedere aiuto sui punti non chiari, non che venga svolto da qualcun'altro
Ok..allora dò una occhiata ai post precedenti e in caso se ho problemi scrivo di nuovo. Grazie 
Ho svolto questa ricorrenza e chiedo il vostro aiuto per verificare se sia corretta o meno.
[tex]T(n)=T(\frac{n}{4})+T(\frac{3n}{4})+n[/tex]
L'altezza dell'albero è [tex]h=\log \frac{4}{3} n[/tex]
e quindi il numero delle foglie sarà:[tex]n^{\log \frac{4}{3} 2}[/tex]
La struttura dell'albero è:
[tex]n[/tex]
[tex]\frac{n}{4}+\frac{3n}{4}= n[/tex]
[tex]\frac{n}{16}+\frac{3n}{16}+\frac{3n}{16}+\frac{9n}{16}= n[/tex]
Quindi suppongo che la mia ricorrenza avrà soluzione [tex]O(n \log n)[/tex]
Andrò a dimostrare che [tex]T(n)\leq dn \log n[/tex]
d è una costante positiva.
[tex]T(n)\leq T(\frac{n}{4})+T(\frac{3n}{4})+n[/tex]
[tex]\leq d(\frac{n}{4})\log (\frac{n}{4})+d(\frac{3n}{4})\log (\frac{3n}{4})+cn[/tex]
[tex]\leq d(\frac{n}{4})\log (n)-d(\frac{n}{4})\log (4)+d(\frac{3n}{4})\log (n)-d(\frac{3n}{4})\log (\frac{4}{3})+cn[/tex]
[tex]= dn\log (n)-d(\frac{n}{4})\log (4)-d(\frac{3n}{4})\log (\frac{4}{3})+cn[/tex]
[tex]= dn\log (n)-d(\frac{n}{4})\log (4)-d(\frac{3n}{4})\log (4)-d(\frac{3n}{4})\log (3)+ cn[/tex]
[tex]= dn\log (n)-d(n)\log (4)-d(\frac{3n}{4})\log (3)+ cn[/tex]
[tex]= dn\log (n)-dn(\log (4)-\frac{3}{4}\log (3))+ cn[/tex]
[tex]\leq dn \log (n)[/tex]
che è [tex]O(n \log n)[/tex]
E' corretto lo svolgimento???
Grazie.
[tex]T(n)=T(\frac{n}{4})+T(\frac{3n}{4})+n[/tex]
L'altezza dell'albero è [tex]h=\log \frac{4}{3} n[/tex]
e quindi il numero delle foglie sarà:[tex]n^{\log \frac{4}{3} 2}[/tex]
La struttura dell'albero è:
[tex]n[/tex]
[tex]\frac{n}{4}+\frac{3n}{4}= n[/tex]
[tex]\frac{n}{16}+\frac{3n}{16}+\frac{3n}{16}+\frac{9n}{16}= n[/tex]
Quindi suppongo che la mia ricorrenza avrà soluzione [tex]O(n \log n)[/tex]
Andrò a dimostrare che [tex]T(n)\leq dn \log n[/tex]
d è una costante positiva.
[tex]T(n)\leq T(\frac{n}{4})+T(\frac{3n}{4})+n[/tex]
[tex]\leq d(\frac{n}{4})\log (\frac{n}{4})+d(\frac{3n}{4})\log (\frac{3n}{4})+cn[/tex]
[tex]\leq d(\frac{n}{4})\log (n)-d(\frac{n}{4})\log (4)+d(\frac{3n}{4})\log (n)-d(\frac{3n}{4})\log (\frac{4}{3})+cn[/tex]
[tex]= dn\log (n)-d(\frac{n}{4})\log (4)-d(\frac{3n}{4})\log (\frac{4}{3})+cn[/tex]
[tex]= dn\log (n)-d(\frac{n}{4})\log (4)-d(\frac{3n}{4})\log (4)-d(\frac{3n}{4})\log (3)+ cn[/tex]
[tex]= dn\log (n)-d(n)\log (4)-d(\frac{3n}{4})\log (3)+ cn[/tex]
[tex]= dn\log (n)-dn(\log (4)-\frac{3}{4}\log (3))+ cn[/tex]
[tex]\leq dn \log (n)[/tex]
che è [tex]O(n \log n)[/tex]
E' corretto lo svolgimento???
Grazie.
Ciao,
il procedimento è corretto, ci sono delle piccole inesattezze formali, te le sottolineo
non è propriamente corretto parlare di altezza in questo caso, è meglio dire il più lungo cammino radice-foglia (perchè?) ha altezza $log_(4/3)(n)$ (un punto che molti "sbagliano" nel capirlo, sai perchè ha la base invertita rispetto al fattore di ricorsione $3/4$?)
le foglie è inutile calcolare in questo caso, dato che dopo un certo livello i nodi interni decrescono perciò è pieno di "buchi", si potrebbe dire che è un limite superiore stretto, ma è inutile parlarne in questo tipo di ricorrenze.
l'albero darà come soluzione la complessità superiore $O(nlog_{4/3)(n))$ ma che non ha significato se è stretto sulla ricorrenza, perciò è valido dire essere $O(nlog_2(n))$
finalmente vedo qualcuno che prende coraggio a dimostrare induttivamente ciò che il metodo dell'albero calcola, ottimo
Però c'è una cosa che manca, per quale $d$ e $n$ la tua ipotesi è vera? non lo dici.
I passaggi credo siano ok, io avrei utilizzato come ipotesi $dnlog_2(n)$ ma anche così potrebbe andare, saresti più preciso nelle costanti, una volta dimostrato per un qualche $d$ va tutto bene il resto.
Una seconda cosa, non dovrebbe servire aggiungere una costante al fattore libero della ricorrenza è puro $n$, non ha costanti nascoste se lo fosse ci sarebbe scritto $O(n)$.
il procedimento è corretto, ci sono delle piccole inesattezze formali, te le sottolineo
L'altezza dell'albero è [tex]h=\log \frac{4}{3} n[/tex]
non è propriamente corretto parlare di altezza in questo caso, è meglio dire il più lungo cammino radice-foglia (perchè?) ha altezza $log_(4/3)(n)$ (un punto che molti "sbagliano" nel capirlo, sai perchè ha la base invertita rispetto al fattore di ricorsione $3/4$?)
e quindi il numero delle foglie sarà:[tex]n^{\log \frac{4}{3} 2}[/tex]
le foglie è inutile calcolare in questo caso, dato che dopo un certo livello i nodi interni decrescono perciò è pieno di "buchi", si potrebbe dire che è un limite superiore stretto, ma è inutile parlarne in questo tipo di ricorrenze.
La struttura dell'albero è:
[tex]n[/tex]
[tex]\frac{n}{4}+\frac{3n}{4}= n[/tex]
[tex]\frac{n}{16}+\frac{3n}{16}+\frac{3n}{16}+\frac{9n}{16}= n[/tex]
Quindi suppongo che la mia ricorrenza avrà soluzione [tex]O(n \log n)[/tex]
l'albero darà come soluzione la complessità superiore $O(nlog_{4/3)(n))$ ma che non ha significato se è stretto sulla ricorrenza, perciò è valido dire essere $O(nlog_2(n))$
Andrò a dimostrare che [tex]T(n)\leq dn \log n[/tex]
d è una costante positiva.
[tex]T(n)\leq T(\frac{n}{4})+T(\frac{3n}{4})+n[/tex]
[tex]\leq d(\frac{n}{4})\log (\frac{n}{4})+d(\frac{3n}{4})\log (\frac{3n}{4})+cn[/tex]
[tex]\leq d(\frac{n}{4})\log (n)-d(\frac{n}{4})\log (4)+d(\frac{3n}{4})\log (n)-d(\frac{3n}{4})\log (\frac{4}{3})+cn[/tex]
[tex]= dn\log (n)-d(\frac{n}{4})\log (4)-d(\frac{3n}{4})\log (\frac{4}{3})+cn[/tex]
[tex]= dn\log (n)-d(\frac{n}{4})\log (4)-d(\frac{3n}{4})\log (4)-d(\frac{3n}{4})\log (3)+ cn[/tex]
[tex]= dn\log (n)-d(n)\log (4)-d(\frac{3n}{4})\log (3)+ cn[/tex]
[tex]= dn\log (n)-dn(\log (4)-\frac{3}{4}\log (3))+ cn[/tex]
[tex]\leq dn \log (n)[/tex]
che è [tex]O(n \log n)[/tex]
finalmente vedo qualcuno che prende coraggio a dimostrare induttivamente ciò che il metodo dell'albero calcola, ottimo
Però c'è una cosa che manca, per quale $d$ e $n$ la tua ipotesi è vera? non lo dici.
I passaggi credo siano ok, io avrei utilizzato come ipotesi $dnlog_2(n)$ ma anche così potrebbe andare, saresti più preciso nelle costanti, una volta dimostrato per un qualche $d$ va tutto bene il resto.
Una seconda cosa, non dovrebbe servire aggiungere una costante al fattore libero della ricorrenza è puro $n$, non ha costanti nascoste se lo fosse ci sarebbe scritto $O(n)$.
Ciao, grazie degli accorgimenti intanto.
Allora, prima di svolgere i calcoli della dimostrazione per induzione dirò per qualche [tex]d>0[/tex].
Quando avrò fatto tutti i calcoli della dimostrazione, dirò che è vera per:
[tex]d\geq \frac{c}{\log (4)-(\frac{3}{4}\log 3)}[/tex]
c è una costante maggiore di zero.
E' corretto? Non ho molta dimestichezza ancora
Allora, prima di svolgere i calcoli della dimostrazione per induzione dirò per qualche [tex]d>0[/tex].
Quando avrò fatto tutti i calcoli della dimostrazione, dirò che è vera per:
[tex]d\geq \frac{c}{\log (4)-(\frac{3}{4}\log 3)}[/tex]
c è una costante maggiore di zero.
E' corretto? Non ho molta dimestichezza ancora
"krak":
Ciao, grazie degli accorgimenti intanto.
Allora, prima di svolgere i calcoli della dimostrazione per induzione dirò per qualche [tex]d>0[/tex].
Quando avrò fatto tutti i calcoli della dimostrazione, dirò che è vera per:
[tex]d\geq \frac{c}{\log (4)-(\frac{3}{4}\log 3)}[/tex]
c è una costante maggiore di zero.
E' corretto? Non ho molta dimestichezza ancora
Si si è ok
Ma non si fa PRIMA della dimostrazione, non è un $d$ fissato, siamo una dimostrazione per induzione. Per essere pignoli c'è anche il caso base da inserire e il per quale $m>= 0$ l'ipotesi è sempre vera.
Cmq anche se non inerisci una costante $c$ (che come detto non serve in questo caso), utilizzando un software di calcolo (non avevo voglia di farlo a mano), l'ipotesi risulta essere vera per $d>= 4/5$ (per $O(nlog_2(n))$).
Ciao.
Ok, ho capito fin qua.
Stavo provando a fare il calcolo del caso base, ma non sono sicuro sia corretto come ho fatto.
Allora, la mia equazione di partenza è:
[tex]T(n)= T(\frac{n}{4})+T(\frac{3n}{4})+n[/tex]
Provo per [tex]n=1[/tex] ed ottengo:
[tex]T(1)=T(\frac{1}{4})+T(\frac{3}{4})+1 = 2 \leq O(1 \log 1)[/tex] che è falsa!
Provo per [tex]n=2[/tex] ed ottengo:
[tex]T(2)=T(\frac{2}{4})+T(\frac{6}{4})+2 = 4 \leq O(2 \log 2)[/tex] che è falsa!
Provo per [tex]n=3[/tex] ed ottengo:
[tex]T(3)=T(\frac{3}{4})+T(\frac{9}{4})+3 = 6 \leq O(3 \log 3)[/tex] che è falsa!
Provo per [tex]n=4[/tex] ed ottengo:
[tex]T(4)=T(\frac{4}{4})+T(\frac{12}{4})+4 = 8 \leq O(4 \log 4)[/tex] che è vera!
Quindi possiamo concludere che [tex]T(n)=O(n \log n)[/tex] per qualunque [tex]n\geq 4[/tex].
E' giusto?
Ok, ho capito fin qua.
Stavo provando a fare il calcolo del caso base, ma non sono sicuro sia corretto come ho fatto.
Allora, la mia equazione di partenza è:
[tex]T(n)= T(\frac{n}{4})+T(\frac{3n}{4})+n[/tex]
Provo per [tex]n=1[/tex] ed ottengo:
[tex]T(1)=T(\frac{1}{4})+T(\frac{3}{4})+1 = 2 \leq O(1 \log 1)[/tex] che è falsa!
Provo per [tex]n=2[/tex] ed ottengo:
[tex]T(2)=T(\frac{2}{4})+T(\frac{6}{4})+2 = 4 \leq O(2 \log 2)[/tex] che è falsa!
Provo per [tex]n=3[/tex] ed ottengo:
[tex]T(3)=T(\frac{3}{4})+T(\frac{9}{4})+3 = 6 \leq O(3 \log 3)[/tex] che è falsa!
Provo per [tex]n=4[/tex] ed ottengo:
[tex]T(4)=T(\frac{4}{4})+T(\frac{12}{4})+4 = 8 \leq O(4 \log 4)[/tex] che è vera!
Quindi possiamo concludere che [tex]T(n)=O(n \log n)[/tex] per qualunque [tex]n\geq 4[/tex].
E' giusto?
"krak":
E' giusto?
mmm si e no...
bisogna fare attenzione, alle costanti e a scrivere il tutto correttamente.
Devi dire per quale $c$ è vero il caso base.
Provo per [tex]n=1[/tex] ed ottengo:
[tex]T(1)=1 \not\leq c 1 \log 1 = 0[/tex] che è falsa!
Ricorda che di solito esiste un costo base nelle equazioni di ricorrenza, es: $O(1) if n=1$
Visto che il caso base non funziona ce lo scegliamo noi:
[tex]T(2)=T(1)+T(1)+2 = 4 \leq c(2 \log 2)[/tex] che è vera per $c>=2$
perciò possiamo dire che $T(n) in O(nlog_2(n)) \forall n>2 \wedge c=2$
PS: per il caso base si può continuare:
$T(3)=T(1)+T(1)+3 = 5 \leq c(3 \log 3) -> c>=(5 log(2))/(3 log(3))$
$T(4)=T(1)+T(1)+4 = 6 \leq c(4 \log 4) -> c>=3/4$
come detto lo scegliamo noi, ma ne basta uno solo
PS2: se vuoi provare con un altra ricorrenza e la dimostrazione per induzione (chiamato in algoritmica "metodo della sostituzione" o "metodo per tentativi"), ti propongo di dimostrare che $3T(n/4) + nlog(n) in O(nlog(n))$ (o se vuoi anche mi sembra essere $\Theta(nlog(n))$. Come prima $O(1)$ quando $n=1$.
Emh..credo di aver capito.
Per sicurezza provo a svolgere quella dimostrazione che mi hai consigliato e in caso mi correggi =)
Per sicurezza provo a svolgere quella dimostrazione che mi hai consigliato e in caso mi correggi =)
Allora, provo a dimostrare che:
[tex]T(n)=3T(\frac{n}{4})+ n \log n \leq c(n \log n)[/tex]
Supponiamo che il costo base della ricorrenza sia: [tex]O(1)[/tex] if [tex]n=1[/tex].
Provo per [tex]n=1[/tex] ed ottengo:
[tex]T(1)=(\frac{3}{4})+ 1 \log 1 = (\frac{3}{4})\leq 1 \log 1[/tex] che è falsa!
Provo per [tex]n=2[/tex] ed ottengo:
[tex]T(2)=T(1)+ 2 \log 2 = (\frac{7}{2}) \leq c(2 \log 2)[/tex] che è vera per [tex]c\geq (\frac{7}{4})[/tex]
Perciò possiamo dire che [tex]T(n)[/tex] appartiene a [tex]O(n \log n)[/tex] per qualunque [tex]n>2[/tex] e
[tex]c= (\frac{7}{4})[/tex].
Adesso ci siamo? è corretto?
[tex]T(n)=3T(\frac{n}{4})+ n \log n \leq c(n \log n)[/tex]
Supponiamo che il costo base della ricorrenza sia: [tex]O(1)[/tex] if [tex]n=1[/tex].
Provo per [tex]n=1[/tex] ed ottengo:
[tex]T(1)=(\frac{3}{4})+ 1 \log 1 = (\frac{3}{4})\leq 1 \log 1[/tex] che è falsa!
Provo per [tex]n=2[/tex] ed ottengo:
[tex]T(2)=T(1)+ 2 \log 2 = (\frac{7}{2}) \leq c(2 \log 2)[/tex] che è vera per [tex]c\geq (\frac{7}{4})[/tex]
Perciò possiamo dire che [tex]T(n)[/tex] appartiene a [tex]O(n \log n)[/tex] per qualunque [tex]n>2[/tex] e
[tex]c= (\frac{7}{4})[/tex].
Adesso ci siamo? è corretto?
Adesso ci siamo? è corretto?
a costo di essere stucchevole, devo dirti che c'è sempre qualcosa che non va... Cerchiamo di riordinare un po' tutto."krak":
Provo per [tex]n=1[/tex] ed ottengo:
[tex]T(1)=(\frac{3}{4})+ 1 \log 1 = (\frac{3}{4})\leq 1 \log 1[/tex] che è falsa!
perchè $3/4$? a me risulta che abbiamo ipotizzato essere $1$...
Provo per [tex]n=2[/tex] ed ottengo:
[tex]T(2)=T(1)+ 2 \log 2 = (\frac{7}{2}) \leq c(2 \log 2)[/tex] che è vera per [tex]c\geq (\frac{7}{4})[/tex]
$7/2$ ma perchè?
fai così dimmi il ragionamente/sostituzione che fai...
Perciò possiamo dire che [tex]T(n)[/tex] appartiene a [tex]O(n \log n)[/tex] per qualunque [tex]n>2[/tex] e
[tex]c= (\frac{7}{4})[/tex].
te hai reso "vero" il caso base, ma il passo induttivo dove sta?
Ti mostro come si inizia, è una normale dimostrazione per induzione...
$T(n) = {(O(1) if n=1),(3T(n/4) + nlogn \ other):}$
Guess: $T(n) in O(nlogn)$
Proof: $\exists c > 0,\ m >= 0\ :\ T(n) <= cnlogn,\ \forall n >= m$
- [*:19oxr1m7]caso base: consiglio di trattarlo sempre alla fine, si evitano possibili inutili calcoli se l'ipotesi è sbagliata e dobbiamo modificarla.[/*:m:19oxr1m7]
[*:19oxr1m7]Ipotesi induttiva: $\forall m < n ^^ c>0\ :\ T(m) <= cmlogm$ [/*:m:19oxr1m7]
[*:19oxr1m7]Passo induttivo:
\[T(n) = 3T(n/4) + nlogn\]
\[\text{sostituzione dell’ipotesi induttiva}\]
\[\leq 3c\frac{n}4log(\frac{n}4) + nlogn\]
lascio continuare te
[/*:m:19oxr1m7]
[*:19oxr1m7]caso base: \(T(1) = 1 \not\leq c*1log1 = 0, \forall c > 0\)
lascio continuare te anche qua
[/*:m:19oxr1m7][/list:u:19oxr1m7]
Per prima cosa ti ringrazio per la tua pazienza, mi stai aiutando a capire i miei errori!
Ci riprovo..
Devo dimostare che:
[tex]T(n)\leq 3c(\frac{n}{4})\log (\frac{n}{4})+ cn \log n[/tex]
[tex]3c(\frac{n}{4})\log n - 3c(\frac{n}{4})\log 4 + cn \log n[/tex]
[tex](\frac{7}{4})cn \log n - 3c(\frac{n}{4})\log 4[/tex]
[tex](\frac{7}{4})cn \log n - 2(\frac{3}{4})cn[/tex]
[tex]\frac{7}{4}cn \log n - \frac{3}{2} cn[/tex]
A questo punto, penso(a meno che non ho sbagliato di nuovo), possiamo concludere che la soluzione è [tex]O(n \log n)[/tex].
Il caso base l'hai scritto tu, io adesso continuo:
[tex]T(2)=T(1)+ 2\log 2=3 \leq c(2\log 2)[/tex] che è vera per [tex]c=(\frac{3}{2\log 2})=\frac{3}{2}[/tex]
Perciò possiamo dire che [tex]T(n)[/tex] appartiene a [tex]O(n \log n)[/tex] per qualunque [tex]n>2[/tex] e [tex]c=\frac{3}{2}[/tex].
Adesso come va?
Ci riprovo..
Devo dimostare che:
[tex]T(n)\leq 3c(\frac{n}{4})\log (\frac{n}{4})+ cn \log n[/tex]
[tex]3c(\frac{n}{4})\log n - 3c(\frac{n}{4})\log 4 + cn \log n[/tex]
[tex](\frac{7}{4})cn \log n - 3c(\frac{n}{4})\log 4[/tex]
[tex](\frac{7}{4})cn \log n - 2(\frac{3}{4})cn[/tex]
[tex]\frac{7}{4}cn \log n - \frac{3}{2} cn[/tex]
A questo punto, penso(a meno che non ho sbagliato di nuovo), possiamo concludere che la soluzione è [tex]O(n \log n)[/tex].
Il caso base l'hai scritto tu, io adesso continuo:
[tex]T(2)=T(1)+ 2\log 2=3 \leq c(2\log 2)[/tex] che è vera per [tex]c=(\frac{3}{2\log 2})=\frac{3}{2}[/tex]
Perciò possiamo dire che [tex]T(n)[/tex] appartiene a [tex]O(n \log n)[/tex] per qualunque [tex]n>2[/tex] e [tex]c=\frac{3}{2}[/tex].
Adesso come va?
"krak":
Per prima cosa ti ringrazio per la tua pazienza, mi stai aiutando a capire i miei errori!
Ci riprovo..
Devo dimostare che:
[tex]T(n)\leq 3c(\frac{n}{4})\log (\frac{n}{4})+ cn \log n[/tex]
[tex]3c(\frac{n}{4})\log n - 3c(\frac{n}{4})\log 4 + cn \log n[/tex]
[tex](\frac{7}{4})cn \log n - 3c(\frac{n}{4})\log 4[/tex]
[tex](\frac{7}{4})cn \log n - 2(\frac{3}{4})cn[/tex]
[tex]\frac{7}{4}cn \log n - \frac{3}{2} cn[/tex]
A questo punto, penso(a meno che non ho sbagliato di nuovo), possiamo concludere che la soluzione è [tex]O(n \log n)[/tex].
ti direi che sono ok i concetti. Ma ho sbagliato a consigliarti questa ricorrenza, ho visto solo ora che può essere sbagliata la soluzione ($O(nlogn)$) oppure ci sono alcuni passaggi non troppo banali per dimostrare effettivamente l'ipotesi. Ti scriverò una soluzione, almeno a quella a cui ho pensato. L'esercizio mi sembrava facile.
Se vedi, facendo delle maggiorazioni, si può subito smentire l'ipotesi:
[tex]3c(\frac{n}{4})(\log n - \log 4) + n \log n <= 3c(\frac{n}{4})\log n + n \log n = 7c(\frac{n}{4})\log n \not\leq cnlogn[/tex]
cadendo in un vicolo cieco. Devo rivedermela quando ho più tempo.
Il caso base l'hai scritto tu, io adesso continuo:
[tex]T(2)=T(1)+ 2\log 2=3 \leq c(2\log 2)[/tex] che è vera per [tex]c=(\frac{3}{2\log 2})=\frac{3}{2}[/tex]
bhe questo mi pare ok
Comunque mettendo da parte questo esercizio in particolare, più che altro volevo sapere se il modo di procedere era giusto, e cioè:
1) Ipotizzo una soluzione alla mia ricorrenza.
2) Dimostro, tramite induzione, se effettivamente l'ipotesi è corretta o meno.
3) Trovo una [tex]m[/tex] e una [tex]c[/tex] per i quali è verificata la soluzione.[/list:u:3mbd6vks]
Fatto questo ho concluso lo studio della mia ricorrenza.
E' corretto tutto ciò?
Grazie
3) Trovo una [tex]m[/tex] e una [tex]c[/tex] per i quali è verificata la soluzione.
Ho sbagliato è n invece di m.
3) Trovo una [tex]n[/tex] e una [tex]c[/tex] per i quali è verificata la soluzione.
"krak":
Comunque mettendo da parte questo esercizio in particolare, più che altro volevo sapere se il modo di procedere era giusto, e cioè:
1) Ipotizzo una soluzione alla mia ricorrenza.
L'ipotesi la puoi costruire con tutte le tecniche messe a disposizione dall'analisi degli algoritmi (dal metodo algebrico al Master Theorem)
2) Dimostro, tramite induzione, se effettivamente l'ipotesi è corretta o meno.
esatto (o se vuoi, chiamalo metodo della sostituzione).
3) Trovo una [tex]m[/tex] e una [tex]c[/tex] per i quali è verificata la soluzione.[/list:u:1dn8ydo6]
questo in accordo con 2), è un'implicazione di verità. E' esatto dire che cerchi un $m$ (ricorda $...\ m>=0,\ ....\ \forall n>=m$)
ed infine (come ho consigliato per evitare calcoli possibilmente inutili) dimostrare il caso base.
Tutto questo sarebbe da fare sempre. Ma alle volte basta anche fermarsi al passo 1), per capire l'andamento di una ricorrenza e perciò la complessità di un algoritmo. La dimostrazione viene dopo.
Ho avuto qualche momento oggi, così ho riguardato la ricorrenza.
Devi dirlo, mi son perso in un bicchier d'acqua (come si dice), troppo lavoro dato dalla tesi
Sì, è vero che $T(n) in O(nlogn)$, io mi ero fissato nel voler dimostrare che $T(n) in O(nlog_4(n))$ cosa vera ma con risvolti formalmente non troppo semplici, per questo è nato il dubbio.
Perciò il tutto rimane con base generale ed anonima, rimane vero ciò che avevamo già scritto, ma con un passaggio semplice in più, manca semplicemente da definire la costante:
[tex]3c(\frac{n}{4})\log (\frac{n}4) + nlogn = 3c(\frac{n}{4})(\log n - \log 4) + n \log n \leq \frac{3}4cn\log n + n \log n \leq cnlogn[/tex] per $c>=4$.
Il caso base è valido per un qualche $n>=2$.
più semplice di così
Devi dirlo, mi son perso in un bicchier d'acqua (come si dice), troppo lavoro dato dalla tesi
Sì, è vero che $T(n) in O(nlogn)$, io mi ero fissato nel voler dimostrare che $T(n) in O(nlog_4(n))$ cosa vera ma con risvolti formalmente non troppo semplici, per questo è nato il dubbio.
Perciò il tutto rimane con base generale ed anonima, rimane vero ciò che avevamo già scritto, ma con un passaggio semplice in più, manca semplicemente da definire la costante:
[tex]3c(\frac{n}{4})\log (\frac{n}4) + nlogn = 3c(\frac{n}{4})(\log n - \log 4) + n \log n \leq \frac{3}4cn\log n + n \log n \leq cnlogn[/tex] per $c>=4$.
Il caso base è valido per un qualche $n>=2$.
più semplice di così
Data questa ricorrenza:
[tex]T(n)=9T(\frac{n}{3})+n^{2}\log n[/tex]
L'ho svolta applicando il secondo caso generalizzato del teorema Master, e ho dato come soluzione: [tex]\Theta (n^{2} \log ^{2}n)[/tex]
E' corretto?
[tex]T(n)=9T(\frac{n}{3})+n^{2}\log n[/tex]
L'ho svolta applicando il secondo caso generalizzato del teorema Master, e ho dato come soluzione: [tex]\Theta (n^{2} \log ^{2}n)[/tex]
E' corretto?
"krak":
Data questa ricorrenza:
[tex]T(n)=9T(\frac{n}{3})+n^{2}\log n[/tex]
L'ho svolta applicando il secondo caso generalizzato del teorema Master, e ho dato come soluzione: [tex]\Theta (n^{2} \log ^{2}n)[/tex]
E' corretto?
ok.
Avedo un dubbio e son andato a controllare su di un libro, hai utilizzato il metodo generale del caso 2, non lo ricordavo
Ho trovato questa discussione. Ho un problema con la prima ricorrenza postata $T(n/3)+T(n/4)+n$. Non ho trovato altri post a riguardo. Ho trovato tramite il metodo dell'albero che è $O(nlog_3n)$. Ho provato a verificarlo con il metodo di sostituzione ma trovo la costante c dipendente da $log_3n$. Come posso fare?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo