pto kolo1 1 05

tołPA-

100

Nazwisko i imię

03.12.2005.

Grupa/rok.

sąsiad lewy

sąsiad prawy

Czas trwania testu: 90 minut Nazwiska proszę pisać CZYTELNIE literami DRUKOWANYMI_

UWAGA: Obok każdego pytania napisz końcowe rozwiązanie. Tok rozumowania prowadzącego do tego rozwiązania załącz _na oddzielnej PODPISANEJ kartce_

20

1. Zakładamy, że poniższa funkcja Xjest wywoływana z argumentem będącym liczbą naturalną.

function Jf(«:integer):integer; begin

if n= 1 or n=2 return exp(«*ln2) else return X(X (X (n-2) div 2) div 2)+4;

end;

-    Ile wynosi X(n)7

Asymptotyczny czas wykonywania się funkcji A (w zależności od argumentu n) należy do: -Q(n^{1 2})nć>(1.5")

-    Q(1.5")n£>(2")

-    Q(2")nO(Ti")

-    Q(n>0(n!)

Właściwą odpowiedź podkreśl, a odpowiedź uzasadnij.

25

1

Oszacuj asymptotyczną liczbę kroków jako funkcję n poniższej procedury. Ponadto podaj jej klasę złożoności obliczeniowej (procedura: subliniowa, wielomianowa, superwielomianowa, wykładnicza, superwykładnicza).

procedurę A(n:integer); var ij,k\ integer; begin

for /:=1 to n do begin

r-=2;

while j<i do begin

2

7':=2*/;

for k:=1 to j do;

end;

end;

end;