Welcome, Guest. Please login or register.

Autor Subiect: complexitatea functiilor  (Citit de 4604 ori)

0 Membri şi 1 Vizitator vizualizează acest subiect.

ulita

  • Vizitator
complexitatea functiilor
« : August 17, 2010, 12:13:19 p.m. »
salut , stiti sa dati exemple de functii ce apartin multimilor O(sin n), Ω(sin n), Θ(sin n) ? ???

Offline AlexandruLazar

  • Senior
  • ****
  • Mesaje postate: 1752
  • Popularitate: +95/-17
Re: complexitatea functiilor
« Răspuns #1 : August 17, 2010, 02:15:36 p.m. »
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

  • Vizitator
Re: complexitatea functiilor
« Răspuns #2 : August 17, 2010, 02:26:48 p.m. »
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 :)
« Ultima Modificare: August 17, 2010, 02:29:40 p.m. de ulita »

Offline AlexandruLazar

  • Senior
  • ****
  • Mesaje postate: 1752
  • Popularitate: +95/-17
Re: complexitatea functiilor
« Răspuns #3 : August 17, 2010, 02:42:01 p.m. »
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:

\Theta(sin(n)): c_1 sin(n) \leq f(x) \leq c_2 sin(n)

(deci cu mai mic sau egal) -- caz în care cred că e destul de clar că pentru c_1 = c_2 = 1 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ă y(t) 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 <, > în loc de \leq, \geq nu cred că există funcţii care să se afle simultan în toate cele trei mulţimi.
« Ultima Modificare: August 17, 2010, 02:44:00 p.m. de AlexandruLazar »

ulita

  • Vizitator
Re: complexitatea functiilor
« Răspuns #4 : August 17, 2010, 02:51:04 p.m. »
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

  • Vizitator
Re: complexitatea functiilor
« Răspuns #5 : August 17, 2010, 07:10:36 p.m. »
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 ?