Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Funzione polinomialmente più grande (o veloce)
423 views
Skip to first unread message
tip&tap
Nov 25, 2014, 6:35:35 PM11/25/14
to
Nei libri che ho consultato quest'espressione salta fuori
all'improvviso, in maniera quasi gergale, senza che sia definita in modo
chiaro.
Se non ho capito male significa che f(n) è polinomialmente più veloce (o
più grande) di g(n) se esiste un d tale che f(n)<=C*g(n)^d, con C
costante positiva.
Però vedo che si parla anche di "logaritmicamente più grande". Ad es.
"n*log(n) è logaritmicamente più grande di n", il che mi fa pensare che
il concetto si possa generalizzare e tirare fuori ulteriori espressioni
come fattorialmente più grande, etc.
Qual'è il concetto generale, e in base a che criterio si stabilisce che
una funzione sia polinomialmente, fattorialmente, logaritmicamente più
veloce rispetto ad un'altra?
Ciao
all'improvviso, in maniera quasi gergale, senza che sia definita in modo
chiaro.
Se non ho capito male significa che f(n) è polinomialmente più veloce (o
più grande) di g(n) se esiste un d tale che f(n)<=C*g(n)^d, con C
costante positiva.
Però vedo che si parla anche di "logaritmicamente più grande". Ad es.
"n*log(n) è logaritmicamente più grande di n", il che mi fa pensare che
il concetto si possa generalizzare e tirare fuori ulteriori espressioni
come fattorialmente più grande, etc.
Qual'è il concetto generale, e in base a che criterio si stabilisce che
una funzione sia polinomialmente, fattorialmente, logaritmicamente più
veloce rispetto ad un'altra?
Ciao
Jasmine
Nov 26, 2014, 2:03:07 PM11/26/14
to
On Wed, 26 Nov 2014 00:35:22 +0100, tip&tap
<tip-n...@tap-no-spam.com> wrote:
>Qual'è il concetto generale, e in base a che criterio si stabilisce che
>una funzione sia polinomialmente, fattorialmente, logaritmicamente più
>veloce rispetto ad un'altra?
non so,però la distanza tra due funzioni f e g continue
<tip-n...@tap-no-spam.com> wrote:
>Qual'è il concetto generale, e in base a che criterio si stabilisce che
>una funzione sia polinomialmente, fattorialmente, logaritmicamente più
>veloce rispetto ad un'altra?
definite su un intervallo di R a valori in R,
dato x qualunque appartenente all'intervallo
si puo' misurare nella norma infinito
d(f,g)=||f-g||= sup|f(x)-g(x)|
x
essendo che la norma infinito
induce una metrica nello spazio
delle funzioni continue, forse
"la velocità" può essere definita
considerando questa metrica?
La tua mi sembra un'ottima domanda, sorry se rispondo
con un'altra domanda :(
speriamo che qualcuno risponda (magari ad entrambi)
ciao, Jasmine
tip&tap
Nov 27, 2014, 1:40:39 PM11/27/14
to
> essendo che la norma infinito
> induce una metrica nello spazio
> delle funzioni continue, forse
> "la velocità" può essere definita
> considerando questa metrica?
Il tuo mi sembra uno spunto interessante, penso che ci sia un modo
> induce una metrica nello spazio
> delle funzioni continue, forse
> "la velocità" può essere definita
> considerando questa metrica?
preciso per inquadrare il concetto ma lo vedo utilizzare in modo molto
spensierato, come se fosse addirittura intuitivo.
Poiché intuitivo non è, come tutte le cose che non vengono definite in
modo chiaro, si rischia di fraintendere senza neppure rendersi conto.
Naturalmente chiunque conoscesse una definizione, se me la indicasse mi
farebbe felice :-)
A quello che ho capito, f(n)=n^2 è "polinomialmente più veloce" di
g(n)=n. Se non è così prego di smentirmi. Questo per quanto riguarda il
"più veloce polinomialmente".
Quando dico più veloce intendo in termini asintotici, nel senso che f(n)
prima diverge a +oo più rapidamente rispetto a g(n).
Cosa potrebbe significare invece che una funzione è logaritmicamente più
veloce?
f(n) = log(n)*n più veloce di g(n)=n ?
f(n) = log^2(n) sarebbe invece *polinomialmente* più veloce di g(n)=log(n) ?
f(n) = log(n)*n^2 sarebbe polinomialmente e logaritmicamente più veloce
di g(n)=n ?
Ed esponenzialmente?
f(n) = 3^n più veloce di g(n)=2^n ?
Fattorialmente?
f(n)=2*n! più veloce di g(n)=2 ?
> La tua mi sembra un'ottima domanda, sorry se rispondo
> con un'altra domanda :(
> speriamo che qualcuno risponda (magari ad entrambi)
Mi piacerebbe capire se gli esempi che ho portato hanno un senso, per
vedere se è possibile approcciare quantomeno intuitivamente la questione.
Se gli esempi fossero corretti, allora si potrebbe dedurre che, in
riferimento a questa tabella...
http://it.wikipedia.org/wiki/O-grande#Ordini_di_funzioni_fra_i_pi.C3.B9_comuni
...presa in considerazione una f(n), laddove si avesse una seconda
successione g(n) tale che
lim f(n)/g(n) = +oo oppure g(n)=o(f(n)) (o-piccolo)
n->oo
allora f(n) sarebbe più veloce in termini polinomiali, logaritmici,
fattoriali ove la f(n) esprimesse i termini della g(n) in forma di
funzione polinomiale, logaritmica, fattoriale, etc.
Mi scuso per il linguaggio impreciso e per le inesattezze, ma spero che
il senso si sia capito.
Ciao
Jasmine
Nov 27, 2014, 4:52:39 PM11/27/14
to
On Thu, 27 Nov 2014 19:40:16 +0100, tip&tap
<tip-n...@tap-no-spam.com> wrote:
>
>A quello che ho capito, f(n)=n^2 č "polinomialmente piů veloce" di
>g(n)=n.
va ad infinito piu' rapidamente
e,se passo al limite
va ad infinito come inf^2 anzichč inf^1
l'espressione polinomialmente
piu' veloce non l'ho incontrata
e quindi non so risponderti in merito
>f(n) = log(n)*n piů veloce di g(n)=n ?
perchč log(n) cresce ed č definita solo per valori
positivi, se n appartiene ad N
n*log(n) va a +inf piu' rapidamente di n
ciao, Jasmine
<tip-n...@tap-no-spam.com> wrote:
>
>A quello che ho capito, f(n)=n^2 č "polinomialmente piů veloce" di
>g(n)=n.
va ad infinito piu' rapidamente
e,se passo al limite
va ad infinito come inf^2 anzichč inf^1
l'espressione polinomialmente
piu' veloce non l'ho incontrata
e quindi non so risponderti in merito
>f(n) = log(n)*n piů veloce di g(n)=n ?
perchč log(n) cresce ed č definita solo per valori
positivi, se n appartiene ad N
n*log(n) va a +inf piu' rapidamente di n
ciao, Jasmine
0 new messages