O, Ω, Θ esercizi
Ciao a tutti,
devo dimostrare che la funzione $f(x) = 5x + 3$ è $\Theta(x)$.
La definizione di $\Theta(f(x))$ è:
$g(n)$ è $Θ(f(n))$ se $∃$ tre costanti $c1,c2>0$ e $n0≥0$ tali che
$c1 f(n) ≤ g(n) ≤ c2 f(n)$ per ogni $n ≥ n0$ cioè $g$ cresce esattamente come $f$.
Detto questo come posso dimostrarlo? Non ho capito molto le applicazioni di questa definizione..
Grazie
devo dimostrare che la funzione $f(x) = 5x + 3$ è $\Theta(x)$.
La definizione di $\Theta(f(x))$ è:
$g(n)$ è $Θ(f(n))$ se $∃$ tre costanti $c1,c2>0$ e $n0≥0$ tali che
$c1 f(n) ≤ g(n) ≤ c2 f(n)$ per ogni $n ≥ n0$ cioè $g$ cresce esattamente come $f$.
Detto questo come posso dimostrarlo? Non ho capito molto le applicazioni di questa definizione..
Grazie
Risposte
Per \(\displaystyle x\ge x_0 = 3 \), \(\displaystyle 6x > 5x+3 \). Inoltre \(\displaystyle 5x<5x+3 \) per ogni \(\displaystyle x>0 \). Ti basta unire le due cose.
Cioè per dimostrarla mi basta prendere due costanti a caso $c_1$ e $c_2$ e sostituirle nella "formula" $c_1f(n)≤g(n)≤c_2f(n)$ ?
Es: $c_1 = 10$ e $c_2 = 7$
$10x <= 5x +3 <= 7x$
Metto in sistema, faccio i calcoli ed ottengo $3/5<= x <= 3/2$ .. Bene, ed ora? Non penso di avere capito..
Es: $c_1 = 10$ e $c_2 = 7$
$10x <= 5x +3 <= 7x$
Metto in sistema, faccio i calcoli ed ottengo $3/5<= x <= 3/2$ .. Bene, ed ora? Non penso di avere capito..
Quello è un caso piuttosto banale. In ogni caso il tutto consiste nel trovare le costanti \(\displaystyle c_1 \), \(\displaystyle c_2 \) e \(\displaystyle n_0 \) per cui vale quella formula. In genere il problema è che tu non hai una espression esplicita di \(\displaystyle g(x) \).
Mmm ok, ma quindi dimostrato come ho scritto io andrebbe bene?
No, la formula deve essere vera. \(\displaystyle 10x \) non è minore di \(\displaystyle 5x+3 \) per \(\displaystyle x>1 \) quindi quello che hai scritto è falso. D'altra parte \(\displaystyle c_1 = 1 \), \(\displaystyle c_2 = 1000000000 \) e \(\displaystyle n_0 = 1 \) vanno assolutamente bene.
\(\displaystyle c_1f(x) \le g(x) \le c_2f(x) \) per \(\displaystyle x\ge n_0 \), vuol dire che \(\displaystyle c_1f(x) \) è minore o uguale a \(\displaystyle g(x) \) per ogni \(\displaystyle x \) che sia maggiore di \(\displaystyle n_0 \) e al contempo per la stessa \(\displaystyle x \) succede che \(\displaystyle g(x) \) sia minore o ugual a \(\displaystyle c_2f(x) \). Dove \(\displaystyle cf(x) \) significa che tu moltiplichi \(\displaystyle c \) a \(\displaystyle f(x) \), non è una notazione formale.
\(\displaystyle c_1f(x) \le g(x) \le c_2f(x) \) per \(\displaystyle x\ge n_0 \), vuol dire che \(\displaystyle c_1f(x) \) è minore o uguale a \(\displaystyle g(x) \) per ogni \(\displaystyle x \) che sia maggiore di \(\displaystyle n_0 \) e al contempo per la stessa \(\displaystyle x \) succede che \(\displaystyle g(x) \) sia minore o ugual a \(\displaystyle c_2f(x) \). Dove \(\displaystyle cf(x) \) significa che tu moltiplichi \(\displaystyle c \) a \(\displaystyle f(x) \), non è una notazione formale.
Ho capito, grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo