Ricorrenza
Salve,
avendo questa ricorrenza:
$T(n) = {(1,if n=1),(4T(\sqrt(n)) + log_{2}^{2}(n),\text{other}):}$
di primo colpo, ho cercato cercato di risolverla con il metodo dell'albero, che è il metodo che più preferisco. Se arrivo ad un punto dove non si trova una soluzione subito, cambio ovviamente metodo.
Però in questo caso, vorrei chiedervi se è possibile arrivare ad una soluzione in qualche modo.
io sono arrivato fin qua, ipotizzando che $n in NN$ e $sqrt(n) in NN$:
$log_{2}^{2}(n) -> 4log_{2}^{2}(\sqrt(n)) -> 4^2log_{2}^{2}(n^{1/2^2}) -> ... -> 4^ilog_{2}^{2}(n^(1/2^i))=4^i(1/2^i)^2log_{2}^{2}(n)= log_{2}^{2}(n)-> ... -> ?$ (*)
ora arrivo ad un punto cieco, di solito con il metodo dell'albero si cerca di raggiungere un punto dove si cerca di equagliare $n$ con la base della ricorsione che è $1$. Perciò si cerca di "annullare" il valore genrico $i$ di $n^(1/2^i)=1$.
Io avevo pensato a $i = log_{2}(n)$ per arrivare alla situazione $n^(1/n) = root(n)(n)$. Io erroneamente ho pensato alla successione $root(n)(n)$ che messa al limite $+oo$ da quello che cercavo $1$. Perciò ho chiesto in Analisi qui se ci fosse un qualche $i$ che uguagliasse $n=1$, cosa che ovviamente non c'è.
Ora visto che sono arrivato ad un punto cieco, e si dovrebbero sommare i nodi con la sommatoria:
$sum_{i=0}^{?} 4^i(1/2^i)^2log_{2}^{2}(n) = sum_{i=0}^{?} log_{2}^{2}(n)$ che è una somma, senza parametro $i$, bisogna capire fino a quando esiste la somma (*), cioè la profondità dell'albero.
Io ho paura sia una somma infinita...con le ovvie conseguenze.
Avete idee?
Ringrazio
avendo questa ricorrenza:
$T(n) = {(1,if n=1),(4T(\sqrt(n)) + log_{2}^{2}(n),\text{other}):}$
di primo colpo, ho cercato cercato di risolverla con il metodo dell'albero, che è il metodo che più preferisco. Se arrivo ad un punto dove non si trova una soluzione subito, cambio ovviamente metodo.
Però in questo caso, vorrei chiedervi se è possibile arrivare ad una soluzione in qualche modo.
io sono arrivato fin qua, ipotizzando che $n in NN$ e $sqrt(n) in NN$:
$log_{2}^{2}(n) -> 4log_{2}^{2}(\sqrt(n)) -> 4^2log_{2}^{2}(n^{1/2^2}) -> ... -> 4^ilog_{2}^{2}(n^(1/2^i))=4^i(1/2^i)^2log_{2}^{2}(n)= log_{2}^{2}(n)-> ... -> ?$ (*)
ora arrivo ad un punto cieco, di solito con il metodo dell'albero si cerca di raggiungere un punto dove si cerca di equagliare $n$ con la base della ricorsione che è $1$. Perciò si cerca di "annullare" il valore genrico $i$ di $n^(1/2^i)=1$.
Io avevo pensato a $i = log_{2}(n)$ per arrivare alla situazione $n^(1/n) = root(n)(n)$. Io erroneamente ho pensato alla successione $root(n)(n)$ che messa al limite $+oo$ da quello che cercavo $1$. Perciò ho chiesto in Analisi qui se ci fosse un qualche $i$ che uguagliasse $n=1$, cosa che ovviamente non c'è.
Ora visto che sono arrivato ad un punto cieco, e si dovrebbero sommare i nodi con la sommatoria:
$sum_{i=0}^{?} 4^i(1/2^i)^2log_{2}^{2}(n) = sum_{i=0}^{?} log_{2}^{2}(n)$ che è una somma, senza parametro $i$, bisogna capire fino a quando esiste la somma (*), cioè la profondità dell'albero.
Io ho paura sia una somma infinita...con le ovvie conseguenze.
Avete idee?
Ringrazio
Risposte
Immagino in effetti che si debba cercare di usare qualche proprietà dei logaritmi. In questo caso hai:
\[ T(n) = \log^2 n + 4 ( \log^2 \sqrt n + 4 (...) ) \]
Possiamo per prima cosa cercare di tirare fuori la radice dal logaritmo ricordandoci che il logaritmo è al quadrato. Siccome gli esponenti di \(n\) seguono la successione \( 1, 1/2, 1/4, \dots 1/2^i \) e i coefficienti davanti al logaritmo seguono invece la successione \(1, 4, 16, \dots 2^{2i} \), otteniamo
\[ T(n) = F(n) \log^2 n + 2^{2F(n)} \]
dove \( F(n) \) è il numero di iterazioni di \( n \to \left\lfloor \sqrt n \right\rfloor \) necessarie prima di ottenere \( 1 \).
A questo punto non rimane che stimare questo \( F(n) \). Iniziamo per prima cosa a notare che \( \left\lfloor \sqrt n \right\rfloor \le \left\lfloor \frac{n}{2} \right\rfloor \) per ogni \(n > 1\)*. Quindi \( F(n) < \log n \) per \( n \) sufficientemente grande. Ma in realtà, \( F(n) \) cresce più lentamente di \( \log n \). Certamente non è una somma infinita..
Supponiamo ora che \( n = r^{2^m} \) dove \( r \in [1, 2] \subset \mathbb R\) ed \( m \in \mathbb Z\). Supponiamo che \( m \) sia l'intero più piccolo per cui esista un \( r \) con tale proprietà. È abbastanza ovvio che \( F(n) <= m \). Vediamo quindi come calcolare questo \(m\). Fissiamo quindi un \(m_0\) e consideriamo il limite \(M = 2^{2^{m_0}}\). Per ogni \( n \ge M \), deve essere \( n^{1/2^{m_0}} \ge 2 \) e per ogni \( n < M \) avremo invece che \( n^{1/2^{m_0}} < 2 \) perché \( *^{1/2^{m_0}} \) è monotona. Abbiamo quindi ottenuto che \( F(n) \le m_0 \) se e solo se \( n < 2^{2^{m_0}} \). Se non ho quindi preso un abbaglio dovrebbe allora valere che \( F(n) \in O(\log \log n)\) per cui valere la seguente
\[ T(n) < (C \log \log n + 1)\log^2 n. \]
Per cui alla fine del discorso dovrebbe valere qualcosa tipo \( T(n) \in \log (\log n) \log^2 n \).
Sconvolgente se è così.. Dacci un occhiata che tutto questo non fa esattamente parte del mio settore di studio e sono abbastanza stupito di essere arrivato a questo punto.
* Direi che non c'è molto da discutere. Si ha infatti \( \sqrt n = \frac{n}{\sqrt n} < \frac{n}{2} \) per ogni \( n > 4 \) come è facile osservare. Inoltre \( \left\lfloor \sqrt n \right\rfloor = \left\lfloor \frac{n}{2} \right\rfloor \) per i valori di \(2\), \(3\) e \(4\).
\[ T(n) = \log^2 n + 4 ( \log^2 \sqrt n + 4 (...) ) \]
Possiamo per prima cosa cercare di tirare fuori la radice dal logaritmo ricordandoci che il logaritmo è al quadrato. Siccome gli esponenti di \(n\) seguono la successione \( 1, 1/2, 1/4, \dots 1/2^i \) e i coefficienti davanti al logaritmo seguono invece la successione \(1, 4, 16, \dots 2^{2i} \), otteniamo
\[ T(n) = F(n) \log^2 n + 2^{2F(n)} \]
dove \( F(n) \) è il numero di iterazioni di \( n \to \left\lfloor \sqrt n \right\rfloor \) necessarie prima di ottenere \( 1 \).
A questo punto non rimane che stimare questo \( F(n) \). Iniziamo per prima cosa a notare che \( \left\lfloor \sqrt n \right\rfloor \le \left\lfloor \frac{n}{2} \right\rfloor \) per ogni \(n > 1\)*. Quindi \( F(n) < \log n \) per \( n \) sufficientemente grande. Ma in realtà, \( F(n) \) cresce più lentamente di \( \log n \). Certamente non è una somma infinita..
Supponiamo ora che \( n = r^{2^m} \) dove \( r \in [1, 2] \subset \mathbb R\) ed \( m \in \mathbb Z\). Supponiamo che \( m \) sia l'intero più piccolo per cui esista un \( r \) con tale proprietà. È abbastanza ovvio che \( F(n) <= m \). Vediamo quindi come calcolare questo \(m\). Fissiamo quindi un \(m_0\) e consideriamo il limite \(M = 2^{2^{m_0}}\). Per ogni \( n \ge M \), deve essere \( n^{1/2^{m_0}} \ge 2 \) e per ogni \( n < M \) avremo invece che \( n^{1/2^{m_0}} < 2 \) perché \( *^{1/2^{m_0}} \) è monotona. Abbiamo quindi ottenuto che \( F(n) \le m_0 \) se e solo se \( n < 2^{2^{m_0}} \). Se non ho quindi preso un abbaglio dovrebbe allora valere che \( F(n) \in O(\log \log n)\) per cui valere la seguente
\[ T(n) < (C \log \log n + 1)\log^2 n. \]
Per cui alla fine del discorso dovrebbe valere qualcosa tipo \( T(n) \in \log (\log n) \log^2 n \).
Sconvolgente se è così.. Dacci un occhiata che tutto questo non fa esattamente parte del mio settore di studio e sono abbastanza stupito di essere arrivato a questo punto.* Direi che non c'è molto da discutere. Si ha infatti \( \sqrt n = \frac{n}{\sqrt n} < \frac{n}{2} \) per ogni \( n > 4 \) come è facile osservare. Inoltre \( \left\lfloor \sqrt n \right\rfloor = \left\lfloor \frac{n}{2} \right\rfloor \) per i valori di \(2\), \(3\) e \(4\).
ti ringrazio molto dell'interesse
fin qui ok.
perchè lo limiti a $log(n)$, mi manca un passaggio. Lo so spiegare se riferito ad un albero binario completo, essendo i nodi interni $\lfloor n/2 \rfloor$ ma algebricamente non so. Stesso principio penso.
uh interessante. Non sapevo che $sqrt(n) = n/sqrt(n)$ bello bello questo trucco
fondamentale, perchè hai scelto di utilizzare l'intervallo $[1,2] in RR$? Oltre che la restrizione ad utilizzare solo la parte intera, in questo caso non serve più.
se non ho compreso in modo sbagliato, $M$ è l'ultimo valore di $n$ valido dell'equazione. Perciò te lo limiti con l'ipotesi che hai fatto, ok ci sono
qua no, mi manca un passaggio.
non meravigliarti della complessità è esattamente così, bella è vista con questo metodo
Utilizzando sostituzione di variabili, si arriva allo stesso risultato in 2 passaggi, ma volevo proprio risolverlo in questo modo, ti ringrazio. Se mi spieghi quei due passaggi sopra dovrei essere a posto
"apatriarca":
Immagino in effetti che si debba cercare di usare qualche proprietà dei logaritmi. In questo caso hai:
\[ T(n) = \log^2 n + 4 ( \log^2 \sqrt n + 4 (...) ) \]
Possiamo per prima cosa cercare di tirare fuori la radice dal logaritmo ricordandoci che il logaritmo è al quadrato. Siccome gli esponenti di \(n\) seguono la successione \( 1, 1/2, 1/4, \dots 1/2^i \) e i coefficienti davanti al logaritmo seguono invece la successione \(1, 4, 16, \dots 2^{2i} \), otteniamo
\[ T(n) = F(n) \log^2 n + 2^{2F(n)} \]
dove \( F(n) \) è il numero di iterazioni di \( n \to \left\lfloor \sqrt n \right\rfloor \) necessarie prima di ottenere \( 1 \).
fin qui ok.
A questo punto non rimane che stimare questo \( F(n) \). Iniziamo per prima cosa a notare che \( \left\lfloor \sqrt n \right\rfloor \le \left\lfloor \frac{n}{2} \right\rfloor \) per ogni \(n > 1\)*. Quindi \( F(n) < \log n \) per \( n \) sufficientemente grande. Ma in realtà, \( F(n) \) cresce più lentamente di \( \log n \). Certamente non è una somma infinita..
perchè lo limiti a $log(n)$, mi manca un passaggio. Lo so spiegare se riferito ad un albero binario completo, essendo i nodi interni $\lfloor n/2 \rfloor$ ma algebricamente non so. Stesso principio penso.
* Direi che non c'è molto da discutere. Si ha infatti \( \sqrt n = \frac{n}{\sqrt n} < \frac{n}{2} \) per ogni \( n > 4 \) come è facile osservare. Inoltre \( \left\lfloor \sqrt n \right\rfloor = \left\lfloor \frac{n}{2} \right\rfloor \) per i valori di \(2\), \(3\) e \(4\).
uh interessante. Non sapevo che $sqrt(n) = n/sqrt(n)$ bello bello questo trucco
Supponiamo ora che \( n = r^{2^m} \) dove \( r \in [1, 2] \subset \mathbb R\) ed \( m \in \mathbb Z\).
fondamentale, perchè hai scelto di utilizzare l'intervallo $[1,2] in RR$? Oltre che la restrizione ad utilizzare solo la parte intera, in questo caso non serve più.
Supponiamo ora che \( n = r^{2^m} \) dove \( r \in [1, 2] \subset \mathbb R\) ed \( m \in \mathbb Z\). Supponiamo che \( m \) sia l'intero più piccolo per cui esista un \( r \) con tale proprietà. È abbastanza ovvio che \( F(n) <= m \). Vediamo quindi come calcolare questo \(m\). Fissiamo quindi un \(m_0\) e consideriamo il limite \(M = 2^{2^{m_0}}\). Per ogni \( n \ge M \), deve essere \( n^{1/2^{m_0}} \ge 2 \) e per ogni \( n < M \) avremo invece che \( n^{1/2^{m_0}} < 2 \) perché \( *^{1/2^{m_0}} \) è monotona. Abbiamo quindi ottenuto che \( F(n) \le m_0 \) se e solo se \( n < 2^{2^{m_0}} \).
se non ho compreso in modo sbagliato, $M$ è l'ultimo valore di $n$ valido dell'equazione. Perciò te lo limiti con l'ipotesi che hai fatto, ok ci sono
Se non ho quindi preso un abbaglio dovrebbe allora valere che \( F(n) \in O(\log \log n)\)
qua no, mi manca un passaggio.
per cui valere la seguente
\[ T(n) < (C \log \log n + 1)\log^2 n. \]
Per cui alla fine del discorso dovrebbe valere qualcosa tipo \( T(n) \in \log (\log n) \log^2 n \).
non meravigliarti della complessità è esattamente così, bella è vista con questo metodo
Utilizzando sostituzione di variabili, si arriva allo stesso risultato in 2 passaggi, ma volevo proprio risolverlo in questo modo, ti ringrazio. Se mi spieghi quei due passaggi sopra dovrei essere a posto
Quel capoverso è inutile. Volevo solo farti vedere che il valore di \(F(n)\) era evidentemente molto piccolo e che soprattutto terminava perché c'era il floor...
La ragione per cui prendo \(r \in [1,2]\) è che se \( r \in [1, 2] \), \( \lfloor r \rfloor = 1 \). Per cui se \( n^{1/2^{m}} = r \) allora \( \left\lfloor n^{1/2^{m}} \right\rfloor = \lfloor r \rfloor = 1 \). Quando si raggiunge quindi un valore di \( n^{1/2^{i}} \) in questo intervallo si ferma l'iterazione.
Aggiungo qualche commento che avevo un po' tralasciato e cerco di mettere un po' di chiarezza su alcuni passaggi.
Sia \(n\) un numero intero fissato. La funzione reale \( x \mapsto n^{1/2^x} \) è strettamente decrescente in \( x > 0 \) (il resto dell'asse reale non ci interessa per questa discussione) e tende \(1\) quando \(x\) tende a \(\infty\). Ci sarà quindi un valore di \( x_0 \) per cui \( n^{1 / 2^{x_0}} = 2 \), \( n^{1/2^x} < 2 \) quando \( x > x_0 \) e \( n^{1/2^x} > 2 \) quando \( x < x_0 \). Volendo calcolare \(x_0\) riscriviamo la funzione nella forma \( n^{1 / 2^x} = 2^{\frac{\log n}{2^x}} \) ottenendo quindi che \( n^{1 / 2^{x_0}} = 2^{\frac{\log n}{2^{x_0}}} = 2 \) implica \( \frac{\log n}{2^{x_0}} = 1 \). Cioè \( \log n = 2^{x_0} \) e quindi \( \log \log n = x_0 \).
Se prendiamo a questo punto la successione \( n^{1 / 2^m} \) invece della funzione, avremo un numero intero \( m_0 \) per cui \( n^{1/2^m} < 2 \) quando \( x \ge m_0 \) e \( n^{1/2^x} \ge 2 \) quando \( x < m_0 \). Se \(x_0\) è intero, avremo che \( m_0 = x_0 + 1 \), se \( x_0 \) ha invece un parte frazionaria non nulla sarà \( m_0 = \left\lceil x_0 \right\rceil \). In generale si avrà quindi che \( m_0 \le \log\log n + 1 \).
Riprendendo quindi le idee del mio post precedente, abbiamo che \( F(n) < m_0 \) perché \( \left\lfloor \sqrt n \right\rfloor \le \sqrt n \) e quindi la successione dei numeri data dall'iterazione di \( n \mapsto \left\lfloor \sqrt n \right\rfloor \) è sempre minore o uguale a \( \left\lfloor n^{1 / 2^m} \right\rfloor \). Inoltre abbiamo che \( \left\lfloor n^{1 / 2^{m_0}} \right\rfloor = 1 \). Abbiamo quindi ottenuto che \( F(n) < \log \log n + 1 \) per cui \( F(n) \in O(\log \log n) \).
Questa ha senza dubbio più l'aria di essere una dimostrazione. Quella di prima seguiva però di più il modo in cui ero arrivato alla soluzione. Ci sono senza dubbio delle cose non scritte in quella dimostrazione. La parte mancante del ragionamento era che, come ho poi mostrato in questo post, \( m \) è sempre più o meno uguale a \( \log \log n \). La differenza tra i due valori è infatti al massimo \(1\). Quello che forse mancava era mostrare che se \(2^{2^{m-1}} < n < 2^{2^m}\) allora si vedeva subito che \(m-1 < \log\log n\) che \(\log\log n < m \). In un certo senso era sottinteso nel mio discorso su \(M\), ma mai espresso bene.
Sia \(n\) un numero intero fissato. La funzione reale \( x \mapsto n^{1/2^x} \) è strettamente decrescente in \( x > 0 \) (il resto dell'asse reale non ci interessa per questa discussione) e tende \(1\) quando \(x\) tende a \(\infty\). Ci sarà quindi un valore di \( x_0 \) per cui \( n^{1 / 2^{x_0}} = 2 \), \( n^{1/2^x} < 2 \) quando \( x > x_0 \) e \( n^{1/2^x} > 2 \) quando \( x < x_0 \). Volendo calcolare \(x_0\) riscriviamo la funzione nella forma \( n^{1 / 2^x} = 2^{\frac{\log n}{2^x}} \) ottenendo quindi che \( n^{1 / 2^{x_0}} = 2^{\frac{\log n}{2^{x_0}}} = 2 \) implica \( \frac{\log n}{2^{x_0}} = 1 \). Cioè \( \log n = 2^{x_0} \) e quindi \( \log \log n = x_0 \).
Se prendiamo a questo punto la successione \( n^{1 / 2^m} \) invece della funzione, avremo un numero intero \( m_0 \) per cui \( n^{1/2^m} < 2 \) quando \( x \ge m_0 \) e \( n^{1/2^x} \ge 2 \) quando \( x < m_0 \). Se \(x_0\) è intero, avremo che \( m_0 = x_0 + 1 \), se \( x_0 \) ha invece un parte frazionaria non nulla sarà \( m_0 = \left\lceil x_0 \right\rceil \). In generale si avrà quindi che \( m_0 \le \log\log n + 1 \).
Riprendendo quindi le idee del mio post precedente, abbiamo che \( F(n) < m_0 \) perché \( \left\lfloor \sqrt n \right\rfloor \le \sqrt n \) e quindi la successione dei numeri data dall'iterazione di \( n \mapsto \left\lfloor \sqrt n \right\rfloor \) è sempre minore o uguale a \( \left\lfloor n^{1 / 2^m} \right\rfloor \). Inoltre abbiamo che \( \left\lfloor n^{1 / 2^{m_0}} \right\rfloor = 1 \). Abbiamo quindi ottenuto che \( F(n) < \log \log n + 1 \) per cui \( F(n) \in O(\log \log n) \).
Questa ha senza dubbio più l'aria di essere una dimostrazione. Quella di prima seguiva però di più il modo in cui ero arrivato alla soluzione. Ci sono senza dubbio delle cose non scritte in quella dimostrazione. La parte mancante del ragionamento era che, come ho poi mostrato in questo post, \( m \) è sempre più o meno uguale a \( \log \log n \). La differenza tra i due valori è infatti al massimo \(1\). Quello che forse mancava era mostrare che se \(2^{2^{m-1}} < n < 2^{2^m}\) allora si vedeva subito che \(m-1 < \log\log n\) che \(\log\log n < m \). In un certo senso era sottinteso nel mio discorso su \(M\), ma mai espresso bene.
ook ora mi è molto più chiaro, con questo tuo ultimo commento mi ha chiarito alcuni passaggi fumosi.
molto interessante, ti ringrazio davvero
molto interessante, ti ringrazio davvero
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo