PDA

Visualizza la versione completa : ComplessitÓ algoritmica(astenersi deboli di cuore)


MrCoc˛85
03-02-2008, 16:19
Salve a tutti.
Ho un piccolo problema: non riesco a capire il discorso della complessitÓ algoritmica, nello specifico il significato di o-grande.
Mi servirebbe una bella spiegazione for dummies, magari con qualche esempio.

Ad esempio perchŔ 50 n log n Ŕ (per essere pi¨ precisi "appartiene") O(n log n)?
Se mi si chiede di dividere un vettore di n (ad esempio n=8) elementi in O(n/log n) gruppi contenenti O(log n) elementi , in quanti gruppi devo dividerli e con quanti elementi ciascuno?

panta1978
03-02-2008, 16:29
Originariamente inviato da MrCoc˛85
Salve a tutti.
Ho un piccolo problema: non riesco a capire il discorso della complessitÓ algoritmica, nello specifico il significato di o-grande.
Mi servirebbe una bella spiegazione for dummies, magari con qualche esempio.


Partiamo dalla definizione di "O grande".

Date due successioni f(n) e g(n) [oppure due funzioni f(x) e g(x)].

Se esistono i limiti per n->+Inf di f(n) e g(n), avremo che:

=================

1) Se lim (n->+Inf) f(n)/g(n) Ŕ un valore finito (no Infinito) diverso da zero, allora si dice che f(n) e g(n) sono "confrontabili", dunque sono uno l'"O-grande" dell'altro.

Esempi:

f(n) = n^5-10n
g(n) = 25n^5+1
Se faccio f(n)/g(n), ottengo una funzione che ha come limite per n->+Inf pari a 1/25, dunque f(n) e g(n) sono confrontabili.

Attenzione, per˛. Se hai:
f(n) = sin(n)
g(n) = 2*sin(n)

f(n)/g(n) tende a 1/2, ma, siccome f(n) e g(n) NON hanno limiti a +Inf, non possono essere considerati uno l'O grande dell'altro.

==================

2) Se lim (n->+Inf) f(n)/g(n) Ŕ pari a zero, allora f(n) Ŕ "infinitamente pi¨ piccolo" di g(n), e diremo che f(n) Ŕ o-piccolo di g(n).

Esempio:

f(n) = n^5
g(n) = 10^n

Stainboy
03-02-2008, 16:30
Originariamente inviato da panta1978


http://forum.html.it/forum/faccine/d56.gif

Loading