O grande e valutazione della complessità tra funzioni
Mi aiutate a capire qual è la logica per approcciare a questo quesito ?
Confrontare le due funzioni F e G dal punto di vista della complessità: dire se una è $O$ dell’altra e viceversa. In caso affermativo, indicare una coppia $(n0,c)$
$F(x)= \{ (3x^2, text(, se ) x text( è pari)), (50x^3, text(, se ) x text( è dispari)) :}$
$G(x)= \{ (9x^2, text(, se ) x text( è divisore di ) 255), (x^3, text(, altrimenti)) :}$
La definizione di $O$ grande dice:
$f(x) = O(g(x)) <=> \lim_{x \to x_0}f(x)/g(x) = l in RR$ dove $l$ esiste ed è finito.
Facendo una prima analisi noto che i divisore del 255 sono $1, 3, 5, 17, 255$ e non sono pari per cui potrei confrontare la funzione $9x^2$ con $50x^3$ e $3x^2$ e $x^3$, visto che hanno in comune elementi del dominio, ma quale scegliere come numeratore o denominatore tra f(x) e g(x) per il confronto?
potrei tentare questa strada ma non saprei quale sia l'approccio corretto, mi aiutate please?
$\lim_{x \to x_0}(9x^2)/(50x^3)$ e $\lim_{x \to x_0}(3x^2)/x^3$
Grazie
Confrontare le due funzioni F e G dal punto di vista della complessità: dire se una è $O$ dell’altra e viceversa. In caso affermativo, indicare una coppia $(n0,c)$
$F(x)= \{ (3x^2, text(, se ) x text( è pari)), (50x^3, text(, se ) x text( è dispari)) :}$
$G(x)= \{ (9x^2, text(, se ) x text( è divisore di ) 255), (x^3, text(, altrimenti)) :}$
La definizione di $O$ grande dice:
$f(x) = O(g(x)) <=> \lim_{x \to x_0}f(x)/g(x) = l in RR$ dove $l$ esiste ed è finito.
Facendo una prima analisi noto che i divisore del 255 sono $1, 3, 5, 17, 255$ e non sono pari per cui potrei confrontare la funzione $9x^2$ con $50x^3$ e $3x^2$ e $x^3$, visto che hanno in comune elementi del dominio, ma quale scegliere come numeratore o denominatore tra f(x) e g(x) per il confronto?
potrei tentare questa strada ma non saprei quale sia l'approccio corretto, mi aiutate please?
$\lim_{x \to x_0}(9x^2)/(50x^3)$ e $\lim_{x \to x_0}(3x^2)/x^3$
Grazie
Risposte
I divisori di $255$ sono in numero finito, quindi per calcolare il limite ti serve…
In più: il post è disorganizzato, usi notazioni a casaccio (probabilmente perché non hai capito quel che significano), la “definizione” che riporti non è “la” definizione generale.
Ti consiglio di rivedere un po’ il post e la teoria.
In più: il post è disorganizzato, usi notazioni a casaccio (probabilmente perché non hai capito quel che significano), la “definizione” che riporti non è “la” definizione generale.
Ti consiglio di rivedere un po’ il post e la teoria.
"gugo82":
I divisori di $255$ sono in numero finito, quindi per calcolare il limite ti serve…
In più: il post è disorganizzato, usi notazioni a casaccio (probabilmente perché non hai capito quel che significano), la “definizione” che riporti non è “la” definizione generale.
Allora il mio primo errore è quello di aver scritto $\infty$ invece di $x_0$ nei limiti.
Questa invece è la definizione più generale che ho imparato dagli appunti del prof, credevo andasse usata la prima:
date due funzioni $f$ e $g$ così definite $f, g: N->N$ si dice che $f(n)$ è di ordine $O(g(n))$ ( cioè $f(n)$ è $O(g(n))$ ) se esiste un valore intero $n_0$ ed una costante $C>0$ tale che $f(n)<=Cg(n)$ per ogni $n>=n_0$
Proverai a confrontare $9x^2 <=C*50x^3$ dove $x^3$ la considererei $f(n)$ in quanto cresce più velocemente di $x^2$. Posso ricondurmi a questa disuguaglianza se divido per $9x^2$ (valore positivo) quindi ho $1 <=C*50/9x$ da cui $C>=9/(50x)$
quindi provo a mettere i valori $1,3,5,17,255$ al posto di $x$
Ha senso quello che dico?
No, non ce l’ha (almeno così come hai scritto).
La definizione, invece, è buona (anche se al posto di $n$ dovrai usare $x$ come variabile).
Inoltre, $oo$ c’è l’ho messo io correggendo la formattazione del post (formule in primis), perché almeno non dovevo chiederti anche di specificare cosa fosse $x_0$.
Allora, ragiona. Cosa ti dice la definizione?
Cosa devi fare per stabilire se $f = text(O)(g)$ intorno a $oo$?
La definizione, invece, è buona (anche se al posto di $n$ dovrai usare $x$ come variabile).
Inoltre, $oo$ c’è l’ho messo io correggendo la formattazione del post (formule in primis), perché almeno non dovevo chiederti anche di specificare cosa fosse $x_0$.
Allora, ragiona. Cosa ti dice la definizione?
Cosa devi fare per stabilire se $f = text(O)(g)$ intorno a $oo$?
Intorno $\infty$ la funzione $g$ deve assumere valori più grandi rispetto a quelli di $f$ cioè :
$f(n)≤Cg(n)$
un altro dubbio è proprio quello, perchè devo valutare $\infty$ quando una parte delle due funzioni hanno come dominio in comune solo i divisori di 255 ? e l'altra solo quelli pari?
Posso provare intanto a verificare l'andamento delle due funzioni a infinito visto che il loro dominio comune è composto da tutti i numeri pari:
$3x^2<=C*x^3$ se divido per $3x^2$ ottengo $1<= C/3x$
Le due funzioni ($3x^2$ , $x^3$) tendono entrambe ad infinito
ma non capisco dove arrivare l'ultima disequazione è sempre verificata visto che infinito è sempre maggiore di 1
$f(n)≤Cg(n)$
perché almeno non dovevo chiederti anche di specificare cosa fosse x0
un altro dubbio è proprio quello, perchè devo valutare $\infty$ quando una parte delle due funzioni hanno come dominio in comune solo i divisori di 255 ? e l'altra solo quelli pari?
Posso provare intanto a verificare l'andamento delle due funzioni a infinito visto che il loro dominio comune è composto da tutti i numeri pari:
$3x^2<=C*x^3$ se divido per $3x^2$ ottengo $1<= C/3x$
Le due funzioni ($3x^2$ , $x^3$) tendono entrambe ad infinito
ma non capisco dove arrivare l'ultima disequazione è sempre verificata visto che infinito è sempre maggiore di 1
"zio_mangrovia":
Intorno $\infty$ la funzione $g$ deve assumere valori più grandi rispetto a quelli di $f$ cioè :
$f(n)≤Cg(n)$
Se così fosse, non sarebbe bastato scrivere $f(n) <= g(n)$?
"zio_mangrovia":perché almeno non dovevo chiederti anche di specificare cosa fosse x0
un altro dubbio è proprio quello, perchè devo valutare $\infty$ quando una parte delle due funzioni hanno come dominio in comune solo i divisori di 255 ? e l'altra solo quelli pari?
Sei sicuro di aver capito a cosa serve un confronto del genere per quanto riguarda la complessità?
"zio_mangrovia":
Posso provare intanto a verificare l'andamento delle due funzioni a infinito visto che il loro dominio comune è composto da tutti i numeri pari […]
Veramente, il dominio comune di $f$ e $g$ è tutto $NN$.
Sei sicuro di avere ben chiaro cos’è una funzione? E cos’è una funzione definita per casi?
"zio_mangrovia":
[…] $3x^2<=C*x^3$ se divido per $3x^2$ ottengo $1<= C/3x$
Le due funzioni ($3x^2$ , $x^3$) tendono entrambe ad infinito
ma non capisco dove arrivare l'ultima disequazione è sempre verificata visto che infinito è sempre maggiore di 1
Scusa?
rileggendo devo dire che ho fatto un bel po' confusione...
Da ciò che capisco $g(n)$ è come se fosse una limitazione superiore di $f(n)$ quindi $O(g(n))$ possiamo vederlo come un insieme di funzioni cui $g(n)$ appartiene... tradotto in parole spicciole $f(n)<=Cg(n)$
Scusate ma oltre non arrivo...
Da ciò che capisco $g(n)$ è come se fosse una limitazione superiore di $f(n)$ quindi $O(g(n))$ possiamo vederlo come un insieme di funzioni cui $g(n)$ appartiene... tradotto in parole spicciole $f(n)<=Cg(n)$
Scusate ma oltre non arrivo...
Ora stai scrivendo il contrario di quello che avevi scritto sopra…
Decidi: cosa vuoi studiare prima? Che $f = text(O)(g)$ oppure che $g = text(O)(f)$?
Decidi: cosa vuoi studiare prima? Che $f = text(O)(g)$ oppure che $g = text(O)(f)$?
corretto adesso, questi f e g mi stanno facendo perdere la mia identità ! 
partiamo dall'ultima affermazione da me corretta se non ti dispiace... un aiuto please?
partiamo dall'ultima affermazione da me corretta se non ti dispiace... un aiuto please?
Devi mostrare che esistono $x_0 in NN$ e $C>0$ tali che $f(x) <= C g(x)$ per ogni $x >= x_0$.
Quando la funzione $g$ non è nulla (come in questo caso), la condizione $f(x) <= C g(x)$ equivale a $(f(x))(
/(g(x)) <= C$, ossia alla limitatezza dall’alto del rapporto $f/g$; in tal caso, come $C$ puoi prendere l’estremo superiore di $f/g$ (è la costante ottimale) e coprire tutti i valori naturali di $x$, oppure prendere una costante più piccola a patto che sia possibile scegliere $x_0$ sufficientemente grande da verificare la disuguaglianza.
Nel tuo caso, il rapporto $f/g$ lo puoi esprimere esplicitamente usando le leggi di assegnazione di $f$ e $g$, ossia distinguendo opportuni casi:
$(f(x))/(g(x)) := \{ ((3x^2)/(x^3), text(, se ) x text( è pari)), ((50x^3)/(9x^2), text(, se ) x text( è divisore di ) 255), ((50x^3)/(x^3), text(, altrimenti)) :} = \{ (3/x, text(, se ) x text( è pari)), (50/9 x, text(, se ) x text(=1, 3, 5, 15, 17, 51, 85, 255)), (50, text(, altrimenti)) :}$
e quel che ti rimane da fare è capire chi è l’estremo superiore di $f/g$.
P.S.: Renditi conto che non hai nemmeno elencato tutti i divisori di $255$, il che è una questione di Aritmetica da scuole medie…
Quando la funzione $g$ non è nulla (come in questo caso), la condizione $f(x) <= C g(x)$ equivale a $(f(x))(
/(g(x)) <= C$, ossia alla limitatezza dall’alto del rapporto $f/g$; in tal caso, come $C$ puoi prendere l’estremo superiore di $f/g$ (è la costante ottimale) e coprire tutti i valori naturali di $x$, oppure prendere una costante più piccola a patto che sia possibile scegliere $x_0$ sufficientemente grande da verificare la disuguaglianza.
Nel tuo caso, il rapporto $f/g$ lo puoi esprimere esplicitamente usando le leggi di assegnazione di $f$ e $g$, ossia distinguendo opportuni casi:
$(f(x))/(g(x)) := \{ ((3x^2)/(x^3), text(, se ) x text( è pari)), ((50x^3)/(9x^2), text(, se ) x text( è divisore di ) 255), ((50x^3)/(x^3), text(, altrimenti)) :} = \{ (3/x, text(, se ) x text( è pari)), (50/9 x, text(, se ) x text(=1, 3, 5, 15, 17, 51, 85, 255)), (50, text(, altrimenti)) :}$
e quel che ti rimane da fare è capire chi è l’estremo superiore di $f/g$.
P.S.: Renditi conto che non hai nemmeno elencato tutti i divisori di $255$, il che è una questione di Aritmetica da scuole medie…
Adesso si fa luce dopo la tempesta.
Se non sbaglio la mia interpretazione dovrei trovare il valore della costante $C$ nei 3 casi e scegliere quello più grande che soddisfi ogni disuguaglianza.
nel caso 3 il limite superiore è 50 quindi $C$ non può scendere sotto $50$
nel caso 2 $C$ assume come valore minimo $50/9$ fino a $50/9*255$
nel caso 1 $C=3/x$ per cui il valore più grande sarà $3/2$ in quanto il primo numero pari è 2
quindi potrei prendere $C=50/9*255$ che mi soddisferebbe disuguaglianza $f(x)<=Cg(x)$
La soluzione riporta però $n_0=256, C=51$ (chiedeva di indicare una coppia $n_0,C$) di cui non comprendo pienamente la logica ma provo con voi a ragionarci su.
[list=1] [*:2lidzkwt] Caso 3: $C=51$ è stato considerato perchè immediatamente sopra al $50$
Caso 2: $n_0$ lo prendo maggiore di 255 in modo da evitare i divisori del 255 perchè il maggiore determinerebbe una costante sopra il 51.
Caso 1: $C$ non rappresenta un problema in quanto $x<1$ quando $x$ è pari e $x>=256$
Corretto?
[/*:m:2lidzkwt]
[*:2lidzkwt]Avrei potuto però considerare anche la soluzione $n_0=256, C=50$ ? Del resto la disuguaglianza $f(x)<=Cg(x)$ non parla di minore stretto.
[/*:m:2lidzkwt]
[*:2lidzkwt] Posso considerare la mia soluzione corretta $C=50/9*255$ per qualunque $x>0$ ?
[/*:m:2lidzkwt]
[*:2lidzkwt] Si dice:
Che significa? Per come è definita la funzione g(x) quando $x=0$ $x^3=0$ no ?
Immagino si intenda che non è definita in $x=0$ quando si parla di rapporto $f(x)/g(x)$ giusto ?
[/*:m:2lidzkwt]
[*:2lidzkwt] C'e' una strategia che mi consente di capire quale sia la funzione da prendere in esame come $g(x)$ e $f(x)$ ?[/*:m:2lidzkwt][/list:o:2lidzkwt]
La fretta, la benedetta fretta di arrivare al dunque, devia il focus altrove e ti scava il piede nella fossa.
Non ho scuse !!! Mi autoflagellerò
Grazie per la tua spiegazione super chiarissima.
Se non sbaglio la mia interpretazione dovrei trovare il valore della costante $C$ nei 3 casi e scegliere quello più grande che soddisfi ogni disuguaglianza.
nel caso 3 il limite superiore è 50 quindi $C$ non può scendere sotto $50$
nel caso 2 $C$ assume come valore minimo $50/9$ fino a $50/9*255$
nel caso 1 $C=3/x$ per cui il valore più grande sarà $3/2$ in quanto il primo numero pari è 2
quindi potrei prendere $C=50/9*255$ che mi soddisferebbe disuguaglianza $f(x)<=Cg(x)$
La soluzione riporta però $n_0=256, C=51$ (chiedeva di indicare una coppia $n_0,C$) di cui non comprendo pienamente la logica ma provo con voi a ragionarci su.
[list=1] [*:2lidzkwt] Caso 3: $C=51$ è stato considerato perchè immediatamente sopra al $50$
Caso 2: $n_0$ lo prendo maggiore di 255 in modo da evitare i divisori del 255 perchè il maggiore determinerebbe una costante sopra il 51.
Caso 1: $C$ non rappresenta un problema in quanto $x<1$ quando $x$ è pari e $x>=256$
Corretto?
[/*:m:2lidzkwt]
[*:2lidzkwt]Avrei potuto però considerare anche la soluzione $n_0=256, C=50$ ? Del resto la disuguaglianza $f(x)<=Cg(x)$ non parla di minore stretto.
[/*:m:2lidzkwt]
[*:2lidzkwt] Posso considerare la mia soluzione corretta $C=50/9*255$ per qualunque $x>0$ ?
[/*:m:2lidzkwt]
[*:2lidzkwt] Si dice:
quando la funzione g non è nulla (come in questo caso)
Che significa? Per come è definita la funzione g(x) quando $x=0$ $x^3=0$ no ?
Immagino si intenda che non è definita in $x=0$ quando si parla di rapporto $f(x)/g(x)$ giusto ?
[/*:m:2lidzkwt]
[*:2lidzkwt] C'e' una strategia che mi consente di capire quale sia la funzione da prendere in esame come $g(x)$ e $f(x)$ ?[/*:m:2lidzkwt][/list:o:2lidzkwt]
Renditi conto che non hai nemmeno elencato tutti i divisori di 255, il che è una questione di Aritmetica da scuole medie…
La fretta, la benedetta fretta di arrivare al dunque, devia il focus altrove e ti scava il piede nella fossa.
Non ho scuse !!! Mi autoflagellerò
Grazie per la tua spiegazione super chiarissima.
Qualcuno potrebbe sciogliere i miei dubbi?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo