Equazione di ricorrenza
Innanzitutto dico che una ricorrenza è un equazione o disequazione che descrive una funzione in termini del suo valore con input più piccoli.
La mia ricorrenza è [tex]T(n)= T(n/4) + T(3n/4) +n[/tex].
Risolvendo col teorema della sostituzione penso sia una[tex]O(nlog n)[/tex]. Secondo voi è il bound più stretto???Oppure potrebbe essere una [tex]O(nloglogn)[/tex] o una [tex]O(n^2)[/tex]
La mia ricorrenza è [tex]T(n)= T(n/4) + T(3n/4) +n[/tex].
Risolvendo col teorema della sostituzione penso sia una[tex]O(nlog n)[/tex]. Secondo voi è il bound più stretto???Oppure potrebbe essere una [tex]O(nloglogn)[/tex] o una [tex]O(n^2)[/tex]
Risposte
la complessità più stretta è $O(nlog_{4/3}(n))$ che in pratica si generalizza con quella che hai trovato $O(nlog(n))$.
perchè pensi sia $O(nlog(log(n)))$? Ovviamente $O(n^2)$ è quadratica e non è sicuramente più stretta di $O(nlogn)$.
perchè pensi sia $O(nlog(log(n)))$? Ovviamente $O(n^2)$ è quadratica e non è sicuramente più stretta di $O(nlogn)$.
Ciao scusa...sono i primi esercizi che faccio con le ricorrenze...mi dici come sei arrivato a [tex]nlog4/3 n[/tex].
Io ho utilizzato il metodo della sostituzione e ho provato(tralasciando il caso base) che ci fosse un k=n tale che [tex]T(k)<= c(k/4)log (k/4)+ c(3k/4)log (3k/4)+k[/tex]....Tu hai utilizzato l'albero di ricorsione vero??
Mi potresti anche spiegare come lo hai fatto??
Te lo giuro non lo riesco proprio a capire....
Io ho utilizzato il metodo della sostituzione e ho provato(tralasciando il caso base) che ci fosse un k=n tale che [tex]T(k)<= c(k/4)log (k/4)+ c(3k/4)log (3k/4)+k[/tex]....Tu hai utilizzato l'albero di ricorsione vero??
Mi potresti anche spiegare come lo hai fatto??
Te lo giuro non lo riesco proprio a capire....
Guarda che il tuo metodo è ben corretto. Il metodo della sostituzione è di fatto la dimostrare formalmente che tale ricorrenza ha tal complessità e più di questo non serve altro, basta che fissi una costante. Se vuoi mostra i passaggi e ti si dice se ci sono problemi "formali"...
Ni, la complessità l'ho trovata ad occhio...perchè conosco quale è la soluzione di tali ricorrenze. Ma in pratica la puoi trovare con l'albero o per iterazione.
Ma in questo caso, la generalizzazione a loglineare è la soluzione corretta, perchè se ti basi sull'albero vedi che non è un albero completo e non ha senso scrivere una complessità stretta ma solo accennarla.
Tu hai utilizzato l'albero di ricorsione vero??
Ni, la complessità l'ho trovata ad occhio...perchè conosco quale è la soluzione di tali ricorrenze. Ma in pratica la puoi trovare con l'albero o per iterazione.
Ma in questo caso, la generalizzazione a loglineare è la soluzione corretta, perchè se ti basi sull'albero vedi che non è un albero completo e non ha senso scrivere una complessità stretta ma solo accennarla.
"hamming_burst":
Guarda che il tuo metodo è ben corretto. Il metodo della sostituzione è di fatto la dimostrare formalmente che tale ricorrenza ha tal complessità e più di questo non serve altro, basta che fissi una costante. Se vuoi mostra i passaggi e ti si dice se ci sono problemi "formali"...
Tu hai utilizzato l'albero di ricorsione vero??
Ni, la complessità l'ho trovata ad occhio...perchè conosco quale è la soluzione di tali ricorrenze. Ma in pratica la puoi trovare con l'albero o per iterazione.
Ma in questo caso, la generalizzazione a loglineare è la soluzione corretta, perchè se ti basi sull'albero vedi che non è un albero completo e non ha senso scrivere una complessità stretta ma solo accennarla.
Thanks, invece per [tex]8T(n/2) + n^2logn[/tex] potrebbe essere [tex]O(n^2logn)[/tex] ??
"peppe89ct":
[tex]8T(n/2) + n^2logn[/tex] potrebbe essere [tex]O(n^2logn)[/tex] ??
basta che provi ad utilizzare la sostituzione come hai fatto precedentemente. Ipotizzando che sia $log_2$:
\[8c(\frac{n}2)^2\log_2(\frac{n}2) + n^2\log_2(n) = 2cn^2\log_2(n) + n^2\log_2(n) =\]
\[= (2c + 1)n^2\log_2(n) \nleq cn^2\log_2(n) \Longrightarrow \nexists\ c\]
quindi tale complessità non funziona.
Prova ad utilizzare il Master, anche se non mi sembra si possa dimostrare una limitazione superiore in modo esatto.
[size=85]ATTENZIONE:[/size]
c'è un errore di calcolo nella versione sopra riportata.
"hamming_burst":
[quote="peppe89ct"][tex]8T(n/2) + n^2logn[/tex] potrebbe essere [tex]O(n^2logn)[/tex] ??
basta che provi ad utilizzare la sostituzione come hai fatto precedentemente. Ipotizzando che sia $log_2$:
\[8c(\frac{n}2)^2\log_2(\frac{n}2) + n^2\log_2(n) = 2cn^2\log_2(n) + n^2\log_2(n) =\]
\[= (2c + 1)n^2\log_2(n) \nleq cn^2\log_2(n) \Longrightarrow \nexists\ c\]
quindi tale complessità non funziona.
Prova ad utilizzare il Master, anche se non mi sembra si possa dimostrare una limitazione superiore in modo esatto.[/quote]
Utilizzando il teorema Master ho a=8 b=2 e la funzione [tex]n^{log_2(8)}[/tex] è polinomialmente più grande(dato che epsilon è [tex]3- 2logn[/tex] ;quindi asintoticamente più grande) di una [tex]O(n^2logn)[/tex] allora per il caso uno ho una [tex]theta (n^{2}logn)[/tex].....Giusto??
La dimostrazione per $O(n^2log(n))$ ho notato non essere corretta, per un errore di calcolo.
Questa sotto dovrebbe essere più accettabile:
\[8c(\frac{n}2)^2\log_2(\frac{n}2) + n^2\log_2(n) = 2cn^2(\log_2(n) - 1) + n^2\log_2(n) =\]
\[= 2cn^2\log_2(n) - 2cn^2 + n^2\log_2(n) = \]
\[ = (2c + 1)n^2\log_2(n) - 2cn^2 <=^\mathbin{\color{red}{1}} (2c + 1)n^2\log_2(n) \nleq cn^2\log_2(n)\]
\(\color{red}{1}:\) la sovrastima dovrebbe essere corretta in questo caso, perchè si sottrae un valore polinomialmente minore e non cambia la dimostrazione che tale complessità non è valida. Ma devo dire che non mi convince, ma ovviamente la complessità, dimostrazione o meno, $O(n^2log_2(n))$ non può essere valida perchè troppo stretta.
ok.
da dove esce questo calcolo?
No.
Come hai scritto $n^{log_2(8)} = n^3$
Allora ci domandiamo se $n^2log_2(n) \in^? O(n^{3-\epsilon})$
per scegliere $\epsilon$ dovremmo trovare un valore nell'intervallo $[0,1)$ che limiti il logaritmo (cioè il divario tra $n^2$ e $n^3$), ma questo non è possibile perchè non esiste un valore preciso (si può approfondire se interessa tale fatto (*)). Se ne potrebbe scegliere uno qualunque, ma questo non comporta una dimostrazione esatta, ma solo empirica.
Il mio spunto sull'utilizzo del Master era per farti ragionare su queste tecniche.
Comunque ho notato che questa ricorrenza è piuttosto difficile da dimostrarne formalmente la complessità.
Il metodo dell'albero riporta una complessità molto più alta del Master, devo pensarci...
___________________________
(*)
Vogliamo dimostrare che per qualsiasi costante $a,b,k > 0$ vale $\log^a(n^b) \in O(n^k)$.
\[\forall a,b,k > 0,\ \exists c>0,\ m \geq 0\ :\ \log^a(n^b) \leq cn^k,\ \forall n\geq m\]
edit:
corretto alcune frasi.
Questa sotto dovrebbe essere più accettabile:
\[8c(\frac{n}2)^2\log_2(\frac{n}2) + n^2\log_2(n) = 2cn^2(\log_2(n) - 1) + n^2\log_2(n) =\]
\[= 2cn^2\log_2(n) - 2cn^2 + n^2\log_2(n) = \]
\[ = (2c + 1)n^2\log_2(n) - 2cn^2 <=^\mathbin{\color{red}{1}} (2c + 1)n^2\log_2(n) \nleq cn^2\log_2(n)\]
\(\color{red}{1}:\) la sovrastima dovrebbe essere corretta in questo caso, perchè si sottrae un valore polinomialmente minore e non cambia la dimostrazione che tale complessità non è valida. Ma devo dire che non mi convince, ma ovviamente la complessità, dimostrazione o meno, $O(n^2log_2(n))$ non può essere valida perchè troppo stretta.
"peppe89ct":
Utilizzando il teorema Master ho a=8 b=2 e la funzione [tex]n^{log_2(8)}[/tex] è polinomialmente più grande
ok.
"peppe89ct":
(dato che epsilon è [tex]3- 2logn[/tex] ;
da dove esce questo calcolo?
quindi asintoticamente più grande) di una [tex]O(n^2logn)[/tex] allora per il caso uno ho una [tex]theta (n^{2}logn)[/tex].....Giusto??
No.
Come hai scritto $n^{log_2(8)} = n^3$
Allora ci domandiamo se $n^2log_2(n) \in^? O(n^{3-\epsilon})$
per scegliere $\epsilon$ dovremmo trovare un valore nell'intervallo $[0,1)$ che limiti il logaritmo (cioè il divario tra $n^2$ e $n^3$), ma questo non è possibile perchè non esiste un valore preciso (si può approfondire se interessa tale fatto (*)). Se ne potrebbe scegliere uno qualunque, ma questo non comporta una dimostrazione esatta, ma solo empirica.
Il mio spunto sull'utilizzo del Master era per farti ragionare su queste tecniche.
Comunque ho notato che questa ricorrenza è piuttosto difficile da dimostrarne formalmente la complessità.
Il metodo dell'albero riporta una complessità molto più alta del Master, devo pensarci...
___________________________
(*)
Vogliamo dimostrare che per qualsiasi costante $a,b,k > 0$ vale $\log^a(n^b) \in O(n^k)$.
\[\forall a,b,k > 0,\ \exists c>0,\ m \geq 0\ :\ \log^a(n^b) \leq cn^k,\ \forall n\geq m\]
edit:
corretto alcune frasi.
Quando ho fatto il teorema master ero mezzo ubriaco mi sa.....scusami...
Io devo scegliere tra queste 4 risposte.
[tex]T(n)= O(n^2 log n)[/tex]
[tex]T(n)= O(n^3 / log n)[/tex]
[tex]T(n)= O(n^3)[/tex]
[tex]T(n)= O(n^3 log n)[/tex]
Quale è secondo te??
Io ho già un idea e voglio sapere se è uguale alla tua
Io devo scegliere tra queste 4 risposte.
[tex]T(n)= O(n^2 log n)[/tex]
[tex]T(n)= O(n^3 / log n)[/tex]
[tex]T(n)= O(n^3)[/tex]
[tex]T(n)= O(n^3 log n)[/tex]
Quale è secondo te??
Io ho già un idea e voglio sapere se è uguale alla tua
\[ T(n) = 3\,n^3 - n^2\,( \log_2(n) + 2) \]
Infatti,
\[ 8\,T(n) + n^2\,\log_2(n) = 8\,( (3/8)\,n^3 - n^2\,( \log_2(n) - 1 + 2)/4 ) + n^2\,\log_2(n) = T(n) \]
Infatti,
\[ 8\,T(n) + n^2\,\log_2(n) = 8\,( (3/8)\,n^3 - n^2\,( \log_2(n) - 1 + 2)/4 ) + n^2\,\log_2(n) = T(n) \]
$n^2log_2(n) $
$8^1n^2/2^2(log_2(n)-1) = 2^1n^2(log_2(n)-1)$
$8^2n^2/2^3(log_2(n)-2) = 2^3n^2(log_2(n)-2)$
$8^3n^2/2^4(log_2(n)-3) = 2^5n^2(log_2(n)-3)$
$8^4n^2/2^5(log_2(n)-4) = 2^7n^2(log_2(n)-4)$
$...$
$8^i\n^2/2^(i+1)(log_2(n)-i) = 2^(2i+1)n^2(log_2(n)-(i+1))$
$...$
$n^2log_2(n) + sum_{k=0}^{log_2(n)-1} 2^(2k+1)n^2(log_2(n)-(k+1)) = ... $ wolfram
$...= (2 n^4 log(2))/(log(512)) +(n^2 log(n))/(log(2)) -(2 n^2 log(2))/(log(512))-(6 n^2 log(n))/(log(512)) \in O(n^4)$
le foglie $8^{\log_2(n)}T(1) \in O(n^3)$
quindi a me la complessità tramite l'albero diviene $O(n^4)$.
@apatriarca:
non capisco il tuo procedimento potresti mettere qualche nota in più... con che metodologia hai trovato $O(n^3)$? (tralasciando il master).
$8^1n^2/2^2(log_2(n)-1) = 2^1n^2(log_2(n)-1)$
$8^2n^2/2^3(log_2(n)-2) = 2^3n^2(log_2(n)-2)$
$8^3n^2/2^4(log_2(n)-3) = 2^5n^2(log_2(n)-3)$
$8^4n^2/2^5(log_2(n)-4) = 2^7n^2(log_2(n)-4)$
$...$
$8^i\n^2/2^(i+1)(log_2(n)-i) = 2^(2i+1)n^2(log_2(n)-(i+1))$
$...$
$n^2log_2(n) + sum_{k=0}^{log_2(n)-1} 2^(2k+1)n^2(log_2(n)-(k+1)) = ... $ wolfram
$...= (2 n^4 log(2))/(log(512)) +(n^2 log(n))/(log(2)) -(2 n^2 log(2))/(log(512))-(6 n^2 log(n))/(log(512)) \in O(n^4)$
le foglie $8^{\log_2(n)}T(1) \in O(n^3)$
quindi a me la complessità tramite l'albero diviene $O(n^4)$.
@apatriarca:
non capisco il tuo procedimento potresti mettere qualche nota in più... con che metodologia hai trovato $O(n^3)$? (tralasciando il master).
Quella funzione che ho scritto non è un calcolo approssimato, è la soluzione dell'equazione funzionale \( T(n) = 8\,T(n/2) + n^2\,\log_2(n) \) calcolata con Wolfram Alpha e semplificata. Tecnicamente invece di \( 3\,n^3 \) si potrebbe anche prendere \( 3\,c\,n^3/8 \) (se non ricordo male). Speravo di riuscire a trovare qualche metodo di risoluzione (che mi facesse venire in mente qualche idea insomma..) ma non ci sono riuscito (diciamo che non ho avuto neanche il tempo di pensarci più di tanto) e ho solo proposto la soluzione e la verifica che quella funzione rispetti effettivamente l'equazione funzionale.
Partiamo dalla nostra equazione di ricorrenza \( T(n) = 8\,T(n/2) + n^2\,\log_2(n) \) e la dividiamo per \( n^3 \) ottenendo
\[ S(n) = \frac{T(n)}{n^3} = \frac{2^3\,T(n/2)}{n^3} + \frac{\log_2(n)}{n} = S(n/2) + \frac{\log_2(n)}{n}. \]
Usando la tecnica del telescoping otteniamo quindi
\[ S(n) \sim \sum_{i=0}^{\log_2(n)} \frac{2^i\,\log_2(n/2^i)}{n} = \frac{1}{n} \, \sum_{i=0}^{\log_2(n)} (2^i\,\log_2(n) - i\,2^i) \]
Delle due serie (dimenticandoci per ora che dobbiamo anche dividere per \(n\)) ottenute la prima è geometrica e vale \( \log_2(n)\,(2\,n - 1). \) La seconda è la derivata di una serie geometrica e vale \( 1 + n. \) Ho usato le formule risolutive che si trovano per esempio su wikipedia. Mettendo tutto insieme si trova che
\[ S(n) \sim 2\,\log_2(n) - \frac{\log_2(n/2)}{n} + 1. \]
Per calcolare \( T(n) \) dovrebbe ora essere sufficiente moltiplicare per \(n^3\) ottenendo
\[ T(n) \sim 2\,n^3\,\log_2(n) + n^3 - n^2\,\log_2(n) + n^2 \]
Questo non sembra però in accordo con quanto fornito da Wolfram Alpha e verificato con il mio calcolo. Se riuscite a trovare un errore qui o nella mia verifica..
EDIT: Ovviamente questo risultato non verifica l'equazione di ricorrenza.
\[ S(n) = \frac{T(n)}{n^3} = \frac{2^3\,T(n/2)}{n^3} + \frac{\log_2(n)}{n} = S(n/2) + \frac{\log_2(n)}{n}. \]
Usando la tecnica del telescoping otteniamo quindi
\[ S(n) \sim \sum_{i=0}^{\log_2(n)} \frac{2^i\,\log_2(n/2^i)}{n} = \frac{1}{n} \, \sum_{i=0}^{\log_2(n)} (2^i\,\log_2(n) - i\,2^i) \]
Delle due serie (dimenticandoci per ora che dobbiamo anche dividere per \(n\)) ottenute la prima è geometrica e vale \( \log_2(n)\,(2\,n - 1). \) La seconda è la derivata di una serie geometrica e vale \( 1 + n. \) Ho usato le formule risolutive che si trovano per esempio su wikipedia. Mettendo tutto insieme si trova che
\[ S(n) \sim 2\,\log_2(n) - \frac{\log_2(n/2)}{n} + 1. \]
Per calcolare \( T(n) \) dovrebbe ora essere sufficiente moltiplicare per \(n^3\) ottenendo
\[ T(n) \sim 2\,n^3\,\log_2(n) + n^3 - n^2\,\log_2(n) + n^2 \]
Questo non sembra però in accordo con quanto fornito da Wolfram Alpha e verificato con il mio calcolo. Se riuscite a trovare un errore qui o nella mia verifica..
EDIT: Ovviamente questo risultato non verifica l'equazione di ricorrenza.
Ho svolto nuovi calcoli. Per prima cosa ho notato che se si scrive \( T(n) = c\,n^3 + f(n) \) si ottiene che
\[ c\,n^3 + f(n) = c\,n^3 + 8\,f(n/2) + n^2\,\log_2(n) \implies f(n) = 8\,f(n/2) + n^2\,\log_2(n). \]
Data cioè che una soluzione \(f(n)\) della equazione di ricorrenza si può aggiungere ad essa un qualsiasi multiplo di \(n^3\) ottenendo un'altra soluzione alla equazione di ricorrenza.
Ho fatto poi dei nuovi calcoli ottenendo dei risultati un po' diversi. Sia quindi \( S(n) = S(n/2) + \log_2(n)/n\) come prima e sostituiamo \( n = 2^m. \)
\[ U(m) = S(2^m) = S(2^m/2) + m/2^m = U(m-1) + m/2^m = \sum_{i=0}^{m} i/2^i = \frac{2\,n - \log_2(n) - 2}{n} \]
L'ultimo passaggio l'ho calcolato con Wolfram Alpha, ma è sufficiente usare la formula risolutiva per la serie derivata di quella geometrica. La formula in questo caso sembra quindi dare \( T(n) = (2 + c)\,n^3 - n^2\,(\log_2(n) + 2) \). E questa è decisamente in accordo con quanto calcolato nel mio primo post usando Wolfram Alpha per tutto. Sarei però a questo punto curioso di capire dove ho sbagliato nel mio precedente post in cui ho usato un metodo alla fine equivalente a questo ma senza sostituzione.
\[ c\,n^3 + f(n) = c\,n^3 + 8\,f(n/2) + n^2\,\log_2(n) \implies f(n) = 8\,f(n/2) + n^2\,\log_2(n). \]
Data cioè che una soluzione \(f(n)\) della equazione di ricorrenza si può aggiungere ad essa un qualsiasi multiplo di \(n^3\) ottenendo un'altra soluzione alla equazione di ricorrenza.
Ho fatto poi dei nuovi calcoli ottenendo dei risultati un po' diversi. Sia quindi \( S(n) = S(n/2) + \log_2(n)/n\) come prima e sostituiamo \( n = 2^m. \)
\[ U(m) = S(2^m) = S(2^m/2) + m/2^m = U(m-1) + m/2^m = \sum_{i=0}^{m} i/2^i = \frac{2\,n - \log_2(n) - 2}{n} \]
L'ultimo passaggio l'ho calcolato con Wolfram Alpha, ma è sufficiente usare la formula risolutiva per la serie derivata di quella geometrica. La formula in questo caso sembra quindi dare \( T(n) = (2 + c)\,n^3 - n^2\,(\log_2(n) + 2) \). E questa è decisamente in accordo con quanto calcolato nel mio primo post usando Wolfram Alpha per tutto. Sarei però a questo punto curioso di capire dove ho sbagliato nel mio precedente post in cui ho usato un metodo alla fine equivalente a questo ma senza sostituzione.
Simpatico procedimento, non ho guardato ancora tutti i dettagli, ma in pratica utilizzi il metodo della sostituzione di variabili, non ci avevo pensato.
Penso sia solo un errore di calcolo, vedi la seconda parte della sommatoria, a me non risultata $1+n$ (forse non ha sostituito $n$ di wiki con $log_2(n)$?). Difatti una volta calcolata la sommatoria e moltiplicando per $n^3$ il risultato combacia nei tuoi due metodi.
"apatriarca":
Sarei però a questo punto curioso di capire dove ho sbagliato nel mio precedente post in cui ho usato un metodo alla fine equivalente a questo ma senza sostituzione.
Penso sia solo un errore di calcolo, vedi la seconda parte della sommatoria, a me non risultata $1+n$ (forse non ha sostituito $n$ di wiki con $log_2(n)$?). Difatti una volta calcolata la sommatoria e moltiplicando per $n^3$ il risultato combacia nei tuoi due metodi.
In realtà, una volta che ho avuto un po' di tempo per pensarci con calma non è stato difficile risolvere questa equazione di ricorrenza. Ho in realtà applicato due metodi di applicazione abbastanza generale..
La scelta di dividere per \(n^3\) non è stata infatti "casuale". Supponiamo infatti di avere una equazione di ricorrenza del tipo \( T(n) = f(n)\,T\bigl(g(n)\bigr) + h(n). \) Se si cerca di svolgere i calcoli con questa equazione di ricorrenza si avranno tante parentesi annidate. Se invece dividiamo tutto per la funzione \( F(n) = \prod_{i \geq 0} f\bigl( g^i(n) \bigr) \). Otteniamo la nuova equazione di ricorrenza
\[ S(n) = \frac{T(n)}{F(n)} = \frac{f(n)\,T\bigl(g(n)\bigr)}{F(n)} + \frac{h(n)}{F(n)} = S\bigl(g(n)\bigr) + \frac{h(n)}{F(n)} = \sum_{i \geq 0} \frac{h\bigl(g^i(n)\bigr)}{F\bigl(g^i(n)\bigr)}. \]
Nel nostro caso avevamo che \( f(n) = 8 \) per ogni \(n > 0\) e quindi si ottiene che \( F(n) = 2^{3\,\log_2(n)} = n^3. \) Fosse stato \( 3 \) al posto di \( 8 \) avrei ad esempio diviso per \( 3^{\log_2(n)}. \) Ovviamente, in casi più complicati è necessario fare qualche calcolo in più e potrebbe essere complicato seguire questa strada. Ma dopotutto il master theorem esiste per qualche ragione..
L'altro metodo è stato quello della sostituzione e la sostituzione che ho fatto era abbastanza ovvia e standard.
La scelta di dividere per \(n^3\) non è stata infatti "casuale". Supponiamo infatti di avere una equazione di ricorrenza del tipo \( T(n) = f(n)\,T\bigl(g(n)\bigr) + h(n). \) Se si cerca di svolgere i calcoli con questa equazione di ricorrenza si avranno tante parentesi annidate. Se invece dividiamo tutto per la funzione \( F(n) = \prod_{i \geq 0} f\bigl( g^i(n) \bigr) \). Otteniamo la nuova equazione di ricorrenza
\[ S(n) = \frac{T(n)}{F(n)} = \frac{f(n)\,T\bigl(g(n)\bigr)}{F(n)} + \frac{h(n)}{F(n)} = S\bigl(g(n)\bigr) + \frac{h(n)}{F(n)} = \sum_{i \geq 0} \frac{h\bigl(g^i(n)\bigr)}{F\bigl(g^i(n)\bigr)}. \]
Nel nostro caso avevamo che \( f(n) = 8 \) per ogni \(n > 0\) e quindi si ottiene che \( F(n) = 2^{3\,\log_2(n)} = n^3. \) Fosse stato \( 3 \) al posto di \( 8 \) avrei ad esempio diviso per \( 3^{\log_2(n)}. \) Ovviamente, in casi più complicati è necessario fare qualche calcolo in più e potrebbe essere complicato seguire questa strada. Ma dopotutto il master theorem esiste per qualche ragione..
L'altro metodo è stato quello della sostituzione e la sostituzione che ho fatto era abbastanza ovvia e standard.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo