[Algoritmi]Notazione O-grande
Ciao a tutti!
Qualcuno potrebbe aiutarmi a risolvere il seguente quesito?
Grazie.
Si supponga di avere due funzioni $f(x)$ e $g(x)$ tali che $f(x)=O(g(x))$. Per ciascuna delle seguenti affermazioni, si dica se essa è vera, fornendone una prova, o falsa, fornendone un controesempio:
a)$log f(x) = O(log(g(x))$
b)$2^f(x) = O(2^g(x))$
c)$f(x)^2=O(g(x)^2)$
Qualcuno potrebbe aiutarmi a risolvere il seguente quesito?
Grazie.
Si supponga di avere due funzioni $f(x)$ e $g(x)$ tali che $f(x)=O(g(x))$. Per ciascuna delle seguenti affermazioni, si dica se essa è vera, fornendone una prova, o falsa, fornendone un controesempio:
a)$log f(x) = O(log(g(x))$
b)$2^f(x) = O(2^g(x))$
c)$f(x)^2=O(g(x)^2)$
Risposte
Nessuno riesce ad aiutarmi, per favore?
Hai provato ad applicare la definizione? Qualcosa del genere afair
$f(x)inO(g(x)) -= EE x_0 >=0 , EE k>0 : forall x >x_0, |f(x)|<=k|g(x)|$
Fa' vedere cosa (non) ti torna.
$f(x)inO(g(x)) -= EE x_0 >=0 , EE k>0 : forall x >x_0, |f(x)|<=k|g(x)|$
Fa' vedere cosa (non) ti torna.
Ciao ti ringrazio per la risposta.
Il problema è che non riesco a impostarlo perché non ho solo $f(x)$ ma $log f(x)$ come lo sostituisco nella definizione?E poi se errato come faccio il controesempio. La definizione l'ho capita, ho fatto anche altri tipi di esercizi senza grossi problemi, questo invece mi fa andare in difficoltà.
Il problema è che non riesco a impostarlo perché non ho solo $f(x)$ ma $log f(x)$ come lo sostituisco nella definizione?E poi se errato come faccio il controesempio. La definizione l'ho capita, ho fatto anche altri tipi di esercizi senza grossi problemi, questo invece mi fa andare in difficoltà.
La prima direi è vera, se $|f(x)|<=k*|g(x)|$ per qualche $k>0$ allora anche $log(f(x))<=h*log(k*g(x))$ per qualche $h>0$ - ma mi sottopongo ad eventuali smentite se avessi preso una cantonata. 
Per la seconda, un suggerimento: prova a vedere cosa succede con $f(x)=2*x^2$
Per la seconda, un suggerimento: prova a vedere cosa succede con $f(x)=2*x^2$
Ok, per la prima.
Dunque per la seconda, occorre provare che $2^f(x)<=c*2^g(x)$ per c>0 e per ogni x sufficientemente grande.
E poi devo trovare questi valori,c e x?Boh io non riesco a capire.
La prima l'avete dimostrata con semplicità ed effettivamente l'ho capita!
Dunque per la seconda, occorre provare che $2^f(x)<=c*2^g(x)$ per c>0 e per ogni x sufficientemente grande.
E poi devo trovare questi valori,c e x?Boh io non riesco a capire.
La prima l'avete dimostrata con semplicità ed effettivamente l'ho capita!
Il discorso è simile anche in questo caso (e ho l'impressione che sia già stata dimostrata da qualche parte qui nel forum in precedenza).
Abbiamo anche qui che \(f(x) \le k\,g(x)\) implica \( 2^{f(x)} \le 2^{k\,g(x)} \). Qui però il discorso è un po' più complicato. Infatti \( 2^{k\,g(x)} = (2^{g(x)})^k \). Direi infatti, se non ho preso un abbaglio, che non sia possibile trovare una costante \( h \ge 0 \) per cui sia \( 2^{f(x)} \le (2^{g(x)})^k \le h\,2^{g(x)} \). E' ovviamente possibile per alcuni valori di \(k\), ma in generale è falso. Considera per esempio \( f(x) = 3\,x^2 \) e \( g(x) = x^2 \). Si ha ovviamente che \( f(x) \le k\,g(x) \) per ogni \(k \ge 3\). Non esiste però alcuna costante \(h\) per cui \( 2^{f(x)} = 2^{3\,x^2} = (2^{x^2})^3 \le h\,2^{x^2} \).
Abbiamo anche qui che \(f(x) \le k\,g(x)\) implica \( 2^{f(x)} \le 2^{k\,g(x)} \). Qui però il discorso è un po' più complicato. Infatti \( 2^{k\,g(x)} = (2^{g(x)})^k \). Direi infatti, se non ho preso un abbaglio, che non sia possibile trovare una costante \( h \ge 0 \) per cui sia \( 2^{f(x)} \le (2^{g(x)})^k \le h\,2^{g(x)} \). E' ovviamente possibile per alcuni valori di \(k\), ma in generale è falso. Considera per esempio \( f(x) = 3\,x^2 \) e \( g(x) = x^2 \). Si ha ovviamente che \( f(x) \le k\,g(x) \) per ogni \(k \ge 3\). Non esiste però alcuna costante \(h\) per cui \( 2^{f(x)} = 2^{3\,x^2} = (2^{x^2})^3 \le h\,2^{x^2} \).
Non mi è del tutto chiaro. Quello che ho capito è che viene applicata la deinizione di O-grande prima per $f(x)$ e $g(x)$ e poi, nel primo caso, per $log$ oppure nel secondo caso per l'esponenziale. Diciamo che il primo esempio riesco a capirlo, mentre il secondo, già è un po' forzato.
Mentre per il terzo caso, sapendo che $f(x)<= k*g(x)$ implica che $f(x)^2<= k*g(x)^2$ è quindi è vero per ogni $x>=1$ con $k=1$. Giusto?
Grazie.
Mentre per il terzo caso, sapendo che $f(x)<= k*g(x)$ implica che $f(x)^2<= k*g(x)^2$ è quindi è vero per ogni $x>=1$ con $k=1$. Giusto?
Grazie.
Il terzo è il più facile di tutti.. \( f(x) \le k\,g(x) \implies f(x)^2 \le k^2\,g(x)^2 \) e quindi esiste certamente una costante \( h \ge k^2 \) per cui \( f(x)^2 \le h\,g(x)^2 \)...
Giustamente era $k^2$...ma non riesco a capire bene quella $h$...
"apatriarca":
(e ho l'impressione che sia già stata dimostrata da qualche parte qui nel forum in precedenza).
dovreb essere questa: dubbio-analisi-compl-asintotica-t96149.html
"Skeggia":
Giustamente era $k^2$...ma non riesco a capire bene quella $h$...
Forse non sono stato abbastanza chiaro, e quindi ti ho confuso e mi dispiace.
Cercavo solo di farti capire:
- se $f(x) in O(g(x))$ allora per definizione deve valere, per una certa costante positiva - chiamiamola $k$ - che $|(f(x)|<=k*|g(x)|$(*)
- se devo verificare, dato per ipotesi che $f(x) in O(g(x))$, che $2^(f(x)) in O(2^(g(x)))$ oppure il viceversa $2^(f(x)) notin O(2^(g(x)))$ (fornendo un controesempio), applicherò ex-novo la definizione usando una certa costante positiva, che chiamerò $h$ per distinguerla dalla precedente, e vedendo cosa succede alla disuguaglianza $|2^(f(x))| <= h*|2^(k*g(x))|$
Il controesempio di apatriarca va benissimo (io avevo suggerito $2x^2$, lui utilizza $3x^2$). Se desideri un risultato più formale, è sufficiente tu faccia uso della dimostrazione per assurdo: supponi esista $h$ tale che vale l'asserto, arrivi facilmente ad una contraddizione.
(*) A voler essere precisi, questo non deve valere sempre, è sufficiente valga per ogni $x$ maggiore di un certo $x_0>=0$ opportuno.
PS. Spero di non averti confuso ancor di più le idee.
Ciao e grazie mille.
Sei stato molto chiaro e ora va meglio.
Volevo chiederti un ultimo consiglio poiché la traccia dice <> Nel primo caso che è vera, devo trovare le costanti h e k e provare che la definizione è valida per ogni $x>= x_0$, vero?
Sei stato molto chiaro e ora va meglio.
Volevo chiederti un ultimo consiglio poiché la traccia dice <
Il procedimento è quello - nota bene che io non l'ho dimostrata, ma non dovrebbe essere difficile.
In soldoni, per risolvere questi esercizi basta - oltre ad un po' di pratica - ricordarsi qualcosina di Analisi 1 (corso di ingegneria o simili, se di matematica meglio assai).
In soldoni, per risolvere questi esercizi basta - oltre ad un po' di pratica - ricordarsi qualcosina di Analisi 1 (corso di ingegneria o simili, se di matematica meglio assai).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo