pto kolo1 2 05

3. Określ złożoność obliczeniową procedury X umieszczając ją w jednej z następujących klas: subliniowa, wielomianowa, superwielomianowa, wykładnicza, superwykładnicza. Podaj czas działania (w sensie symbolu 0) innej, asymptotycznie najszybszej procedury wyliczającej tę samą funkcję X. Zakładamy, że jej kod nie może zawierać operacji arytmetyki zmiennoprzecinkowej. Odpowiedzi uzasadnij.

function Jć(«:integer):integer;

constprimes: arrayfl ...6] of integer = {2,3,5,7,11,13};

begin

if n<=6 then return primes[ri]

else return \X(n—\)+2*X(n-2)+3*X(n-3)-5*X(n—4y-7*X(n-5)-] 1 *X(n-6)\ mod 102;

end;

Uwaga: Oszacuj T(n) z dołu i z góry.

20

20

4. Dana jest procedura funkcyjna

function D(«: integer): integer;

var /,.s: integer;

begin

s:=0;

for z:=l to n-1 do s:=s+D(i); return s;

end;

Wyprowadź wzór na pesymistyczną złożoność czasową i pesymistyczną złożoność pamięciową tej procedury.

15

5. Uzupełnij poniższy kod tak, aby Twój algorytm miał złożoność taką jak na rysunku.

procedurę Odpowiedz(    );

begin

end;