Studia dzienne, 7go lutego 2005
Nazwisko............................................. Nr studenta............Nr grupy.........
Zadanie l(lOpunktów) Wyobraźmy sobie "nieskończona" strukturę danych S przechowująca liczby całkowite. Jest ona wyposażona w operację get(i), gdzie i może być dowolnie dużą liczbą naturalną; operacja S.get(i) zwraca liczbę całkowitą przechowywaną w strukturze S "pod indeksem" i, przy czym:
1) pod każdym indeksem znajduje się dokładnie jedna liczba całkowita.
2) przechowywane liczby są posortowane rosnąco, tzn. jeśli i < j, to S.get(i)<S.get(j),
3) pierwsza liczba w strukturze (tzn. S.get(O)) jest ujemna.
4) operacja S.get(i) ma koszt 0(1) dla dowolnego naturalnego i.
Opis zadania: Przy powyższych założeniach opracuj algorytm find(), możliwie najszybszy(asymptotycznie), który odnajduje najniższy indeks w strukturze S, pod którym znajduje się liczba dodatnia (tzn. minimalne i, takie że get(i)>0). Jedynym środkiem do sprawdzania zawartości pod indeksem i jest operacja S.get(i).
(a) Podaj możliwie krótki opis algorytmu find().
(b) Napisz pseudokod algorytmu find().
(c) Oszacuj złożoność czasową algorytmu, przy czym dokładnie opisz składniki złożoności, jeśli algorytm składa się z kilku faz. Nie zapomnij precyzyjnie określić co stanowi argument funkcji złożoności (czyli co jest parametrem, od którego zależy złożoność)
Przykład:
S: get(O) = -3, get(l ) = -1, get(2) = 0, get(3) = 3, get(4) = 10,... algorytm S.find(), powinien zwrócić liczbę 3.