O grande e valutazione della complessità tra funzioni

Messaggioda zio_mangrovia » 14/09/2019, 11:41

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
Ultima modifica di zio_mangrovia il 14/09/2019, 13:57, modificato 2 volte in totale.
zio_mangrovia
Average Member
Average Member
 
Messaggio: 983 di 990
Iscritto il: 13/06/2016, 18:42

Re: O grande e valutazione della complessità tra funzioni

Messaggioda gugo82 » 14/09/2019, 12:23

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. :wink:
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Moderatore globale
Moderatore globale
 
Messaggio: 22333 di 22615
Iscritto il: 13/10/2007, 00:58
Località: Napoli

Re: O grande e valutazione della complessità tra funzioni

Messaggioda zio_mangrovia » 14/09/2019, 14:19

gugo82 ha scritto: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?
zio_mangrovia
Average Member
Average Member
 
Messaggio: 984 di 990
Iscritto il: 13/06/2016, 18:42

Re: O grande e valutazione della complessità tra funzioni

Messaggioda gugo82 » 14/09/2019, 15:14

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$. :roll:

Allora, ragiona. Cosa ti dice la definizione?
Cosa devi fare per stabilire se $f = text(O)(g)$ intorno a $oo$?
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Moderatore globale
Moderatore globale
 
Messaggio: 22336 di 22615
Iscritto il: 13/10/2007, 00:58
Località: Napoli

Re: O grande e valutazione della complessità tra funzioni

Messaggioda zio_mangrovia » 14/09/2019, 15:25

Intorno $\infty$ la funzione $g$ deve assumere valori più grandi rispetto a quelli di $f$ cioè :

$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
Average Member
Average Member
 
Messaggio: 985 di 990
Iscritto il: 13/06/2016, 18:42

Re: O grande e valutazione della complessità tra funzioni

Messaggioda gugo82 » 14/09/2019, 15:56

zio_mangrovia ha scritto: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 ha scritto:
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 ha scritto: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 ha scritto:[…] $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?
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Moderatore globale
Moderatore globale
 
Messaggio: 22337 di 22615
Iscritto il: 13/10/2007, 00:58
Località: Napoli

Re: O grande e valutazione della complessità tra funzioni

Messaggioda zio_mangrovia » 14/09/2019, 16:36

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...
Ultima modifica di zio_mangrovia il 14/09/2019, 16:58, modificato 1 volta in totale.
zio_mangrovia
Average Member
Average Member
 
Messaggio: 986 di 990
Iscritto il: 13/06/2016, 18:42

Re: O grande e valutazione della complessità tra funzioni

Messaggioda gugo82 » 14/09/2019, 16:45

Ora stai scrivendo il contrario di quello che avevi scritto sopra… :roll:
Decidi: cosa vuoi studiare prima? Che $f = text(O)(g)$ oppure che $g = text(O)(f)$?
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Moderatore globale
Moderatore globale
 
Messaggio: 22338 di 22615
Iscritto il: 13/10/2007, 00:58
Località: Napoli

Re: O grande e valutazione della complessità tra funzioni

Messaggioda zio_mangrovia » 14/09/2019, 17:00

corretto adesso, questi f e g mi stanno facendo perdere la mia identità ! :-D
partiamo dall'ultima affermazione da me corretta se non ti dispiace... un aiuto please?
zio_mangrovia
Average Member
Average Member
 
Messaggio: 987 di 990
Iscritto il: 13/06/2016, 18:42

Re: O grande e valutazione della complessità tra funzioni

Messaggioda gugo82 » 14/09/2019, 19:11

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…
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Moderatore globale
Moderatore globale
 
Messaggio: 22341 di 22615
Iscritto il: 13/10/2007, 00:58
Località: Napoli

Prossimo

Torna a Analisi matematica di base

Chi c’è in linea

Visitano il forum: Nessuno e 6 ospiti