[Algoritmi]Svolgimento ricorrenza

[krak2]

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]

Non ho trovato altri post a riguardo.

sicuro? cerca meglio ma nn ci son problemi se hai dubbi basta scrivere..

cmq che metodologia hai adottato per trovare questa complessità? hai maggiorato come qui?

[mosca9]

Ho visto che un ramo procedeva più veloce dell'altro, dunque uno arriva primo al caso base dell'altro. Quello che arriva più tardi ha altezza $log_3n$. Avrò quindi dei livelli incompleti di costo massimo O(n) ciascuno e dunque ho $O(nlog_3n)$.

Ho poi applicato il metodo di sostituzione e (salto qualche passaggio) sono arrivato qui:
$T(n)<=cn((log_3n)/3-1/3+(log_3n)/4-log_3(4))+n<=cnlog_3n$
posso elimare n, ma ho c che dipende da $log_3n$ in ogni caso.

[hamming_burst]

"mosca9":Ho visto che un ramo procedeva più veloce dell'altro, dunque uno arriva primo al caso base dell'altro. Quello che arriva più tardi ha altezza $log_3n$. Avrò quindi dei livelli incompleti di costo massimo O(n) ciascuno e dunque ho $O(nlog_3n)$.

non puoi farlo in questo caso (leggi il link sul perchè), la costante $c$ di $O(n)$ è $0
fai un'analisi sui costi (es. anche qui)

1/3 + 1/4 = 0.58

1/3*3 + 1/3*4 + 1/4*3 + 1/4*4 = 0.34

1/3*3*3 + 1/3*3*4 + 1/3*4*3 + 1/3*4*4 +1/4*3*3 + 1/4*3*4 + 1/4*4*3 + 1/4*4*4 = 0.198

perciò la costante diminuisce della metà ad ogni livello.
anche se è vero la tua affermazione di "velocità" ed anche è pieno di buchi dopo il livello $log_4(n)$.

[mosca9]

A questo livello di particolari non lo abbiamo fatto. L'esercizio in effetti non chiedeva di verificarlo ma solo un limite superiore, l'ho provato io per vedere se l'ipotesi fatta era giusta. Dicendo che $O(nlog_3n)$ è limite superiore sovrastimo ma può andare come risposta?

[hamming_burst]

"mosca9":A questo livello di particolari non lo abbiamo fatto. L'esercizio in effetti non chiedeva di verificarlo ma solo un limite superiore, l'ho provato io per vedere se l'ipotesi fatta era giusta. Dicendo che $O(nlog_3n)$ è limite superiore sovrastimo ma può andare come risposta?

ma si dai alla fine la mia è pignoleria. Stimare ad $1$ poi in questo caso può andare.
Maggiorando o minorando comunque si trovano questi risultati continuando con i conti sopra fino al livello 3 dell'albero:

il caso precedente: 1.118
utilizzando sommatorie nella fase successiva dell'albero (es. $sum_{i=1}^{3} (1/3)^i + (1/4)^i$).

sommando solo i rami 1/3 e 1/4 (quelli esterni): 0.809
1/3 e 1/3 : 1.407
1/4 e 1/4 : 0.875
1/4 e 2/4 : 1.203

l'ultimo sarebbe quello che si avvicina di più per calcolare una limitazione più stretta con due semplici sommatorie.
Questi sono i tipi di analisi che si fanno per restringere maggiormente una complessità, ma anche considerare come costante $1$ dire che in questo caso va bene.

Perciò la tua stima è ok.

[hamming_burst]

per i vari passaggi

"mosca9":Ho poi applicato il metodo di sostituzione e (salto qualche passaggio) sono arrivato qui:
$T(n)<=cn((log_3n)/3-1/3+(log_3n)/4-log_3(4))+n<=cnlog_3n$
posso elimare n, ma ho c che dipende da $log_3n$ in ogni caso.

sbagli nel raggruppare devi tenere sempre presente la forma da dimostrare.

$T(n/3)+T(n/4) + n <= cn/3log_3(n/3) + cn/4log_3(n/4) + n = cn/3(log_3(n) - 1) + cn/4(log_3(n) - log_3(4)) + n =$

$= cn/3log_3(n) - cn/3 + cn/4\log_3(n) - {\log_3(4)}/4cn + n = (1/3+1/4)cn\log_3(n) - (1/3+{\log_3(4)}/4)cn + n \approx $

$\approx 7/12cn\log_3(n) - (193/300)cn + n <= cn\log_3(n)$ che è vero per $c>= 50/53$ (approssimazioni fatte con wolfram...)

[mosca9]

Non capisco l'ultimo passaggio con la maggiorazione.

[hamming_burst]

"mosca9":Non capisco l'ultimo passaggio con la maggiorazione.

quale la costante?

[mosca9]

Si. La hai trovata con matlab?

[hamming_burst]

"mosca9":Si. La hai trovata con matlab?

ok.
per far veloce ho utilizzato wolfram-alpha, ma non è propriamente corretto (ci posson esser valori che sfasano l'analisi).
Considera che quell'ultimo passaggio serve per fissare un "limite inferiore" sulla validità della disuguaglianza per la costante $c$.

A mano è alquanto veloce, e si può fare un'analisi un po' più accurata, se vuoi spezza le varie parti:

$- (193/300)cn + n$ è preferibile pensare che deve annullarsi. Perciò bisogna prendi $c=300/193$

$7/12cn\log_3(n) <= cn\log_3(n)$ è vero per $c>=12/7$

ora avresti due costanti $12/7$ e $300/193$ prendi la più grande cioè $12/7$ ed hai finito (se vuoi ci sarebbe un fattore di sottrazione di $-cn$ se $c>300/193$ ma sono fregature dovute alla non perfetta accuratezza della limitazione).