Visualizzazione dei risultati da 1 a 7 su 7
  1. #1
    Utente di HTML.it
    Registrato dal
    Feb 2011
    Messaggi
    2

    Notazioni Asintotiche - Tasso di crescita di funzioni

    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 ) ?

  2. #2
    Utente di HTML.it
    Registrato dal
    Jul 2008
    Messaggi
    1,326

    Re: Notazioni Asintotiche - Tasso di crescita di funzioni

    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.
    every day above ground is a good one

  3. #3
    Utente di HTML.it
    Registrato dal
    Feb 2011
    Messaggi
    2
    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.

  4. #4
    Utente di HTML.it
    Registrato dal
    Feb 2011
    Messaggi
    2
    Ciao YuYevon,
    mi farebbe comodo anche solo una tua impressione soprattutto sulla seconda.

  5. #5
    è 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 ...

  6. #6
    Utente di HTML.it L'avatar di Pastore12
    Registrato dal
    Oct 2008
    Messaggi
    1,051
    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

  7. #7
    Utente di HTML.it
    Registrato dal
    Jul 2008
    Messaggi
    1,326
    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.
    every day above ground is a good one

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.