2

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

8-4 | Niech A, B oraz C będą następującymi procedurami.

function A( n: integer ): word;

var ?;, j, k: word; begin

k := 0;

for i := 1 to n do

for j := 1 to n do begin

k := max{fc,j}; j := i * j; end;

A := k\ end;

function B( n: integer ): word; begin

if (n = 0) then

B :=0

else if (n > 0) then

B := B{n/2) + 1 else

B := B(n + 1) + 1;

end;

function C{ n: word ): word; begin

if (n < 2) then C := n else if (2|n) then C := C(n/2) else C := C{{n/2) * Pow(2,n)); end;

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

gdy n <

B(n) = -

gdy n <

C{n) = <

gdy n <

gdy n >

Wskazówka: Zmienna typu integer może przyjmować dowolne wartości całkowite; zmienna typu word może przyjmować dowolne nieujemne wartości całkowite.

| | 2-1 | Uzupełnij poniższe zdania, korzystając tylko ze znaków r, +, —, •, /, lg, y/~, [, J, [,],(,) oraz dowolnych

stałych.

Jeżeli T* jest pesymistyczną złożonością obliczeniową pro-cedury A. to

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

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

Jeżeli T* jest optymistyczną złożonością obliczeniową procedury A, 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

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

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

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

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

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

Jeżeli SOI* 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

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

Wskazówka: £L₂ = e(j^).

1 | 5-2 | Niech G,H: N->N będą funkcjami danymi wzorem

G(n) =

2G{n - 2) - G(n - 3) + 1

gdy n < 3 gdy n > 3

H{n) =

2 gdy n = 1

H(n - 1) ■ H(n - 2) ■... • H(l) gdy n > 1

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

Dla każdego n > 4 zachodzi równość

G(n) =

Dla każdego n > 2 zachodzi równość

H(n) =

| | 2-1

rubrykach.

Które z poniższych zdań są prawdziwe? Wypełnij poniższą tabelkę, stawiając krzyżyk w odpowiednich

Tak Nie

ZUZI T(0) = 1, T(n) = 2T([* j) + l_gn =* _T(n) = O(^)

_ T(0) = 1, T(n) = T(n - 1) + T(^J) => T(n) = Q(n³)

Strona 2