ASD k1 11 2005 4

Zadanie 4a Niech V będzie obustronnie nieskończonym wektorem liczb naturalnych, indeksowanym liczbami z zakresu od -oo, ...,-1,0, 1, oo. Zakładamy, że:

-V[0] = 0,

- istnieje dokładnie jedna liczba całkowita n taka, że V[n] mod 2 = 1 oraz dla każdej liczby naturalnej i różnej od n zachodzi V[i] mod 2 = 0.

Dodatkowo zdefiniowano „działającą w miejscu" funkcję

int SUM(int V[], int 1, int r),

która w czasie 0(1) wyznacza sumę kolejnych elementów wektora wejściowego V od elementu o indeksie 1 do elementu o indeksie r włącznie. Zaprojektuj możliwie efektywną funkcję

int FIND(int V[]>,

która wyznaczy indeks n wektora V taki, że V[n| mod 2=1.

Polecenia:

a)    Podaj krótki słowny opis rozwiązania.

b)    Podaj pseudokod funkcji FIND()-

c)    Oszacuj złożoność czasową i pamięciową rozwiązania. Przyjmij, że operacją dominującą jest ewaluacja (obliczenie wartości) funkcji SUM().

d)    Czy złożoność twojego rozwiązania zmieni się istotnie, gdy elementy wektora wejściowego V indeksowane liczbami od -oo, ..., -1 będą uporządkowane w kolejności nierosnącej oraz gdy elementy indeksowane liczbami od 1, ..., oo będą uporządkowane w kolejności niemalejącej? Odpowiedź uzasadnij.