Pages: [1]   Go Down
Print
Author Topic: Notazione O-grande  (Read 984 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« on: 07-11-2010, 12:27:03 »

In un esercizio mi p capitato di dover dire se è vera questa relazione:

6nlog3(n)+7n3log(n) = O(4n3log(n))

Lo è, ma non mi spiego il perchè. La prima parte dovrebbe essere \leq dell' altra.
A me risulta che sia maggiore....
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
dani89
Apprendista Forumista
**
Offline Offline

Posts: 254



« Reply #1 on: 07-11-2010, 15:37:47 »

In un esercizio mi p capitato di dover dire se è vera questa relazione:

6nlog3(n)+7n3log(n) = O(4n3log(n))

Lo è, ma non mi spiego il perchè. La prima parte dovrebbe essere \leq dell' altra.
A me risulta che sia maggiore....
ma sarebbe n^3? cmq le costanti prima delle funzioni non contano, forse tu credi che sia maggiore perchè a sinistra c'è il 7 e a destra il 4 ma non le costanti si ingorano quindi rimangono n3log(n)<=n3log(n) che è vero ovviamente
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #2 on: 07-11-2010, 15:43:05 »

Si ma scusa io non ho solo:

n3log(n)\leq n3logn

Ma ho:

nlog3(n)+n3log(n)\leq n3logn

Il primo membro non sarebbe uguale al secondo ma con qualcosa in più, quindi maggiore?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
dani89
Apprendista Forumista
**
Offline Offline

Posts: 254



« Reply #3 on: 07-11-2010, 17:49:19 »

no perchè devi considerare solo la più grande fra tutte le funzioni, nlog3n è minore di n3logn quindi lo puoi anche ingorare, così come puoi ingorare le costanti, il confronto quindi rimane solo fra n3logn e n3logn che sono uguali quindi è vera!
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #4 on: 07-11-2010, 18:22:41 »

Partendo dal presupposto che

f(x)\ \in\ O (g(x))\mbox{ per }x\to\infty
se e solo se
\exists x_0,\ \exists M\ >\ 0\mbox{ tale che } |f(x)|\ \le\ M |g(x)|\mbox{ per }x>x_0

allora e' ovvio che

6n\log^3 n + 7n^3\log n\ \in O(4n^3\log n)

in quanto

 |6n\log^3 n + 7n^3\log n\|\ \le\ M |4n^3\log n| \mbox{ per }M \mbox{ e }x_0 \mbox{ sufficientemente grandi }
« Last Edit: 07-11-2010, 18:24:35 by shiny » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #5 on: 07-11-2010, 20:35:09 »

Ah bene, quindi si considera la funzione più grande, allora funziona, grazie ad entrambi  ok
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: