4

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) lg3 n, Xfin, 2003. (|)lgn, n1 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ż n2n

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.


Wyszukiwarka

Podobne podstrony:
Kolokwium ze Złożoności Obliczeniowej 17 kwietnia 2003
Kolokwium ze Złożoności Obliczeniowej 17 kwietnia 2003 Kolokwium ze Złożoności Obliczeniowej 17 kwie
Kolokwium ze Złożoności Obliczeniowej 26 kwietnia 2003 Kolokwium ze Złożoności Obliczeniowej 26 kwie
Kolokwium ze Złożoności Obliczeniowej 26 kwietnia 2003 8-4
Kolokwium ze Złożoności Obliczeniowej_17 kwietnia
Resize of* Kolokwium ze Złożoności Obliczeniowej Algorytmów Wypełnij 2-1
Resize of I Kolokwium ze Złożoności Obliczeniowej Algorytmów ..    • • • • o 5-3
Resize of: Kolokwium ze Złożoności Obliczeniowej Algorytmów 1 czerwca 2002 Nazwisko Imię Ocena [ Uwa
Resize of Kolokwium ze Złożoności Obliczeniowej Algorytmów Nazwisko Imięyc 1 czerwca 2002 Ocena [ U
Resize of+ Kolokwium ze Złożoności Obliczeniowej Algorytmów 1 czerwca 2CC2
Resize of; Kolokwium ze Złożoności Obliczeniowej Algorytmów 1 czerwca 2002

więcej podobnych podstron