Pages: [1]   Go Down
Print
Author Topic: Esercizi sulle Relazioni Asintotiche  (Read 2117 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


"Quanto manca alla vetta?";"Tu sali e non pensare"


« on: 15-11-2010, 16:04:27 »

Ragazzi non ho compreso bene il perchè le seguenti relazioni asintotiche sono tutte vere(sono prese dal sistema di esercitazione):

QUI trovate l'esercizio.
Poi non ho capito un'altra cosa.... quando trovo scritto per esempio: 8=O(9log(n)) devo pensare alla definizione di O-grande e quindi vericare che f(n)<=g(n) oppure verificare l'uguaglianza e in quest'ultimo caso perchè l'uguaglianza è vera???
Grazie a tutti.
« Last Edit: 15-11-2010, 18:11:13 by soeca » Logged

"A cavallina....a cavallina.....a chi era bedda quannu  curreva" [Cit.  Dal Tenerissimo via plebiscito]
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #1 on: 15-11-2010, 17:31:15 »

O è una funzione maggiorante. Quindi dire che  8=O(9log(n)) e come dire che la funzione costante 8 sta sotto la funzione 9lg(n), cioè f(x)<=g(x) ==> 8<=9lg(n) ==> 8= O (9lg(n)).
Per questo sono tutte vere le precedenti!
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


"Quanto manca alla vetta?";"Tu sali e non pensare"


« Reply #2 on: 15-11-2010, 17:47:05 »

Ma scusa ma allora perchè si mette l'uguale se si applica solo la definizione??Che poi pensandoci bene...... questo non è quello che in Analisi si chiamava (se non ricordo male) "Abuso di notazione"??Anche perchè qui, a quanto ho capito, non chiede l'uguaglianza tra 2 funzioni proprio perchè O(g(n) ) rappresenta una classe di funzioni no??(correggetemi se sto dicendo fesserie!!  )
Logged

"A cavallina....a cavallina.....a chi era bedda quannu  curreva" [Cit.  Dal Tenerissimo via plebiscito]
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #3 on: 15-11-2010, 18:14:49 »

si è proprio quello ma lo puoi fare perchè a noi interessa un calcolo asintotico per valori di n molto grandi.
Comunque non capisco l'obbiezione sull'uguaglianza.
dire che una funzione è uguale a O di un'altra funzione e come dire che è minore uguale.
Se non ti convince prendila per buono.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Fr3d3R!K
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.463



« Reply #4 on: 15-11-2010, 18:17:18 »

Se non ti convince prendila per buono.
Parole sante!!! [Emoticon] Asd
Logged

Search Button, CODE Tag, Google & Italian language are your friends! Use Them!
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


"Quanto manca alla vetta?";"Tu sali e non pensare"


« Reply #5 on: 15-11-2010, 21:24:28 »

Quello che non mi convince è che qui non stiamo affermando l'uguaglianza tra 2 funzioni ma tra una funzione e UNA CLASSE di funzioni (nel nostro caso O(g(n) ) ..... pag 152 del nostro libro Cap 4 paragrafo 4.2.5 "Impiego della notazione O-grande" ....mi sono confuso proprio perchè li sconsiglia di fare questa cosa e qui me la ritrovo quindi non capivo come applicare la definizione.....però comunque grazie per l'aiuto....sei stato abbastanza chiaro(e soprattutto l'esempio mi è servito parecchio!!) Grazie mille.   
Logged

"A cavallina....a cavallina.....a chi era bedda quannu  curreva" [Cit.  Dal Tenerissimo via plebiscito]
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #6 on: 15-11-2010, 21:29:02 »

beh potresti vedere il simbolo di uguaglianza come l'appartenenza all'insieme di funzioni. Forse diventerebbe ancora più chiaro.
Comunque figurati non c'è di che l'importante è che hai capito.
Buon studio   
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Pages: [1]   Go Up
Print
Jump to: