6

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

|    | 2-2~| 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, x/2lgn + 2i ^lgn, nⁿ + lgn, (n³ + l)lg³n, £2", £2003, (§)^lgn, n^lglgn; 6) w każdej z rubryk znalazła się funkcja, która rośnie szybciej od funkcji umieszczonych w poprzednich (znajdujących się na lewo) rubrykach.

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

rośnie wolniej od każdej z powyż-

a)

szych funkcji oraz szybciej niż lglgn

b)

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

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

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

function B( n: word ): word;

var i, j: integer; begin

i := n; j := 1; while (i > j) do begin i:—i- 2; j := 2 + j; end;

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

function C( n: word ): word;

var i: word; begin

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

ż:=l;

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

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/2; D n,; end; end;

Uzupełnij poniższe zdania, korzystając tylko ze znaków n, f.(ń), +, —, •, /, lg, , [, J, [, ~|, (, ) oraz dowolnych stałych.

gdy n < gdy n >

C(n) = 0

(\ f\

		gdy n <	-
		gdy n >

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

stałych.

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

X* = 0 X* = © X* = 0 X* = 0 X, = © X* = ©

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

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

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

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

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

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

971* = © 971* = © 971* = © 971* = © 971* = © 971* = ©

Strona 2