ASD ew( 06 2005 1

Algorytmy i Struktury Danych

Egzamin. 28 czerwca 2005, Wersja A, studia wieczorowe

Imię i nazwisko.......................................................................... Nr indeksu....

Pvtanie •	i	2		4	5	6	7	8	I
ocena						»

1. (2+2+1)

(a)    Koszt pewnego algorytmu A można oszacować przez funkcję T(n), gdzie n jest rozmiarem danych. Jeśli n jest potęgą 2, np. n=2^k, to funkcję T można przedstawić następującym równaniem rekurencyjnym:

T(2) = 1, T(2^k+l) = 2* T(2 ^k)+l.

Jaki jest koszt tego algorytmu: liniowy, kwadratowy, liniowo logarytmiczny czy wykładniczy?

(b)    Jeżeli algorytm B, którego koszt T(n) wyraża się funkcją kwadratową 2n² wykonuje na pewnym komputerze zadanie o rozmiarze 10 w czasie 10 s, to w jakim czasie ten algorytm wykona zadanie 100 razy większe?

(c)    Jeżeli wykonamy algorytm B na komputerze 100 razy szybszym, to ile czasu zajmie wykonanie zadania o rozmiarze 100?

2. (2+2+1)

Rozważmy następujący algorytm: int COTO(int y, int n){

if (n=0) then return 0 fi ; if (n=l) then return y fi;

if (n mod 2 =0) then return COTO(y+y, n 12) else return COTO(y+y, n/2)+y; fi

}

(a)    Jak zwracany wynik funkcji COTO zależy od n i y?

(b)    Oszacuj, możliwie najdokładniej, koszt czasowy tego algorytmu stosując notację O.

(c)    He razy zostanie rekurencyjnie wywołana funkcja COTO dla n=512 i y= 100?