[Algoritmi] Notazioni asintotiche
Salve, sto avendo delle difficoltà nel dimostrare la veridicità di alcuni esercizi sulle notazioni asintotiche, ovvero:
Provare che $10n^3+2n^2+7=O(n^3)$
Ora, risparmiandovi la definizione della notazione O grande, in cui bisogna trovare una costante e un n0 ecc. ecc. come va provato l'esercizio? Ovvero quali sono i passi da compiere per trovare appunto questa costante e n0 ? Sul testo dice che i passi sono questi ma non dice come si è arrivati:
$10n^3+2n^2+7<=10n^3+2n^3+7<=10n^3+2n^3+n^3=13n^3$
La diseguaglianza è soddisfatta quindi per $c = 13$ e $n0 = 2$
Provare che $10n^3+2n^2+7=O(n^3)$
Ora, risparmiandovi la definizione della notazione O grande, in cui bisogna trovare una costante e un n0 ecc. ecc. come va provato l'esercizio? Ovvero quali sono i passi da compiere per trovare appunto questa costante e n0 ? Sul testo dice che i passi sono questi ma non dice come si è arrivati:
$10n^3+2n^2+7<=10n^3+2n^3+7<=10n^3+2n^3+n^3=13n^3$
La diseguaglianza è soddisfatta quindi per $c = 13$ e $n0 = 2$
Risposte
Non c'è un vero e proprio metodo.. Puoi ovviamente creartene uno, ma alla fine devi trovare una costante qualsiasi per cui valga la relazione. Siccome \(2\,n^2 + 7\) è positivo per ogni \(n\) è ovvio che questa costante deve essere maggiore di \(10,\) ma di quanto maggiore vuoi questa costante dipende da te. Se ad esempio prendi come costante \(11,\) devi trovare un \(n_0\) per cui \( 10\,n_0^3 + 2\,n_0^2 + 7 \leq 11\,n_0^3.\) Di fatto devi risolvere l'equazione corrispondente. La soluzione è circa \(2.9\), per cui puoi ad esempio scegliere \(n_0 = 3\).
Normalmente si cerca di scegliere delle costanti per cui vengono facilmente i calcoli. Sostituire ad ogni potenza, una potenza superiore è un esempio di metodo utilizzabile per trovare queste costanti. Hai insomma ovviamente che \( 2\,n^2 \leq 2\,n^3\) per \( n \geq 1\) per cui puoi usare questo fatto per arrivare ad espressioni con una sola potenza. Esistono anche molte altre diseguaglianze che puoi usare. Se avessi ad esempio qualcosa come \( x^2 + \log(x^3 + 3\,x^2) \) puoi osservare che il logaritmo è una funzione monotona per cui \( \log(x^3 + 3\,x^2) \leq \log( 4\,x^3 \) \leq \log\,4 + 3\,\log\,x \leq x^2 \) per un \(x\) sufficientemente grande. Per cui alla fine andrà bene usare \(2\) (o qualcosa di anche più grande) come costante e poi ti calcoli il tuo \(n_0\).
Grazie più o meno sto iniziando a capire qualcosa, ora sto avendo però molte difficoltà con i logaritmi negli esercizi, ad esempio qui non so proprio da dove partire:
$5n sqrt(n) log n^2 + 10n^2 = \Theta(n^2)$
Da dove inizio per trovare le costanti e gli n0 ?
$5n sqrt(n) log n^2 + 10n^2 = \Theta(n^2)$
Da dove inizio per trovare le costanti e gli n0 ?
Puoi in generale memorizzare che il logaritmo è più piccolo di ogni potenza.. Per cui in particolare hai che \( \log(n) < n^{1/2}. \) Nel tuo caso hai quindi \( 5\,n\,\sqrt{n}\log(n^2) = 10\,n^{3/2}\,\log(n) < 10\,n^2. \) che puoi quindi usare per arrivare a rispondere alla tua domanda.
Provando a svolgere l'esercizio mi risulta quindi che la relazione è $\Omega$ se prendiamo una costante = 10, per ogni n0 maggiore o uguale a 0. Infatti correggimi se sbaglio, mi trovo:
Nel caso n = 0 e c = 10
$0 >= 0$
Nel caso n = 1 e c = 10
$10 >= 10$
Nel caso n = 2 e c = 10
$68.2 >= 40$
Quindi inutile fare altri n casi dato che si intuisce che f(x) sarà sempre maggiore di g(x). Non ho capito però se n0 in questo caso parte da 0 o da 2
Nel caso n = 0 e c = 10
$0 >= 0$
Nel caso n = 1 e c = 10
$10 >= 10$
Nel caso n = 2 e c = 10
$68.2 >= 40$
Quindi inutile fare altri n casi dato che si intuisce che f(x) sarà sempre maggiore di g(x). Non ho capito però se n0 in questo caso parte da 0 o da 2
Non ha importanza quale \( n_0 \) scegli.. Puoi prendere \(0,\) \(2\) o anche \(10^6\). L'importante è che esista un tale valore.
Capisco, quindi in questo caso basta scegliere 2 come n0 e 10 come costante per verificare che la relazione è $\Omega$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo