PDA

Visualizza la versione completa : [ALGORITMO] Upper bound e Lower bound


lorenzcollixx
02-07-2012, 12:00
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
02-07-2012, 12:34
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. :ciauz:

Kaamos
02-07-2012, 13:04
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
02-07-2012, 13:17
Grazie Kaamos!!!Molto esauriente!!!!;)

MItaly
02-07-2012, 14:55
Occhio che sono tutte definizioni asintotiche "prese a prestito" dall'analisi matematica, e normalmente si considerano per n->infinito.

Loading