Ştiri:

Vă rugăm să citiţi Regulamentul de utilizare a forumului Scientia în secţiunea intitulată "Regulamentul de utilizare a forumului. CITEŞTE-L!".

Main Menu

complexitatea functiilor

Creat de ulita, August 17, 2010, 12:13:19 PM

« precedentul - următorul »

0 Membri şi 1 Vizitator vizualizează acest subiect.

ulita

salut , stiti sa dati exemple de functii ce apartin multimilor O(sin n), Ω(sin n), Θ(sin n) ? ???

AlexandruLazar

Funcţiile trebuie să aparţină tuturor celor trei mulţimi? Sau, pe rând, câte un exemplu pentru fiecare?

În primul caz, întrucât e vorba de relaţii asimptotic slabe, exemplul cel mai bun este chiar sin n.

Edit: dacă nu eşti foarte bine lămurit(ă) care-i treaba cu complexitatea, o explicaţie succintă dar foarte bună găseşti în Introducere în Algoritmi -- Cormen, Leiserson, Rivest.

ulita

#2
Da asa e pentru O(sin n ) pot sa dau ca exemplu sin (n) ,insa pentru teta si omega trebuie sa caut functii care sa  satisfaca conditiile :
pentru    Θ(sin n): c1 g(x) < f(x) < c2 g(x)
pentru     Ω(sin n): 0<cg(x) <f(n)

Posibil ar merge o schimbare de variabila pentru n , dar inca nu imi dau seama cum sa gasesc astfel de functii.

Da sigur ca pentru functii diferite trebuie sa obtin acele coplexitati :)

AlexandruLazar

#3
Sigur aşa e definiţia? Pentru că dacă da, cartea pe care o foloseşti (sau profesorul care predă cursul) foloseşte o notaţie nestandard. Cele cu litere mari sunt margini asimptotic slabe, adică relaţiile sunt de tipul:

[tex]\Theta(sin(n)): c_1 sin(n) \leq f(x) \leq c_2 sin(n) [/tex]

(deci cu mai mic sau egal) -- caz în care cred că e destul de clar că pentru [tex]c_1 = c_2 = 1[/tex] relaţia e satisfăcută.

De asemenea, funcţiile asociate unui semnal modulat în amplitudine pe o purtătoare sinusoidală satisfac relaţiile de acest tip (vezi http://en.wikipedia.org/wiki/Amplitude_modulation#Example:_double-sideband_AM -- te interesează [tex]y(t)[/tex] de acolo, dar e util să vezi cum au ajuns la el ca să poţi face demonstraţia). E drept însă că asemenea funcţii sunt doar O(sin n).

Verifică încă o dată definiţiile ca să fiu eu liniştit, nu de alta dar dacă marginile sunt asimptotic tari (adică, cu [tex]<, >[/tex] în loc de [tex]\leq, \geq[/tex] nu cred că există funcţii care să se afle simultan în toate cele trei mulţimi.

ulita

Da ai dreptate asa e cu <= si >=

O(g(n) ) : 0<=f(n)<=cg(n)
Θ(g(n))  : 0<=c1g(n)<=f(n) <=c2g(n)
Ω(g(n))  : 0<=cg(n)<=f(n)

ulita

daca folosesc f(n) =3 atunci voi avea  0<=c*sin(n)<=3 ... daca iau c=1 sin(n)<=3 Adevarat , iar pentur 0<=sin(n) nu prea imi iese pentru ca e o functie periodica.. sau gresesc ceva ?