[Algoritmi]Svolgimento ricorrenza

[krak]

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.

[hamming_burst]

Ciao,
se noti questa ricorrenza a due punti di espansione \( \displaystyle {T}{\left(\frac{{n}}{{3}}\right)} \) e \( \displaystyle {T}{\left(\frac{{n}}{{4}}\right)} \); 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

[krak]

Ok..allora dò una occhiata ai post precedenti e in caso se ho problemi scrivo di nuovo. Grazie

[krak]

Ho svolto questa ricorrenza e chiedo il vostro aiuto per verificare se sia corretta o meno.
\( \displaystyle T(n)=T(\frac{n}{4})+T(\frac{3n}{4})+n \)

L'altezza dell'albero è \( \displaystyle h=\log \frac{4}{3} n \)
e quindi il numero delle foglie sarà: \( \displaystyle n^{\log \frac{4}{3} 2} \)

La struttura dell'albero è:
\( \displaystyle n \)
\( \displaystyle \frac{n}{4}+\frac{3n}{4}= n \)
\( \displaystyle \frac{n}{16}+\frac{3n}{16}+\frac{3n}{16}+\frac{9n}{16}= n \)

Quindi suppongo che la mia ricorrenza avrà soluzione \( \displaystyle O(n \log n) \)
Andrò a dimostrare che \( \displaystyle T(n)\leq dn \log n \)
d è una costante positiva.

\( \displaystyle T(n)\leq T(\frac{n}{4})+T(\frac{3n}{4})+n \)
\( \displaystyle \leq d(\frac{n}{4})\log (\frac{n}{4})+d(\frac{3n}{4})\log (\frac{3n}{4})+cn \)
\( \displaystyle \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 \)
\( \displaystyle = dn\log (n)-d(\frac{n}{4})\log (4)-d(\frac{3n}{4})\log (\frac{4}{3})+cn \)
\( \displaystyle = dn\log (n)-d(\frac{n}{4})\log (4)-d(\frac{3n}{4})\log (4)-d(\frac{3n}{4})\log (3)+ cn \)
\( \displaystyle = dn\log (n)-d(n)\log (4)-d(\frac{3n}{4})\log (3)+ cn \)
\( \displaystyle = dn\log (n)-dn(\log (4)-\frac{3}{4}\log (3))+ cn \)
\( \displaystyle \leq dn \log (n) \)

che è \( \displaystyle O(n \log n) \)

E' corretto lo svolgimento???
Grazie.

[hamming_burst]

Ciao,
il procedimento è corretto, ci sono delle piccole inesattezze formali, te le sottolineo

L'altezza dell'albero è \( \displaystyle h=\log \frac{4}{3} n \)

non è propriamente corretto parlare di altezza in questo caso, è meglio dire il più lungo cammino radice-foglia (perchè?) ha altezza \( \displaystyle {\log}_{{\frac{{4}}{{3}}}}{\left({n}\right)} \) (un punto che molti "sbagliano" nel capirlo, sai perchè ha la base invertita rispetto al fattore di ricorsione \( \displaystyle \frac{{3}}{{4}} \)?)

e quindi il numero delle foglie sarà: \( \displaystyle n^{\log \frac{4}{3} 2} \)

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 è:
\( \displaystyle n \)
\( \displaystyle \frac{n}{4}+\frac{3n}{4}= n \)
\( \displaystyle \frac{n}{16}+\frac{3n}{16}+\frac{3n}{16}+\frac{9n}{16}= n \)

Quindi suppongo che la mia ricorrenza avrà soluzione \( \displaystyle O(n \log n) \)

l'albero darà come soluzione la complessità superiore \( \displaystyle {O}{\left({n}{\log}_{{\frac{{4}}{{3}}}}{\left({n}\right)}\right)} \) ma che non ha significato se è stretto sulla ricorrenza, perciò è valido dire essere \( \displaystyle {O}{\left({n}{\log}_{{2}}{\left({n}\right)}\right)} \)

Andrò a dimostrare che \( \displaystyle T(n)\leq dn \log n \)
d è una costante positiva.

\( \displaystyle T(n)\leq T(\frac{n}{4})+T(\frac{3n}{4})+n \)
\( \displaystyle \leq d(\frac{n}{4})\log (\frac{n}{4})+d(\frac{3n}{4})\log (\frac{3n}{4})+cn \)
\( \displaystyle \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 \)
\( \displaystyle = dn\log (n)-d(\frac{n}{4})\log (4)-d(\frac{3n}{4})\log (\frac{4}{3})+cn \)
\( \displaystyle = dn\log (n)-d(\frac{n}{4})\log (4)-d(\frac{3n}{4})\log (4)-d(\frac{3n}{4})\log (3)+ cn \)
\( \displaystyle = dn\log (n)-d(n)\log (4)-d(\frac{3n}{4})\log (3)+ cn \)
\( \displaystyle = dn\log (n)-dn(\log (4)-\frac{3}{4}\log (3))+ cn \)
\( \displaystyle \leq dn \log (n) \)

che è \( \displaystyle O(n \log 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 \( \displaystyle {d} \) e \( \displaystyle {n} \) la tua ipotesi è vera? non lo dici.
I passaggi credo siano ok, io avrei utilizzato come ipotesi \( \displaystyle {d}{n}{\log}_{{2}}{\left({n}\right)} \) ma anche così potrebbe andare, saresti più preciso nelle costanti, una volta dimostrato per un qualche \( \displaystyle {d} \) va tutto bene il resto.
Una seconda cosa, non dovrebbe servire aggiungere una costante al fattore libero della ricorrenza è puro \( \displaystyle {n} \), non ha costanti nascoste se lo fosse ci sarebbe scritto \( \displaystyle {O}{\left({n}\right)} \).

[krak]

Ciao, grazie degli accorgimenti intanto.
Allora, prima di svolgere i calcoli della dimostrazione per induzione dirò per qualche \( \displaystyle d>0 \) .
Quando avrò fatto tutti i calcoli della dimostrazione, dirò che è vera per:
\( \displaystyle d\geq \frac{c}{\log (4)-(\frac{3}{4}\log 3)} \)
c è una costante maggiore di zero.

E' corretto? Non ho molta dimestichezza ancora

[hamming_burst]

Ciao, grazie degli accorgimenti intanto.
Allora, prima di svolgere i calcoli della dimostrazione per induzione dirò per qualche \( \displaystyle d>0 \) .
Quando avrò fatto tutti i calcoli della dimostrazione, dirò che è vera per:
\( \displaystyle d\geq \frac{c}{\log (4)-(\frac{3}{4}\log 3)} \)
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 \( \displaystyle {d} \) fissato, siamo una dimostrazione per induzione. Per essere pignoli c'è anche il caso base da inserire e il per quale \( \displaystyle {m}\ge{0} \) l'ipotesi è sempre vera.
Cmq anche se non inerisci una costante \( \displaystyle {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 \( \displaystyle {d}\ge\frac{{4}}{{5}} \) (per \( \displaystyle {O}{\left({n}{\log}_{{2}}{\left({n}\right)}\right)} \)).

[krak]

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 è:
\( \displaystyle T(n)= T(\frac{n}{4})+T(\frac{3n}{4})+n \)
Provo per \( \displaystyle n=1 \) ed ottengo:
\( \displaystyle T(1)=T(\frac{1}{4})+T(\frac{3}{4})+1 = 2 \leq O(1 \log 1) \) che è falsa!
Provo per \( \displaystyle n=2 \) ed ottengo:
\( \displaystyle T(2)=T(\frac{2}{4})+T(\frac{6}{4})+2 = 4 \leq O(2 \log 2) \) che è falsa!
Provo per \( \displaystyle n=3 \) ed ottengo:
\( \displaystyle T(3)=T(\frac{3}{4})+T(\frac{9}{4})+3 = 6 \leq O(3 \log 3) \) che è falsa!
Provo per \( \displaystyle n=4 \) ed ottengo:
\( \displaystyle T(4)=T(\frac{4}{4})+T(\frac{12}{4})+4 = 8 \leq O(4 \log 4) \) che è vera!

Quindi possiamo concludere che \( \displaystyle T(n)=O(n \log n) \) per qualunque \( \displaystyle n\geq 4 \) .

E' giusto?

[hamming_burst]

E' giusto?

mmm si e no...

bisogna fare attenzione, alle costanti e a scrivere il tutto correttamente.
Devi dire per quale \( \displaystyle {c} \) è vero il caso base.

Provo per \( \displaystyle n=1 \) ed ottengo:
\( \displaystyle T(1)=1 \not\leq c 1 \log 1 = 0 \) che è falsa!
Ricorda che di solito esiste un costo base nelle equazioni di ricorrenza, es: \( \displaystyle {O}{\left({1}\right)}{\quad\text{if}\quad}{n}={1} \)

Visto che il caso base non funziona ce lo scegliamo noi:

\( \displaystyle T(2)=T(1)+T(1)+2 = 4 \leq c(2 \log 2) \) che è vera per \( \displaystyle {c}\ge{2} \)

perciò possiamo dire che \( \displaystyle {T}{\left({n}\right)}\in{O}{\left({n}{\log}_{{2}}{\left({n}\right)}\right)}\forall{n}\gt{2}\wedge{c}={2} \)

PS: per il caso base si può continuare:
\( \displaystyle {T}{\left({3}\right)}={T}{\left({1}\right)}+{T}{\left({1}\right)}+{3}={5}\leq{c}{\left({3}{\log{{3}}}\right)}\to{c}\ge\frac{{{5}{\log{{\left({2}\right)}}}}}{{{3}{\log{{\left({3}\right)}}}}} \)
\( \displaystyle {T}{\left({4}\right)}={T}{\left({1}\right)}+{T}{\left({1}\right)}+{4}={6}\leq{c}{\left({4}{\log{{4}}}\right)}\to{c}\ge\frac{{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 \( \displaystyle {3}{T}{\left(\frac{{n}}{{4}}\right)}+{n}{\log{{\left({n}\right)}}}\in{O}{\left({n}{\log{{\left({n}\right)}}}\right)} \) (o se vuoi anche mi sembra essere \( \displaystyle \Theta{\left({n}{\log{{\left({n}\right)}}}\right)} \). Come prima \( \displaystyle {O}{\left({1}\right)} \) quando \( \displaystyle {n}={1} \).

[krak]

Emh..credo di aver capito.
Per sicurezza provo a svolgere quella dimostrazione che mi hai consigliato e in caso mi correggi =)