[Algoritmi] Dubbi Dimostrazioni complessità asintotica
Salve, sto riscontrando delle difficoltà nel dimostrare la seguente affermazione (e in generale in tutte le dimostrazioni simili):
$ (n + 2)3^n = O((4^n)/n) $
Utilizzando la definizione lo scopo è trovare le due costanti $ c $ e $n_0$ per cui vale
$ (n+2)3^n <= (4^n)/n, AA n>=n_0$
Ma a questo punto non ho proprio idea di come procedere... scelgo la costante $c$ e trovo $n_0$? O viceversa? Grazie in anticipo per l’aiuto
$ (n + 2)3^n = O((4^n)/n) $
Utilizzando la definizione lo scopo è trovare le due costanti $ c $ e $n_0$ per cui vale
$ (n+2)3^n <= (4^n)/n, AA n>=n_0$
Ma a questo punto non ho proprio idea di come procedere... scelgo la costante $c$ e trovo $n_0$? O viceversa? Grazie in anticipo per l’aiuto
Risposte
Hai dimenticato di inserire la costante \(c\) nella tua diseguaglianza. In ogni caso tratti di solito la \(c\) come l'incognita e quando fai delle semplificazioni aggiungi delle condizioni su (n.\)
In particolare inizi riscrivendo la tua disuguaglianza in modo da estrarre \(c\). Hai quindi:
\[ c \geq \frac{n\,(n + 2)\,3^n}{4^n} \]
Per \(n > 1\) hai che \(n\,(n+2) < 4\,n^2.\) Portiamo poi i due esponenti alla stessa base in modo da poterci fare qualcosa. Puoi scrivere \(3^n = 2^{n\,\log 3}\) e \(4^n = 2^{2\,n}\) ottenendo
\[ c \geq 4\,n^2\,2^{n\,(\log 3 - 2)} \]
Hai che \(\log 3 - 2 < -0.4\) per cui \( e^{n\,(\log 3 - 2)} < e^{-n/3} \) per ad esempio \(n > 3\). Riscriviamo \( 4\,n^2 = 2^{ 2 + 2\,\log n } \) ottenendo infine:
\[ c \geq 2^{ 2 + 2\,\log n - n/3 } \]
A questo punto puoi scegliere un valore di \(c\) per cui questa disuguaglianza ha senso e usarlo per trovare un \(n\) che vada bene. Se per esempio scegli \(c = 4\) ottieni \(1 \geq 2^{2\,\log n - n/3} \) da cui prendendo il logaritmo hai \( n \geq 6\,\log n. \) Questo è certamente vero per \(n > 32.\) Nota che normalmente non sei interessato a sapere i valori più piccoli per cui questo è verificato. Devi solo dimostrare che esistono.
In particolare inizi riscrivendo la tua disuguaglianza in modo da estrarre \(c\). Hai quindi:
\[ c \geq \frac{n\,(n + 2)\,3^n}{4^n} \]
Per \(n > 1\) hai che \(n\,(n+2) < 4\,n^2.\) Portiamo poi i due esponenti alla stessa base in modo da poterci fare qualcosa. Puoi scrivere \(3^n = 2^{n\,\log 3}\) e \(4^n = 2^{2\,n}\) ottenendo
\[ c \geq 4\,n^2\,2^{n\,(\log 3 - 2)} \]
Hai che \(\log 3 - 2 < -0.4\) per cui \( e^{n\,(\log 3 - 2)} < e^{-n/3} \) per ad esempio \(n > 3\). Riscriviamo \( 4\,n^2 = 2^{ 2 + 2\,\log n } \) ottenendo infine:
\[ c \geq 2^{ 2 + 2\,\log n - n/3 } \]
A questo punto puoi scegliere un valore di \(c\) per cui questa disuguaglianza ha senso e usarlo per trovare un \(n\) che vada bene. Se per esempio scegli \(c = 4\) ottieni \(1 \geq 2^{2\,\log n - n/3} \) da cui prendendo il logaritmo hai \( n \geq 6\,\log n. \) Questo è certamente vero per \(n > 32.\) Nota che normalmente non sei interessato a sapere i valori più piccoli per cui questo è verificato. Devi solo dimostrare che esistono.
Grazie mille davvero
"apatriarca":
Per \(n > 1\) hai che \(n\,(n+2) < 4\,n^2.\) Portiamo poi i due esponenti alla stessa base in modo da poterci fare qualcosa.
Per lo stesso ragionamento al secondo passaggio avrebbe senso sostituire $ 3^n$ con $4^n$ per ottenere
$ c >= (n(n+2)4^n )/ 4^n $ ?
Quel passaggio porterebbe a eliminare i due esponenziali e a rimanere con una costante maggiore di una sequenza che tende all'infinito.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo