Complessità algoritmica(astenersi deboli di cuore)

[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.

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]

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]

Originariamente inviato da panta1978