25 (878)

er.a;

vhi 1    :

jJtrfc^- : * l <7’

Złożoność pomyślna dla lego wyszukiwania jest taka sama jak złożoność dla wyszukiwania prostego, ale zastosowanie wartownika sprawia, że nie trzeba sprawdzać indeksu za każdym obiegiem pętli, wyszukiwanie niepomyślne:

T(n) ~ a(n+l) = O(n)

36. Podać algorytm wyszukiwania binarnego. Określić jego złożoność pesymistyczną.

:*u

pr/.Oi • Ci t-sIdL

r;^wi* ^v'    '    - •    ••    «v—

algorytm:    ^A*~ 'ⁿ

proceduro wys z_b Inarr.e {x: eyp^klucsa; var j es" : bocie ar.; Var m: 1. . r.} ;

'/ar lewy, prawy : 0 . ^ r.t l;    "Y

beęin

lewy: -1; prawy:-n;

jesc:-*faise; repeac

u.: ■* ( i e wy - p r a wy j d I v 2 if A(m].klucz=x then

3 e * c:= crue {rakcńczenie poszukiwań)

el są

if A (sil • klucz <x then

iewy:=rr,+ i; (cale] szukanie na prawo od rrd

ai :e

prawy:    1; (dalej szukanie na Lewo od m)

end_if; end_if;

iir.ti. 1 jesz or (lewy > prawy); (gdy lewy > prawy to wyszukiwanie niepomyślne

*? W * ■> "-a*'' *. i « W V

(cdii

indeksu środka

end

zaietą algorytmu jest, że każde porównanie zmniejsza obszar poszukiwań o połowę.

Ij/yzn. ziozonosci obkJ

założenie :    - l < n < 2^H~¹ -{    gdzie tt - wysokość drzewa r* r    Uź

wyszukiwanie pomyślne    /

<_OT4a)=.b4    £-?

Tp^.fn) = b(H+1) (b - czas 'wykonania pojedynczej iteracji repeac)    ~ ^?

\

Dl

/

Q

za założenia wynika, że n < 2 ■ czy i i H-l>lozn

<2

H-l

H * Uogril

Tpe (n) = b( iiogni - 1) = b(l log\n-H)]) = O (logn) T~ ( n) = b[ I + Uognl + Hi ogni - 2    ^ ¹ -r 2)/nl

wyszukiwanie niepomyślne:

Tobfn)- b-H«biogn!

(n) = b{ jlognj - 1) == b(flog(n-H) f) - O (logn) T_sr (n) = biz -r iloen! - 7^jQ^* ¹ )/(n+-l)]

37. Porównać algorytmy wyszukiwania liniowego i bina-rnego pod kątem pesymistycznej złożoności obliczeniowej oraz narzutu związanego z koniecznością reorganizacji p4iku rekordów.

25

1

Złożoność pesymistyczna:

Dla pewnych n<N₀ wyszukiwanie liniowe jest szybsze (w praktyce No jest małe, rzędu 7,8). Wynika to z tego, że w wyszukiwaniu binarnym wykona się więcej operacji przypisania i sprawdzania warunków logicznych.