[ALGORITMO] Upper bound e Lower bound

[lorenzcollixx]

Salve a tutti....sono alle prese con lo studio della complessità..sono arrivato all' analisi asintotica e mi sono inbattuto nella definizione di Upper bound e Lower bound e della notazione Θ..Ho queste definizioni:

Lower Bound:

f(n)=Ω(g(n)) se esistono due costanti c>0 ed n0>0 tali che f(n)>=c*g(n) con n>=n0

Upper Bound:

f(n)=O(g(n)) se esistono due costanti c>0 ed n0>0 tale che f(n)<= c*g(n) con n>=n0

Notazione Θ:

f(n)=Θ(g(n)) se esistono tre costanti c1,c2>0 e n0>0 tali che c1*g(n)>=f(n)<=c2*g(n)

Fatte le definizioni ho visto questo esempio:

f(n)=3n^2+10 
di cui:
f(n)=O(n^2) per c=4 e n0=10
f(n)=Ω(n^2) per c=1 e n0=0
f(n)=Θ(n^2)
poi dice anche che:
f(n)=O(n^3)
f(n)!=Θ(n^3)

ora io non capisco come si calcola praticamente, con i passaggi e tutto, l' Upper bound e il Lower bound ma soprattutto non capisco come si fa a dire che :

f(n)=O(n^3)
f(n)!=Θ(n^3)

Qualcuno può aiutarmi a capire???grazie

[LeleFT]

Direi che è un argomento di trattazione generale... non specifico di Java o di un linguaggio in particolare.

Sposto in "Programmazione" e lo marco come OT.


Ciao.

[Kaamos]

Nella notazione Theta che hai postato c'è un piccolo errore, hai messo un maggiore al posto di un minore (o viceversa). Ovviamente è:

0 <= c1*g(n) <= f(n) <= c2*g(n)

Quando hai una funzione, per verificare se appartene ad uno di questi insiemi di funzioni (O, Theta, Omega - in realtà ce ne sono anche altri due) basta che applichi la definizione e verifichi le disuguaglianze.

Data f(n) = 3n^2 + 10 ovviamente si vede ad occhio che è in O(n^2) ma devi dimostrarlo applicando la definizione, che è:

f(n) = O(g(n)) se esistono c > 0 t.c. f(n) <= c*g(n) per n sufficientemente grande

Quindi devi trovare i due valori di c ed n che rendono vera la seguente disequazione:

f(n) <= c*g(n)

Che è:

3*n^2 + 10 <= c*n^2

Con c = 4 e n = 10:

3*10^2 + 10 <= 4*10^2

310 <= 400

Le due costanti trovate verificano la disequazione, quindi è dimostrato che f(n) appartiene a O(n^2).

In modo analogo dimostri il lower bound (ovviamente le costanti possono essere diverse). Per la notazione Theta, non serve rifare i calcoli, perché se una funzione è sia in O(g(n)) che in Omega(g(n)) allora è anche in Theta(g(n)).

Riguardo alle ultime due righe, è semplice dimostrare (come ho fatto sopra) che f(n) è in O(n^3). Ciò che però non puoi fare è verificare che f(n) sia in Omega(g(n)), di conseguenza non puoi affermare che f(n) sia in Theta(g(n)), perché come ho già detto il limite inferiore dovrebbe coincidere con quello superiore.

[lorenzcollixx]

Grazie Kaamos!!!Molto esauriente!!!!

[MItaly]

Occhio che sono tutte definizioni asintotiche "prese a prestito" dall'analisi matematica, e normalmente si considerano per n->infinito.