Egzamin Algorytmy

Zadanie

■for (int i-0; i<n; i-*-*-)

(

i* <i%3--0)

A[i]-l; // (-) i* (i%6--0)

A[i]-2J // (*•)

Dany jest następujący algorytm wykonujący pewne operacje na tablicy A o rotmlarw n ^początkowo w każdej komórce tablicy znajduje się wartoić O):

For (int i«0; i<n; I-*--*-)

<

1. Jakie wartości znajdą się w tablicy A po wykonaniu algorytmu, gdy rozmiar tablicy n»Y17

2. Operacje przypisania oznaczone w komentarzu przez {“) i t**j wykonają się łącznic cn^k. iic wynosi stała c i k? Odpowiedź uzasadnić.

3. Przedstawić pseudokod algorytmu, wstawiającego do co drugiej komórki tablicy A wartoit 1 Przykładowo dla tablicy A o rozmiarze 12 wynikiem algorytmu byłby następująca tablica-.

I n I 1 ' ^ ¹ 4 1 " ¹ ' ¹

Odpowiedz na pytania:

a)    Podać definicję złożoności średniej.

b)    Czy funkcja n² jest 0(n³)?

c)    Podać regułę dla sum dotyczącą O~notacji.

d)    Jaka jest złożoność średnia wyszukiwania liniowego w przypadku pomyśl-nyiri T+(n)?

e)    Jaka jest. złożoność algorytmu Homera?

0 Podać rozwiązanie równań rekurencyjnych: T(n) = V, gdy n = 1, oraz T(n) = 2T(§) + 2, gdy n > 2, u = 2^fc, dla pewnego k.