4962385663

• Wynik: TAK, gdy dla pewnego 1 < i < n, w = wp, NIE, w przeciwnym przypadku.

Przykład. Dane: w =' a'/ ala'/ b'' bela'/ hela!, w — bela'. Wynik: TAK.

Poniższa procedura mem sprawdza czy słowo występuje w słowniku pomiędzy słowami w_mi i w_m2.

procedura mem(ml,m2); jeśli ml=m2 to

jeśli w=w_ml to wypisz(’TAK’)

w przeciwnym przypadku wypisz(’NIE’) w przeciwnym przypadku m3:= (ml+m2) div 2; jeśli w>w_m3 to mem(m3+l,m2) w przeciwnym przypadku mem(ml,m3)

mem(l,n) (wywołanie początkowe)

Rozmiar danych: długość ciągu.

p_n -liczba porównań słów dla słownika długości n.

Równanie rekurencyjne:

f Pi = 1

\ P2n = Pn + 1

Rozwiązanie: p_n ~ log n.

Liczba porównań jest rzędu logn. Algorytm działa w czasie O(logn).

2.7 Tablice rzeczywistego czasu działania algorytmów

W poniższej tabeli przedstawiony jest rozmiar zadań jakie można rozwiązać w ciągu jednej sekundy, minuty, godziny.

Zakładamy, że do wykonania operacji podstawowej potrzebna jest jedna milisekunda (= 10^_3s).

nr	Algorytm	Złożoność	Maksymalny rozmiar zadania
			1 sekunda	1 minuta	1 godzina
Al	szukanie słowa w słowniku	O(logre)	21000	-	-
A2	znajdowanie maksimum w tablicy	0(n)	1000	6* 10^4	3.6 110®
A3	sortowanie przez 'scalanie’, 'kopcowanie’	0(n * logn)	140	4893	2 * 10^5
A4	sortowanie przez 'wkładanie’,	oę?)	31	244	1897
A5		n^ó	10	39	153
A6	Wieże Hanoi	0(2”)	9	15	21

A teraz przypuśćmy, że zwiększymy szybkość komputera 10 razy. Poniższa tablica pokazuje o ile zwiększy się maksymalny rozmiar zadania który można rozwiązać po przyspieszeniu.