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 ) ?
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 ) ?
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.Originariamente inviato da GIULIOS
posso considerarla anche Θ( radice quarta di n ) ?
E a proposito della big-O notation, credo che in quel caso valga anche la little-O.
every day above ground is a good one
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.
Ciao YuYevon,
mi farebbe comodo anche solo una tua impressione soprattutto sulla seconda.
è normale che leggendo questi simboli mi è partita in testa BAD ROMANCE di Lady Gaga quasi a resettare automaticamente ciò che stavo leggendo?
Life is easy if you wear a smile ...
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?
"Ethics are to me something private. Whenever you use it as an argument for why somebody_else should do something, you’re no longer being ethical, you’re just being a sanctimonious dick-head"
Linus Torvalds
Il fattoriale non deve impressionarti dato che log(n!) si può ridurre di fatto a log(n): abbiamo infattiOriginariamente 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.
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.
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 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.
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.Originariamente inviato da Pastore12
Però ho un dubbio che maggiormente mi preme: non è fastidiosamente tecnico?
every day above ground is a good one