Niech E będzie dowolnym, niepustym zbiorem, a X jego dowolnym podzbiorem. Problem wyszukiwania polega na ustaleniu, czy dany element x należy do zbioru X. Rozwiązaniem problemu będzie algorytm, który dla dowolnego ciągu i dowolnego elementu x daje w wyniku wartość prawda wtedy i tylko wtedy, gdy c jest jednym z elementów ciągu. Zakładamy, że elementy zbioru X są umieszczone w tablicy e jako e[1], e[2], ..., e[n] i, że odpowiedź zostanie zapamiętana na zmiennej booleowskiej result.

Specyfikacja poszukiwanego algorytmu składa się z dwóch warunków: warunku początkowego wp określającego dane wejściowe i warunku końcowego wk określającego oczekiwane własności wyniku:

Rozwiązanie

Metoda: Będziemy porównywali x z kolejnymi elementami ciągu poczynając od pierwszego. Jeśli badany element ciągu jest różny od x, to kontynuujemy przeszukiwanie, a jeśli jest równy x, to kończymy postępowanie. Algorytm odpowiadający tej metodzie, nazywany algorytmem poszukiwań sekwencyjnych, jest przedstawiony poniżej. Dla uproszczenia rozważań związanych z uzasadnieniem poprawności, szukany element jest umieszczony dodatkowo na pozycji (n+1)-szej danego ciągu, e[n+1]=x. Po takiej modyfikacji ciągu e, mamy pewność, że przeglądając kolejne pozycje zmodyfikowanego ciągu, trafimy na element x.

ALGORYTM poszukiwań sekwencyjnych

Member	{

	e[n+1] := x; i := 1;	//przed wykonaniem pętli x Ï{e[1],...,e[i-1]}
	while (not x = e[i]) do	//Po sprawdzeniu i-tego elementu, x Ï{e[1],...,e[i-1] } oraz x ¹e[i]
	i := i+1	//Po zmianie wartości i, x Ï{e[1],...,e[i-1]}
	od ;
	if (i £ n) then result := true	//Jeśli pętla zatrzymała się na indeksie mniejszym od n+1, to xÎ{e[1],...,e[n]}
	else
	result := false	//Jeśli pętla zatrzymała się na indeksie równym n+1, to x Ï{e[1],...,e[n]}
	fi
}

Zauważmy, że typ elementów ciągu nie ma tu żadnego znaczenia. Jest tylko konieczne, aby struktura, w której działa algorytm, miała zdefiniowaną relację równości dla obiektów ze zbioru E.

Algorytm przegląda kolejne pozycje zmodyfikowanego ciągu i zatrzymuje się na pozycji, którą zajmuje element x. W przypadku, gdy jest to pozycja ostatnia (n+1)-sza mamy pewność, że x nie występował w danym ciągu. Przeanalizujmy dokładniej zachowanie tego programu, stosując metodę niezmienników.

Łatwo zauważyć, że formuła a = (x¹e[1] Ù ... Ù x¹e[i-1]) jest niezmiennikiem pętli "while" w tym algorytmie. Przed wykonaniem pętli, gdy jeszcze nie sprawdziliśmy żadnego elementu, a i=1, formuła a jest spełniona trywialnie. Jeśli po i-tej kolejnej iteracji stwierdziliśmy, że x ¹ e[i], to wiemy, że na żadnej z pozycji e[1],...,e[i] nie ma elementu x. W takiej sytuacji zwiększamy wartość indeksu i, zatem informacja jaką posiadamy o elementach ciągu e ma postać: (x¹e[1] Ù ... Ù x¹e[i-1]). Jeśli natomiast po i-tej iteracji stwierdzamy, że e[i] = x, to algorytm opuszcza pętlę. Jedyna instrukcja jaką pozostało wykonać, to instrukcja warunkowa, ustalająca wartość wyniku. Jeśli znaleźliśmy x na pozycji od 1 do n, to znaczy, że x jest elementem danego ciągu. Jeśli wyszliśmy z pętli z wartością i = n+1, to znaczy, że nie znaleźliśmy x w danym ciągu. Z powyższych rozważań wynika następujące twierdzenie.

Twierdzenie

Algorytm Member jest poprawnym rozwiązaniem problemu wyszukiwania, tzn. w dowolnej strukturze danych algorytm zatrzymuje się, a po jego wykonaniu prawdziwe jest zdanie
result = true wttw x Î {e[1],...,e[n]}.

Operacją, która (oprócz operacji arytmetycznych) powtarza się w tym algorytmie, jest porównywanie elementów. Koszt czasowy będziemy więc mierzyli liczbą wykonanych porównań elementów ciągu.

Oczywiście, może się zdarzyć, że element x znajduje się na pierwszej pozycji, ale może się też zdarzyć, że nie ma go w naszym ciągu. Zatem:

Ustalmy (dowolnie) strukturę danych, z której pochodzą elementy ciągu e[1],...,e[n]. Koszt średni policzymy ze wzoru:

gdzie D jest zbiorem wszystkich danych rozmiaru n, P(d) jest prawdopodobieństwem wystąpienia danych d, a t(d) jest liczbą porównań wykonanych w czasie realizacji algorytmu 1 dla danych d.

Wszystkie możliwe dane rozmiaru n można podzielić na dwie grupy: wszystkie te ciągi, do których x należy i wszystkie te ciągi, do których x nie należy. Co więcej, wszystkie ciągi rozmiaru n, w których x występuje, można poklasyfikować następująco (są to klasy abstrakcji pewnej relacji równoważności na zbiorze ciągów długości n):

Zatem zdarzenie x Î {e[1],...,e[n]} rozbija się na sumę zdarzeń x = e[i] dla i=1,2,..., n. Zauważmy jeszcze, że dla wszystkich danych z tej samej klasy zachowanie algorytmu jest takie samo, tzn. liczba wykonanych porównań będzie taka sama.

Przyjmijmy następujące uproszczenia. Niech p będzie prawdopodobieństwem zdarzenia x Î {e[1],...,e[n]} i niech prawdopodobieństwo tego, że x = e(i) będzie dla każdego i = 1,...,n takie samo. Mamy więc

Ostatecznie, średni koszt rozważanego algorytmu wyraża się wzorem :
A(n) = P(x = e[1]) ´1 + ...+ P(x = e[i]) ´ i + ... + P(x = e[n]) ´ n + (1-p)´(n+1).

Stąd, po podstawieniu P(x=e[i]) = p/n, otrzymujemy A(n) = p´(n+1)/2 +(1-p)(n+1) = n+1 - p´(n+1)/2.

Jeśli wiemy, że x należy do danego ciągu, tzn. p=1, wtedy koszt średni wyraża się funkcją: A(n) = (n+1)/2.

Koszt pamięciowy mierzymy liczbą miejsc pamięci komputera, koniecznych do przechowania danych i wyników wykonania algorytmu. W tym przypadku wynosi on n+3 (dany ciąg + zmienne pomocnicze). Koszt pamięciowy algorytmu Member jest liniowy ze względu na rozmiar danych.

Uwaga: Właściwie należałoby traktować inaczej zmienne pomocnicze arytmetyczne i zmienne służące go przechowywania obiektów zbioru E. Typu elementów zbioru E nie znamy, a przecież mogą to być skomplikowane obiekty zajmujące dużo więcej miejsca, niż prosta zmienna typu integer.

Pytanie 1: Jaka jest długość ciągu, jeżeli całkowity czas wykonania algorytmu Member dla tego ciągu i pewnego x, wyniósł 1s, a każde porównanie elementów tego ciągu zajmuje 10^-6s (koszt związany z wszystkimi innymi operacjami wykonywanymi przez algorytm zaniedbujemy)?