8 (1718)

ffiipL/a^ brzmi definicja O-notacji? Podać i udowodnić trzy dowolne własności rzęc funkcji.

Definicja O-notacji:

Dana jest funkcja f\n) i jest rzędu co najwyżej g(n)

f(n) = 0(g(n))    £

Dła-ka.żags3 należące do zbioru liczb rzeczywistych i ooftśmieje takie należące do zbioru liczb naturalnych , że ćia każdego o>no

|fln)[c= c Lg(n)|

Wyjaśnienie definicji :

szacujemy szybkość wzrostu jednej funkcji przez drugą która jesr jakąś funkcją podstawową. jasności O-noiacii $ Z; f(n),g(n), a>0, b-dowolne

c*g(n)+b) OfgfnJJ

dowód;

^Łep»*i

d o uod

f(nf<X2i‘g(n)+b)^=>!SLnieje takie „c” należące do zbioru liczb rzeczywistych i istnieje takie rv należące do zbioru liczb naturalnych taki że dla każdego n=>no f(n)<= ć(a*g(n}+b): i j dla b<*^r0 f(n)<- c*a*g(n) + c¹b<- c* a* g(n) (przyjmując c*a -■ e }' ce e¹g(n) cnd.

2) dla b>0

rTn)<= c*a*g(n) + c*b<= c*a*g(n) + c*b¹g(n)(ponieważ g(n) jest rosnące to od pewnego „n" g(n)>0) (a - b)*c*g(n) {przejmując c*(łH-b) - e } = e*g(n) c.n.d.

W ^regT1J-⁵ dla sumy Z; f(n)=0(s(n)) i g(n>=0(t(n)) T: f(n)^g(n)= G(max(s(n),t(n))) D:

1)    f(n)=0(s(n)}=>istnieje takie „.cf należące do zbioru liczb rzeczywistych i istnieje takie n» zbiom liczb naturalnych

taki ze dla każdego n=>nj f(n)<= Cj(s(n))

2) I(n)ⁱ=0(t(n))=>istnieje takie „cd* należące do zbioru liczb rzeczywistych i istnieje takie rn

na lezące do

nalezace dc zbioru liczb naturalnych

taki że dla każdego n=>n_: f[n)<= c₂(t(n))

f(n)-^g(n) Cj(s(ji))-rCł(t(n)) <=    { przyjmują^Cj-rCj)- c } - e¹max((s(n),t(n))

istnieje takie „e** należące do zbioru liczb rzeczywistych i istnieje takie n₃ należące do zbioru liczb naturalnych taki ze dla każdego n=>max(n^ -hw }=ti₃    C3Tnax(s(D)₁t(Q))

f(n)+g(n)= 0(max(s(n),t(n)))c.n.cL

fj rezulą iloczynów ₎

Z: ftn)=0(s(n)) i g(n)=0(t(n))

i: ąn)"g(n}= 0(s(n)*:(n))    ;

D:

1)    f(ny^ciO(s(n))^>ismieje takie „cf* należące do zbioru liczb rzeczywistych i istnieje takie ni należące do

zbioru liczb naturalnych^ >    ^

taki że dla każdego n=>nj ąa)<= c_t(s(n))

2) (Tn)=0(t(n)k=^:>istnieje Lakic „Ci” należące do zbioru liczb rzeczywistych i istnieje takie n₂ należące do zbioru liczb naturalnych.

taki ze dla każdego n=>,n₂ f(n)<= c₂(t(n))

1