24 (918)

Sjors: -true;

- . — \ •

r«p«at

if góra Uian

i.;*⁵!,* j j —ii? h: «n-^xł; 1 j « 2 * n /

elfl e

i:*n*l; j;^fc2*n; k:*l; l;*n; end if;

,,L*cz p-cJci r. i-ci^.gu o*"??, j-c^.gn do V-r.i>gu ora?. l-ci^gu" gora:«not góra;

p:~2*p;

until p=n;

end;

>    -    T7 -

Złożoność^

T(n) = n*l (l-Ib. obrotów pętli repeat) p^l.2,.,.,2¹ 2^I=n Mog2

t_ - A =logn

T(n) = nlogn= 0(nlogn)

j_mSformułować zadanie wyszukiwania. Podać algorytm wyszukiwania liniowegofbez wartownika i z wartownikiem) oraz oktaśiić ich złożoności środnie i pesymistyczne.

Dane do zadania wyszukiwania:

- jednowymiarowa tabiica n rekordów wszystkie klucze są różne każdy rekord posiada kiucz ryp klucza musi być dyskretny k - klucz do wyszukania

Zadanie wyszukiwania polega na znalezieniu takiego rekordu Ajj], ze A[jj.kiucz — k (jeśli da się znaleźć taki kiucz to wyszukiwanie jest nazywane pomyślnym)

Wyszukiwanie niepomyślne jest, gdy nic ma takiego j (na ogói chcemy dopisać ten kiucz do tablicy)

Wyszukiwanie liniowa (proste)    ^

procedurę wysz_iini (k: typ_kiucza; var jestibcołean;    i: l..r.+ i);

_r

<T -

begi n    . £

.kiucz <> k)	do	i ^1
_L i__		(i\'t fi:
^1	A t ^|-.v
— 2 a V		: — ? 7 U m .r>w * ■ i ^ ^1' V-

■iM: C i %$ K *. 4

* ^/V_Ł-

i: * i t 1;

«nd whilfl¹; _/

end

(uf i);

a)    gdy' wyszukiwanie jest pomyślne:

Tpe (n) - a-n = O(h) (a - wsp. zależny od liczby operacji dominujących w ciele pętli) Tś.(n) = y p{x)T(x) zakładamy, że p(x>“l/n (wszystko równje prawdopodobne)

xs2.

y • n.„

T / r» ^;

Tjt (n) = l/n(a-r2a+3a- .. +an) = — - — = O(n) ^ ^r ~    [*

,    2    ^x    u ~

b)    gdy wyszukiwanie jest niepomyślne:

7(n) - a*n — O(n) (bo zawsze przeszukiwana cała tablica)

Wyszukiwanie liniowe z wartownikiem

procedurę wysz Lin2(k:typ klucza; var jest:bcoiean; var i: 1 b^ęin

A(n-1J . klucz:«k;    (warcowni):)

i: * l;

u¹ : ~ l W/{

x-ł