Notazione Asintotica : THETA Grande ( g(n) )
Salve avrei un problema semplice da risolvere ma che mi sta dando filo da torcere.
In effetti studio informatica e sto tarttando la complessità computazionale degli algoritmi.
Sto togliendo un pò di ruggine da alcune nozioni fondamentali in matematica e mi trovo di fronte ad una disequazione che sarà di soluzione banale ma non riesco a risolverla
Spiego un pò il problema in generale:
Definizione:
Per una data funzione g(n) , indichiamo con THETAgrande(g(n)) l'insieme delle funzioni
THETAgrande(g(n)) = { f(n) : esistono delle costanti c1, c2 e n0 tali che
0 <= c1 g(n) <= f(n) <= c2 g(n) per ogni n >= n0
quindi f(n) appartiene all'insieme di THETAgrande(g(n))
adesso ho la funzione f(n) : 1/2n^2 - 3n
Informalmete posso dire che se prendo il termine con grado più alto ( senza coefficiente ) ed elimino quelli di grado inferiore
ottengo n^2 e quindi posso dire che 1/2n^2 - 3n appartiene a THETAgrande(n^2)
Per dimostrare ciò dobbiamo determinare le costanti positive c1,c2 e n0 in modo che
c1 n^2 <= 1/2n^2 - 3n <= c2n^2
semplifico tutto per n^2
ed ottengo
c1 <= 1/2 - 3/n <= c2
adesso ho le soluzioni ma non riesco a dimostrarle
La disuguaglianza destra può essrere resa valida per qualsiasi n>=1 scegliendo c2 >= 1/2,
La disuguaglianza sinistra può essrere resa valida per qualsiasi n>=7 scegliendo c2 >= 1/14,
Soluzione: scegliendo c1 = 1/14 , c2 = 1/2 e n0 = 7 possiamo verificare he 1/2n^2 - 3n appartiene a THETAgrande(n^2)
Chiedo cortesemente se qualcuno puo aiutarmi a risolvere questa piccola disuguaglianza.
Saluti e grazie anticipatamente
In effetti studio informatica e sto tarttando la complessità computazionale degli algoritmi.
Sto togliendo un pò di ruggine da alcune nozioni fondamentali in matematica e mi trovo di fronte ad una disequazione che sarà di soluzione banale ma non riesco a risolverla
Spiego un pò il problema in generale:
Definizione:
Per una data funzione g(n) , indichiamo con THETAgrande(g(n)) l'insieme delle funzioni
THETAgrande(g(n)) = { f(n) : esistono delle costanti c1, c2 e n0 tali che
0 <= c1 g(n) <= f(n) <= c2 g(n) per ogni n >= n0
quindi f(n) appartiene all'insieme di THETAgrande(g(n))
adesso ho la funzione f(n) : 1/2n^2 - 3n
Informalmete posso dire che se prendo il termine con grado più alto ( senza coefficiente ) ed elimino quelli di grado inferiore
ottengo n^2 e quindi posso dire che 1/2n^2 - 3n appartiene a THETAgrande(n^2)
Per dimostrare ciò dobbiamo determinare le costanti positive c1,c2 e n0 in modo che
c1 n^2 <= 1/2n^2 - 3n <= c2n^2
semplifico tutto per n^2
ed ottengo
c1 <= 1/2 - 3/n <= c2
adesso ho le soluzioni ma non riesco a dimostrarle
La disuguaglianza destra può essrere resa valida per qualsiasi n>=1 scegliendo c2 >= 1/2,
La disuguaglianza sinistra può essrere resa valida per qualsiasi n>=7 scegliendo c2 >= 1/14,
Soluzione: scegliendo c1 = 1/14 , c2 = 1/2 e n0 = 7 possiamo verificare he 1/2n^2 - 3n appartiene a THETAgrande(n^2)
Chiedo cortesemente se qualcuno puo aiutarmi a risolvere questa piccola disuguaglianza.
Saluti e grazie anticipatamente
Risposte
Ciao e benvenuto.
Cosa vuoi dimostrare? A parte che alla quintultima riga hai messo un c2 al posto di un c1...mi sembra che tu abbia già tutto quello che ti serve.
$1/2-3/n$ è compreso tra $1/14$ e $1/2$ per $n>=7$. Fine.
Cosa vuoi dimostrare? A parte che alla quintultima riga hai messo un c2 al posto di un c1...mi sembra che tu abbia già tutto quello che ti serve.
$1/2-3/n$ è compreso tra $1/14$ e $1/2$ per $n>=7$. Fine.
si è vero scusa ci voleva c2 è stato un copia ed incolla non controllato
in effetti dalla disuguaglianza iniziale non riesco ad arrivare alle soluzioni tramite i passaggi intermedi...
le soluzioni stanno sul libro non è che le ho trovate io...ma non riesco ad andare avanti se non mi spiego come ci si arriva a quella soluzione..
in effetti dalla disuguaglianza iniziale non riesco ad arrivare alle soluzioni tramite i passaggi intermedi...
le soluzioni stanno sul libro non è che le ho trovate io...ma non riesco ad andare avanti se non mi spiego come ci si arriva a quella soluzione..
scusami di nuovo c1 non c2 eh eh
Non capisco. Ci sono tutti i passaggi in quella dimostrazione. E' molto semplice e molto dettagliata. Forse non sai come passare dall'uno all'altro. Dov'è che ti blocchi?
Da sove escono questi valori è lì che mi blocco
La disuguaglianza destra può essere resa valida per qualsiasi n>=1 scegliendo c2 >= 1/2,
La disuguaglianza sinistra può essere resa valida per qualsiasi n>=7 scegliendo c1 >= 1/14,
La disuguaglianza destra può essere resa valida per qualsiasi n>=1 scegliendo c2 >= 1/2,
La disuguaglianza sinistra può essere resa valida per qualsiasi n>=7 scegliendo c1 >= 1/14,
Ci sono tanti modi per vederlo. Ad esempio osservi che $1/2-3/n$ è una quantità crescente con n, positiva da 6 in poi;
per $n=7$ vale $1/14$. Quindi se è crescente per tutti i valori di n più grandi di $7$ quella quantità è più grande di $1/14$
Inoltre per $n>=1$ quindi $3/n>=0$ quindi $1/2-3/n<=1/2$ per tutti gli $n>=1 $
per $n=7$ vale $1/14$. Quindi se è crescente per tutti i valori di n più grandi di $7$ quella quantità è più grande di $1/14$
Inoltre per $n>=1$ quindi $3/n>=0$ quindi $1/2-3/n<=1/2$ per tutti gli $n>=1 $
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo