Notazioni Asintotiche - Tasso di crescita di funzioni

[GIULIOS]

Ciao ragazzi.

Ho una domanda precisa.

La funzione ³√n (radice cubica di n) è sicuramente Ω (radice quarta di n), posso considerarla anche Θ( radice quarta di n ) ?

[YuYevon]

Originariamente inviato da GIULIOS
posso considerarla anche Θ( radice quarta di n ) ?

Direi proprio di no. Per valere quella relazione la funzione radice cubica dovrebbe essere, oltre che OMEGA(radice quarta), anche O(radice quarta), cosa (quest'ultima) sicuramente non vera perché non vedo come possa esistere un valore di c > 0 tale che, da un certo n0 in poi, risulti sempre n^1/3 <= c*n^1/4. Insomma la funzione radice quarta da un certo punto in poi cresce sicuramente meno rapidamente della radice terza, anche se scalata per una qualsiasi costante positiva c.
E a proposito della big-O notation, credo che in quel caso valga anche la little-O.

[GIULIOS]

Ho capito, sei stato molto chiaro,grazie .

Avrei altri due dubbi che mi affliggono:

1) Ho una lista di funzioni e devo partizionarle in insiemi, rispettando la condizione
che prese due funzioni dall' insieme f(n) e g(n) vale la condizione
f(n) = teta (g(n)).

Ho gia la soluzione dell'esercizio. Ho un dubbio su questo insieme.

A={log(n!/2^n)^4, log(n!), n log(n + 2)3, 8n log 3√n}

Non ho capito perchè mette le prime due funzioni (fattoriale) nell' insieme con
le funz. di tipo n log n.

2) Ho questa funzione f(n)=(n^3+n)/(n log^2 n+log n).
A sinistra ho una lista di funzioni, devo associare alla funzione di
sopra f(n) una funzione che sia omega di f(n), ma che tra tutte quelle che
sono omega deve essere quella che cresce piu velocemente.
A destra o una altra lista dove devo prendere la funione O grande di f(n)
che cresce piu lentamente rispetto alle altre ma che rimane cmq O grande di
f(n).

Ti enuncio quelle della lista di sinistra su cui sono incerto:
omega(n^1.000001),omega(n^2/log^2 n),omega(n^2/log n),omega(n^3/2).
Le ultime due non credo siano omega di f(n), sono incerto sulle prime due !
Per O grande le funzioni sono le stesse.

[GIULIOS]

Ciao YuYevon,
mi farebbe comodo anche solo una tua impressione soprattutto sulla seconda.

[0mbra83]

è normale che leggendo questi simboli mi è partita in testa BAD ROMANCE di Lady Gaga quasi a resettare automaticamente ciò che stavo leggendo?

[Pastore12]

Normale o no non lo so, non ce l'ho fatta a leggere nulla del secondo messaggio.
Però ho un dubbio che maggiormente mi preme: non è fastidiosamente tecnico?

[YuYevon]

Originariamente inviato da GIULIOS
1) Ho una lista di funzioni e devo partizionarle in insiemi, rispettando la condizione
che prese due funzioni dall' insieme f(n) e g(n) vale la condizione
f(n) = teta (g(n)).

Ho gia la soluzione dell'esercizio. Ho un dubbio su questo insieme.

A={log(n!/2^n)^4, log(n!), n log(n + 2)3, 8n log 3√n}

Non ho capito perchè mette le prime due funzioni (fattoriale) nell' insieme con
le funz. di tipo n log n.

Il fattoriale non deve impressionarti dato che log(n!) si può ridurre di fatto a log(n): abbiamo infatti

log(n!) = log(1*2*...*(n-1)*n)

per le proprietà dei logaritmi puoi scriverlo come una somma di logaritmi:

log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)

quantità che è sicuramente O(log(n)).
Intuitivamente, seppure è vero che n! generalmente è "molto più grande" di n, è pur vero che il logaritmo "abbatte" il valore del proprio argomento, ecco perché in fin dei conti log(n) cresce più o meno come log(n!).

Se oltre a questo poi ricordi altre proprietà tipo che il logaritmo di un rapporto si può scrivere come la differenza tra il logaritmo del numeratore e quello del denominatore o anche che un eventuale esponente dell'argomento del logaritmo può essere "spostato" come costante moltiplicativa del logaritmo stesso, evidentemente puoi ricondurre i primi due alla stessa "forma" degli altri due. Non ho tempo per fare calcoli, provaci.

Originariamente inviato da GIULIOS
2) Ho questa funzione f(n)=(n^3+n)/(n log^2 n+log n).
A sinistra ho una lista di funzioni, devo associare alla funzione di
sopra f(n) una funzione che sia omega di f(n), ma che tra tutte quelle che
sono omega deve essere quella che cresce piu velocemente.
A destra o una altra lista dove devo prendere la funione O grande di f(n)
che cresce piu lentamente rispetto alle altre ma che rimane cmq O grande di
f(n).

Ti enuncio quelle della lista di sinistra su cui sono incerto:
omega(n^1.000001),omega(n^2/log^2 n),omega(n^2/log n),omega(n^3/2).
Le ultime due non credo siano omega di f(n), sono incerto sulle prime due !
Per O grande le funzioni sono le stesse.

Mi dispiace qui non mi viene nessuna idea, d'altra parte è un po' che non tratto queste cose. Hai qualche altro elemento?

Originariamente inviato da Pastore12
Però ho un dubbio che maggiormente mi preme: non è fastidiosamente tecnico?

Questo genere di domande di solito le postano in "programmazione" (in altre sezioni non so, lì capita a volte); in genere le tollerano, altre volte le chiudono perché le considerano "Off topic". E al nostro amico è andata proprio così. Per quanto "programmazione" non sembra la sezione giusta per certe domande, di sicuro altre sezioni più indicate non ce ne sono credo, quindi alla fine la domanda o la fai in OT oppure semplicemente non trova luogo su questo forum.