AISDE - Kolokwium

23 listopada 2009 - godz. 17

Podpis:

Zadanie 1 (5p)

Dane: liczba całkowita nieujemna n Wynik: liczba całkowita s function s = alg(n) s=0;

while s<n s=s+1; end

Dla podanego algorytmu określić wzorami analitycznymi s(n), złożoności czasowe t=(n), t+(n), t<(n), jeśli operacją dominującą jest odpowiednio przypisanie, dodawanie i porównanie. Niech m będzie długością bitową n i t+(m)= 0(g(m)). Określić najprostszą postać g(m).

t-(n)=.........,(4.±d..................................(lp)

t+(n)=.....................................................(lp)

t<(n)=.........D.±d...................................(lp)

g(m)=....................................................(2p)

S[h)~ h &f>)

Zadanie 2 (5p)

Pewien algorytm ma złożoność czasową:

n\ogndlal<n<\6

t(n) = \

[64 + 2{n -16) dla n> 16

Określić takie najprostsze g(n), takie że t(n)= 0(g(n)). Udowodnić prawdziwość tego oszacowania asymptotycznie dokładnego z definicji.

8(ti)=..........M.............._f.....

Dowód:.^ ?oUts^-&-c Z C. i o hi^t £

fajrl c_ĄyO _f c₂ ->ó ₍Ho> Qo c₂ lo

C_A ^ 2. ( c 2 = 3 2v\ Źz 2 (A -V 0) cUOs-' t/\ 'y &

^ 2 4 v\y/^2-