4

Kolokwium ze Złożoności Obliczeniowej 17 kwietnia 2003

|    1 2-2 1 Wypełnij poniższą tabelką w taki sposób, żeby: a) w każdej z rubryk znalazła się dokładnie jedna z

funkcji lgn + 2^^lKn,    , (n + 1) lg³ n, Xfiⁿ, 2003. (|)^lgn, n^{1 2}; 6) w każdej z rubryk znalazła się funkcja,

która rośnfe szybciej ocl fumccji umieszczonych w poprzednich (znajdujących się na lewo) rubrykach.

1003

^^vv|

i U"

1^"

Uvm) {<£ z,

rt + luA n ^a

Następnie podaj przykład funkcji, która

rośnie wolniej od każdej z powyż- ^_it szych funkcji oraz szybciej niż lg lg n oWjy

a)

rośnie szybciej od każdej z powyższych funkcji oraz wolniej niż n²ⁿ

Jeżeli taka funkcja nie istnieje, napisz ”nie istnieje”.

| j 6-3 | Niech B, C oraz D będą następującymi procedurami.

function B( n: word ): word;

var i, j: word; begin

i := n; j := 1; while (i > j) do begin i :=i/2; j := 2 * j; end;

B := max{i,y}; end;

function C( n: word ): word;

var i: word; begin

if (n < 1) then C := 0 else begin i := 1;

while (i*i <n) do i := i + 1;

C:=C7(i-l) + l;

end;

end;

function D( n: word ): word;

var i: word; begin

if (n < 1) then D := 0 else begin

i n)

while (i * i > n) do i := i — 1; D:=i) end; end;

Uzupełnij poniższe zdania, korzystając tylko ze znaków n, £(n), +, —, •, /, lg, [, J, [,],(,) oraz dowolnych stałych, gdy n <

B{n) =

C(n) = ©

gdy n >

D{n) =

	gdy n <
	gdy n >

X* = ©

X* = ©

X* = © X* = © X* = © X* = ©'^:

Jeżeli X* jest pesymistyczną złożonością obliczeniową procedury B, to

Jeżeli X* jest pesymistyczną złożonością obliczeniową procedury C, to

Jeżeli X* jest pesymistyczną złożonością obliczeniową procedury D, to

Jeżeli X* jest optymistyczną złożonością obliczeniową procedury B, to

Jeżeli X* jest optymistyczną złożonością obliczeniową procedury C, to

Jeżeli X* jest optymistyczną złożonością obliczeniową procedury D, to

Jeżeli OT* jest pesymistyczną złożonością pamięciową procedury B, to

Jeżeli OT* jest pesymistyczną złożonością pamięciową procedury C, to

Jeżeli OT* jest pesymistyczną złożonością pamięciową procedury D, to

Jeżeli OT* jest optymistyczną złożonością pamięciową procedury B, to

Jeżeli OT* jest optymistyczną złożonością pamięciową procedury C, to

Jeżeli OT* jest optymistyczną złożonością pamięciową procedury D, to

OT* = ©

OT* = ©

OT* = ©

- A

OT* = ©

OT* = ©

A

OT* = ©

Strona 2

1

   | 5-3~) Uzupełnij poniższe zdania, korzystając tylko ze znaków r, +,    ■. /, lg, y/~, [, J, [,],(,) oraz dowolnych

2

stałych.