PAIE?KA PAPRASTAME S?RA?E
1.1. Nuosekli paie?ka
Tegu ?ra?ai i?d?styti atsitiktinai kaip buvo ?ra?yti. Reikia surasti duot?
?ra?? pagal rakt?. Nuosekliai ie?kant reikia per?i?r?ti visus ?ra?us
nuosekliai.Vid.per?i?r?? ?ra?? sk. ie?kant yra Lap =L/2. Jei ?ra?o n?ra
teks per?i?r?ti visus ?ra?us L. Tarkim ie?komo ?ra?o su tikimybe p0 n?ra
s?ra?e, tada vid. per?i?r?t? ?ra?? sk. Lap=L*p0+(i(1L (i*pi ); pi=1-p0/L.
Ie?kant ?ra?o sutvarkytame faile(?ra?ai i?d?styti pagal rakt?) reikia
per?i?r?ti i? eil?s, tod?l vid. per?i?r?t? ?ra?? sk. tas pats: Lsp=L/2. Jei
ie?komo ?ra?o n?ra, tai paie?ka nutraukiama kai eilinis raktas bus didesnis
u? u?duot?. Atliekant k ?ra?? paie?k? nesutvarkytame faile vid. per?i?r?t?
?ra?? sk. Lkap = k * L / 2.
1.2. Paie?ka interpoliavimas
Jei s?ra?ai sur??iuoti ir ?inomas pirmo ?ra?o raktas K(1) ir paskutinio
K(n) tai galima apskai?iuoti p=X-K(1)/K(n)-K(1). X-ie?komo ?ra?o
raktas.Paie?k? pradedam nuo ?ra?o kurio numeris p*n.
1.3. Binarin? paie?ka
Naudojama sur??iuotame masyve. Jis dalinamas pusiau ir ie?komas raktas
lyginamas su vidurio raktu ir t.t.. Idealus masyvo dydis 2n-1.Jei 31 ?ra?as
reik?s 5 ?ingsni?, kad surasti ?ra?? 31(25-1. Bendru atveju 2n-1-1< N ( 2n-
1. Kai ?ra?? sk. bet koks, tai naudojami tokie alg.:1) Pos?ra?io rib? nustatymo metodas. I?kiriame 2 markerius: V vir?utiniam
adresui ir A apatiniam adresui. Vidurinio ?ra?o adresas F(( (V+A) / 2 (.
Ie?komas ?ra?o raktas k palyginamas su F. Jei k(Fk, tai ?ra?as surastas,
jei k<Fk, tai imama vir?utin? pus?, tada V pasilieka tas pats, o A(F-1.Jei
k > Fk, tai imam apatin? dal?, tada V(F+1, o A i?lieka tas pats ir t.t..
Toks dalinimas atliekamas tol, kol nepasidaro A(V. Rekurentin? lygtis
apra?anti max palyginim? sk. binarin?je paie?koje yra:
f(n)({1, n(1 f( ( n/2 ( )+1, n>1. Sprend?iant rekurentin? formul? galim
u?ra?yti: f(n) ( f( (n/2( ) + 1 ( f( (n/21( ) + 1(( f( (n/22( )+1) +
1 ( f( (n/22( )+2 (…( f( (n/2i( ) + i, kol
( n/2i ((1; i((logn(. f(n)((logn(+1 arba f(n) ( (log (n+1)( . Vid.
palyginim? sk. ideliu atveju kai n ( 2k-1:
f(n)(1* 1/n + 2*2/n + 3*4/n +…+ ((log n( + 1)*2k-1/n ( 1/n * (i(1(log
n(+1 (i * 2i-1). 2k-1-1<n< 2k-1. f(n) ( 1*1/n + 2*2/n +…+ (log n ( * 2k-
2/n + ( (log n ( +1) * (n-(2k-1-1))/n ( 1/n (i(1(log n ( ( i *2i-1) + (
(log n ( +1) * ( n — ( 2k-1 — 1))/n.
Jis artimas max plyginim? sk. Jei ie?kom? ?ra?? n?ra, tai jis ( max
palyginim? sk. Binarin? paie?ka tiek pagal max palyginim? sk. tiek pagal
vidutin? yra optimali.
2) Pos?ra?io dyd?io nustatymo metodas.Pradedant paie?k? i?eities pos?ra?io
dydis S1(N, tai pirmoji riba N1((N/2(, o pos?ra?is S2((S1/2(. Si+1((Si/2( ;
Ni+1(Ni((Si+1/2( . Jeigu ?ra?? n?ra, tai paskutin?je iteracijoje Si+1(1.
Toliau dalinant pusiau ir imant sekant? pos?ra??, jis tampa nuliniu ir tai
rodo, kad ?ra?? n?ra.3) Ribos numeris visada 2 laipsnyje
Idealus atvejis binarinei paie?kai N(2k-1 ir riba bus N1(2k-1.Tegu 2k-
1<N<2k-1, tai pirma riba N1(2k-1. Gaunam 2 ne vienodas dalis. Jei K<F1, tai
imam pirm? dal? ir elgiam?s kaip idealiu atveju. Jei K>F1, tai ie?komas
?ra?as yra antroje dalyje, kuri ma?esn? u? pirm?j?.
2r-1-1<N-2k-1<2r-1 ir v?l viskas tas pats. Panagrin?sime algoritmo
sud?tingum?, ?statant n element? ? med? pagal atliekam? palyginim? sk..
Blogiausias atvejis, kai elementai i?rikiuoti, nes gaunamas paprastas
s?ra?as ir kiekvien? element? pastatyti ? s?ra?o gal?. T(n)-bendras
palyginim? sk. ?statant n element? ? s?ra??. T(n-1) — bendras palyginim?
sk. ?statant n-1 element?. ?statant n-t?j? element? reikia n-1 palyginim?.
T(n) ( T(n-1) + (n-1). T(n) ( T(n-1) + (n-1) ( T(n-2) + (n-2) + (n-1) (
T(1) + 1 +…+ (n-1) ( (i(1n-1 ( i ) ( n * (n-1)/2. Vidutinis atvejis, kai
i?eities seka a1,a2,…,an yra bet kokia, tai ?io algoritmo sud?tingumas
((n log n ). Lygi? sk. binariniame medyje — log n. Tegu T(n) yra palyginim?
sk. ?statant elementus a1,a2,…,an ? binarin? med?. Tegu b1,b2,…,bn yra
ta pati seka, ta?iau jau i?r??iuota did?jimo tvarka. Kadangi a1,a2,..,an
yra atsitiktinai i?d?styti, tai bet kuris i? j? gali atsidurti bent kurioje
vietoje su vienoda tikimybe. Tuomet a1 su tikimybe 1/n gali atsirasti j
vietoje (j(1…n). a1 fakti?kai tampa med?io ?aknim ir jis yra j-tasis. Tai
(j-1) element? yra kair?je pus?je, o (n-j) de?in?je. ?statant (j-1)
element? ? kair? pomed?, reikia (j-1) palyginim? su ?aknimi plius T(j-1)
((j-1)+T(j-1)). Analogi?kai de?iniam pomed?iui reikia (n-j) palyginim? su
?aknimi plius T(n-j). (j-1) + T(j-1) + (n-j) + T(n-j) ( (n-1) + T(j-1) +
T(n-j). Tiek palyginim? reik?t? jei b?t? j-tasis elementas (med?io
?aknimi),bet a1 gali b?ti bet kuris, tuomet palyginim? sk.: T(n) ( 1/n
(j(1n ((n-1)+T(j-1)+T(n-j)) ( n-1+ 1/n (j(1n (T(j-1) + T(n-j)) ( n-1 + 2/n
(j(0n-1 ( T(j) ).
Toliau pertvarkant galima parodyti, kad T(n) ( k n log n, kur k ( ln 4 (
1.39.1) Principas — ‘Skaldyk ir valdyk’
Sprend?iant kok? nors u?davin? kartais jie suskaldomi ? du. Rasti j?
sprendimai apjungiami ir gaunamas u?davinio sprendimas. Savo ruo?tu
suskaidyti u?daviniai gali b?ti toliau skaidomi. Visiems u?daviniams
spr?sti naudojama ta pati rekursyvi proced?ra. Pavyzd?iui, reikia rasti
aib?je i? N element? max ir min element?. Surandant max element? reikia (n-
1) palyginim?. Taip pat ir ie?kant min reikia (n-2) palyginim? (su max
nelyginam). Ie?kant min ir max element? reikia 2n -3. Tarkim n(2k. Vis?
aib? suskaldom ? 2 dalis. Kiekvienoje i? j? randam min ir max ir juos
palyginam. T(n)({1, n(22T(n/2)+2, n>2. Tas dvi dalis galim dalinti dar
pusiau. T(n) ( T(2k) ( 2T(2k-1)+2 ( 2(2T(2k-2) + 2) +2 ( 22T(2k-2) + 22 +2
( 2k-1T(2) + 2k-1 +…+ 23 +22 +2 ( 2k-1 + 2k-1 + 2k-2 + … + 23 +22 +2 (
n+2k-1-2 ( n+n/2-2 ( 3n/2-2. Atliekant toki? skaidymo proced?r?, algoritmo
sud?tingumas suma??ja.Rekurentini? lyg?i? sprendimas
T(n) ( {b, n(1aT(n/c) + bi, n>1
a,b,c-teigiamos const.n(ck; k(log cn.
T(1) ( b
T(c) ( aT(1) + bc ( ab + bc ( (1+a/c);
T(c2) ( aT(c) + bc2 ( a(ab + bc) + bc2 ( a2b + abc + bc2 ( bc2(1+ a/c +
a2/c2) ……
T(n) ( T(ck) ( aT(ck-1) + bck ( bck(1+a/c+a2/c2+…+ak/ck) . T(n) (
bn(i(0logcn (a/c)i. Jei a<c, turim ma??jan?i? geometrin? progresij?. Tuomet
turim tiesin? algoritm? ((n). Jei a(c, tai algoritmo sud?tingumas
((nlogcn). Jei a>c, turim did?jan?i? geometrin? progresij?. Tuomet T(n)
greitai did?ja did?jant n, tai eksponentinio sud?tingumo algoritmas.
U?davin? suskaid?ius ? 4 dalis ir toki? dali? pa?mus 4 – ias: a=c=4,
gauname ((nlog4n), log2n > log4n. Kas bus, kai n?ck? I?vestos formul?s
netinka, bet pa?mus atvej?, kai n’=ck > n, i?vados galioja. U?davinys gali
b?ti sprend?iamas su rekursija arba be jos, ta?iau u?davinio sud?tingumas
nepasikei?ia. Su rekursija algoritmas sprend?iamas ?iek tiek ilgiau.
T Apie rekurentin?s lygties tipo T(n)=aT(nc)+f(n), kur a?1, c?1, f(n)-
teigiama f-ja. 1) Jei f(n)= ((n(logca)-() ,tai T(n)= ((nlogca). 2) Jei
f(n)= ((nlogca) ,tai T(n)= ((nlogca . log n. 3) Jei f(n)= ((n(logca)+()
,tai T(n)= ((f(n)), jei af(nc)?bf(n) (b>1 dideliems n).Balansavimas (skaidymas ? vienodas dalis). Reikia sur??iuoti n ilgio masyv?
did?jimo tvarka. 1.surandam min, kur? sukei?iam su pirmu, po to i? (n-1)
elemento surandam min ir sukei?iam su antru ir t.t.. Rekursyvin? lygtis
apra?anti palyginim? sk.: T(n) ( {0, n(1T(n-1)+n-1, n>1 ;
T(n) ( n(n-1)/2, o algoritmo sud?tingumas ((n2). ?ia skaldymas ? dvi
nelygias dalis: ? vieno elemento ir (n-1).2. Gaunamas suskald?ius u?davin?
? dvi lygias dalis ( n/2. Tarkim, kad n ( 2k. Viena dalis nuo x1 iki xn/2 ,
o kita nuo xn/2+1 iki xn. ?ias dalis sur??iuojam ir sujungiam palyginant
minimalius elementus. Sujungimui reiks maksimum n-1 palyginim?. Tok?
skaidym? galima rekursyviai t?sti toliau, kol lieka dalyse po 1 element?.
Rekursyvin? lygtis apra?anti tok? algoritm? yra:
T(n) ( {0, n(1 2T(n/2) + n — 1, n>1.
?io algoritmo sud?tingumas (( n log n).Dinaminis programavimas.
Kartais galima efektyvius algoritmus gauti naudojant dinamin? programavim?.
?iuo b?du reik?t? skai?iuoti visus dalinius u?davnius, bet sprend?iami nuo
ma?? prie dideli?. Atsakymai prisimenami lentel?je ir u?daviniai jungiami,
kad b?t? i?spr?stas visas u?davinys ir gautas optimumas. Pvz. sudauginant n
matric? yra labai svarbus daugybos eili?kumas, kuris nulemia bendr? veiksm?
skai?i?. Pa?ymim mi j minimalus veiksm? sk. dauginant matricas:
Mi*Mi+1*…*Mj, kur 1 ( i < j ( n. Kai M ( M1*M2*…*Mn, tai j? mati?kumas
yra r0*r1*r2*…*rn.
mi j ( {0, i(j MIN( mik + mk+1, j + ri-1 rk rj ),
j > i, i ( k < j (1).
M` (Mi*Mi+1*…*Mk, [ri-1*rk]. Min vei-ksm? sk. mi,k.
M«(Mk+1 *Mk+2 *… * Mj, [rk*rj].
Atliekant ?i? daugyb? min veiksm? sk. mk+1, j, o sudauginant M` su M«,
min veiksm? sk. ri-1 rk rj. Tai atliekam tol kol negaunam m1n.1-a lygtis
ya dinaminio programavimo rekurentin? lygtis. mi,j reik?m?s skai?iuojamos
tvarka, kai did?ja indeks? sk. I? prad?i? skai?iuojam mi,i( 0 (visiem i),
toliau mi, i+1, po to mi, i+2, kol neprieinam m1n.R??IAVIMO ALGORITMAI
K-ma?i? korte?? r??iavimas
Tegul mes turime sek? A1 A2 … An k-ma?i? korte??, t.y., A erdvinis Ai
elementas, sudarytas i? ai1 ai2 … aik.Reikia ?i? sek? r??iuoti taip: B1
B2 … Bn, kad visiem i Bi ( Bi+1. R??iavimas atliekamas k kart? pereinant
per duot? sek?. Pirm? kart? atliekamas r??iavimas pagal k-?j? komponent?.
Antr? kart? pagal (k-1) komponent? ir t.t. Pr?jus pagal i-?j?, tur?sim
s?ru?iuot? sek?. Kiekviena skiltis ai j yra nuo 0 iki m-1. Reikia
organizuoti m pagalbini? eili? Q(j), kur j ( 0,…,m-1, kurios i? prad?i?
turi b?ti tu??ios. Duomenis A1 A2 … An i? prad?i? sura?om ? s?ra?? EIL?.
Paimam eilin? korte?? Ai i? EIL?S ir patalpinam ? pagalbin? eil? Q(j) pagal
analizuojamos komponent?s reik?m?. Taip darom tol, kol bendra EIL?
i?tu?t?ja. Visi korte?ai atsiduria pagalbin?se eil?se. Po to jie suduriami:
Q(0) Q(1)…Q(m-1) ir jie sudaro vien? bendr? eil? EIL?. Kai praeinam pro
visas komponentes, tai EIL? bus sur??iuota. Algoritmo sud?tingumas yra
tiesinis ([(n+m)/k]. Naudoti ?? metod? neverta, kai n yra ma?as.Nevienodo ilgio korte?? r??iavimas
Kad suvienodinti korte?? ilgius galima priekyje prira?yti nulius, ta?iau
tai ne efektyvu, nes bus bereikaling? daug per?i?r?jim?. Tuomet tegul lmax-
korte?? maksimalus ilgis, tai reikia i? prad?i? sur??iuoti maksimalaus
ilgio korte?us pagal l max paskutin? komponent?. Reik?s lmax kart? r??iuoti
visus korte?us.Antr? kart? reikia r??iuoti korte?us, kuri? ilgis lmax -1 ir
jau sur??iuotus pagal paskutin? komponent?, kuri? ilgis lmax. Ir paskutin?
kart? lmax per?jus per vis? s?ra??, bendram s?ra?e bus sur??iuota seka.
Pastabos: 1. Prie? naudojant ?? algoritm?, visi korte?ai turi b?ti
i?skirstyti pagal ilgius. Tam formuojami s?ra?ai ILGIS(l), kur l (
1,…,lmax, kuriuose sura?yti atitinkamo ilgio korte?ai. Pirmame ?ingsnyje
r??iuojamas tik s?ra?as ILGIS(lmax) pagal paskutin? komponent?. 2. Be to
matom, kad pra?jus kart? pro vien? komponent? gali b?ti daug pagalbini?
eili? Q(i) (kur i ( 0,1,…,m-1) tu??ios. Ne?i?rint to jas visas reikia
jungti ? bendr? s?ra??, tod?l naudinga b?t? i? prad?i? nustatyti kurios
pagalbin?s eil?s bus netu??ios ir tik jas jungti ? vien? bendr? s?ra??.R??iavimas lyginant elementus
“Burbuliuko” metodas. Paprastai elementai r??iuojami pagal raktin? ?od?.
Tarkim turim K1..K16 element? ir lyginame K1 >K2. Jeigu daugiau sukei?iam
vietom. Jeigu ne nieko nedarom ir t.t. Paskutinis palyginimas bus Km > Kn.
Po 1 iteracijos did?iausias skai?ius atsiranda pabaigoje. Sekanti iteracija
vyksta su n-1 elementu, nes paskutinio neimame ir t.t.
Pirmoje iteracijoje bus (n-1) palyginim?. Antroje iteracijoje (n-2), i-
tojoje iteracijoje (n-i).
Tuomet bendras palyginim? skai?ius bus
[pic]
Kadangi ne visuomet elementai sukei?iami, tuomet jeigu i?r??iuota seka bus
0 pakitim?, o atvirk??iai i?r??iuota seka — n(n-1)/2 pakeitim?. Tada
vidutinis pakeitim? sk. bus n(n-1)/4.
Jeigu yra n element? seka, tai i? jos gali b?ti padaryti n! sek?. Mes
laikome kad bet kuri seka gali pasitaikyti su vienoda tikimybe 1/n!.
Kiekvienai sekai galima para?yti inversi?k? sek?. Jeigu turime tokias 2
sekas, ir jas sur??iuosime, tai sumalinis pakeitim? sk. bus n(n-1)/4.
Algoritmo sud?tingumas ((n2).
Iterpimo metodas.
?ia eilinis elementas yra ?terpiamas ? jau sur??iuot? elemet? sek?. Tegul
turime n element? i? viso ir turime jau i sur??iuot? element?. Mums reikia
?terpti i+1 element? Ki+1. Ki+1 atsidurs tarp Kj < Ki+1 < Kj+1 element?.
?statant i+1 element? mums reik?s max palyginim? (su 1, su 2…).Max
palyginim? sk. b?t?:
[pic]Pagal tai ir algoritmo sud?tingumas bus ((n2).Vidutini?kai bus ma?iau
palyginim?.?iuo b?du r??iuojant masyvus (paprastus) patogiau prad?ti elemt?
lyginim? nuo sur??iuotos sekos pabaigos. Tai yra nuo i-tojo elemento.
Panagrin?kime koks ?iame algoritme yra vidutinis palyginim? sk. Tegul
turime i sur??iuot? elemt? ir reikia ?statyti I+1 element?. Pirmiau
lyginsime su 1 elememtu. Yra i+1 pozicijos, ? kurias galima ?statyti i+1
element? ir priekyje ir gale. Laikome, kad i+1 elementas ? bet kuri?
pozicij? gali patekti su vienoda tikimybe 1/(i + 1). Vidutinis palyginim?
sk. ?statant element? bus:
[pic]jei patenka ? paskutin?
prie? pirm?j? pozicij?
element? (gale)
=1/(i+1)(1+2+…+i+i) = 1/(i+1)*((i+1)/i ) /2 + i / ( i + 1 ) = i / 2 + i / (
i + 1 )
Tiek pagal max,tiek pagal vidutin? palyginim? skai?i? ?io algoritmo
sud?tingumas yra ((n2)Ekspermentinis statistinis algoritm? tyrima.s ?iuo metodu pvz. tiriant
r??iavimo algoritmus mums reikia para?yti atitinkam? program?, paiimti
atsitiktin? sek? i? n duomen? ir atlikti skai?iavimus, pvz.: fikstuoti
laik? t1, po to paimame kit? sek? ir gauname laik? t2 po to paimame kit?
sek? taip pat i? n duomen? ir gauname laik? t3 ir tokius bandymus kartojame
k kart?. Gauname atsitiktini? dyd?i? imt? t1, t2, …. tk. Vidurkis bus ( =
1/K(i(1K (ti), vidurkis — atsitiktinis dydis.
Dirpersija bus : S2(t)=[pic]i-t)2= =[pic]ti2-2(t ti +(t2) = =[pic] ti2-
2t[pic]ti+K(t2]= =[pic][pic]ti2-2([pic][pic]ti)* *[pic]ti + K/K2
([pic]ti)2] = [pic]* *[ [pic]ti2 — [pic]( [pic]ti)2]
?i dispersijos fomul? patogesn? ma?ininiuose skai?iavimuose, nes su
kiekvienu nauju atsitiktiniu dyd?iu ti mes kaupiame tik dvi sumas : (ti ir
(ti2.(t — atvirk?tinis dydis ir jis vertina tam tikr? matematin? vilt?.(t
dispersija yra tokia: D((t )= D [[pic][pic]ti] = 1/K2[pic] D(ti) =
1/K*D(t); D — tikroji dispersija;S-?vertinimas.S2((t)=S2(t)/K arba
i?traukus ?akn?: S(t) = S(t)/[pic]; |(t — m|<( — t.y. artiname ir
reikalaujame, kad jos skirtus? (. Kad i?rai?ka tur?t? prasm?, mes para?ome:
P{|(t — m |<(}=p.Padalinkime abi puses i? vidutin?s kvadratin?s paklaidos.
P {|(t — m |/S((t)<( / S((t)}=p. Pa?y-m?kime tp = (/ S((t) (2). m- vidurkio
matematin? viltis.(t — m ?vertinimas tada i? formul?s (2) i?eina, kad ( =
tp*S((t) = tp[pic]. Galim para?yti : t-(< m< t+(, tada t — tp[pic]< m <(t +
tp[pic]t.y. tikroji matematin? viltis su tikimybe p rasis ?iame intervale,
o su tikimybe 1 i?eis i? ?io intervalo. Turime taip vadinam? intervalin?
?vertinim?.Dviej? program? ekspermentinis- statistinis tyrimas. Tegul mes atlikom
skai?iavimus pagal vien? program? ir fiksavom laikus t1i(i=1….K). Galima
paskai?iuoti vidurk? (t1 , dispersij? S2(t1) ir t1+- (1(intervalinis
?vertinimas). T? pat? atlie-kam su kita programa(t2, S2(t2), (t2 +- (2
Jei palyginsim tik (t1 ir (t2 tas dar nerodo, kad vienas i? ?i? algoritm?
yra geresnis, nes (t1 ir (t2 — atsitiktiniai dyd?iai, tod?l palyginim?
rezultatas taip pat gali b?ti atsitiktinis. Geriau lyginti (t1 ( (1 ir (t2
( (2. Jei jie nepersidengia, tai yra pagrindo teigti, kad viena programa
yra geresn? u? kit?.Arba galima lyginti ir taip:
1.paskai?iuojam (t=t1-t2 ; D(((t ) = D((t1)+D((t2); Jeigu ?ie atsitiktiniai
dy-d?iai nepriklausomi.
S2(((t ) = S2((t1 ) + S2((t2) = S2(t1)/K + S2(t2)/K ;
S(((t)=(((S2(t1)+S2(t2))/K);
((t — tpS(((t )<m(((t )< ((t + tpS(((t )
p=0.95. Jeigu ?is intervalas neapima 0, tai galima teigti, kad viena
programa geresn? u? kit?.
Galima naudoti priklausomus bandymus, kurie gaunami taip:
suformuluojam atsitiktin? sek? i? n element?. J? sur??iuojame su viena
programa ir gaunama laik? t11. Po to t? pa?i? sek? sur??iuojame su kita ir
gauname t21 ir taip toliau k kart?, t.y. gauname t1i ir t2i, kur i
=1,2…,K. Galima paskai?iuoti: (t1, (t2, S2(t1)=[pic][[pic]t21I —
1/K([pic]t1I)2]; S2(t2)([pic][[pic]t22I — 1/K([pic]t2i)2]
Tarpusavio momentai M1=[pic][pic] (t1i-(t1)(t2i-(t2)=[pic][pic](t1it2i-
(t1t2i -(t2t1i+(t1(t2)=[pic][[pic] t1it2i — (t1(t2i — (t2(t1i + K (t1(t2]
=[pic][[pic]t1it2i-1/K[pic] t1i[pic] t2i] ; (ti= t1i — t2i ; D((t)=D(t1)+
D(t2)-2M12 (1); Koreliacijos koef. K12 = M12 / ((t1)((t2); Jis gali kisti
nuo -1 iki +1. M12=K12((t1)((t2). Jei K12=1, tai rei?kia teisin? funkcin?
priklausomyb?. Jei K12=1 ir ((t1)=((t2), tai jei ?statysim ? 1 -aj?
formul?, tai gausime D((t)=0. Ta?iau tai idealus atvejis, o prakti?kai K12
< 1.
Jei K12 > 0, tai ((t = (t1- (t2, S2((t)(S2((t1)+ S2((t2)-2(M12 t.y.
dispersija ma?esn? nei nepriklausom? dyd?i? atvju. S2(((t)( S2(t1)/K+
S2(t2)/K — 2K12S((t1) * S((t2)= S2(t1)/K+ S2(t2)/K — 2M12/S(t1)S(t2)*
S(t1)/(k * S(t2)/(K = S2(t1)/K+ S2(t2)/K — 2M12/K t.y. ir vidurkio
dispersija yra ma?esn?, nes atsiima 2M12/K. Atitinkamai intervalinis
?vertinimas: ((t — tpS(((t) <m ((t) < ((t + tpS(((t) (1). Kadangi S2((t)
esant priklausom? bandym? atvejais yra < nei nepriklausom? bandym?, tai
intervalinis ?vertinimas (1) yra siauresnis ir algoritm? vertinimas yra
tikslesnis. Jei intervalas apima 0, tai algoritm? palyginti negalima. Arba
galima sakyti ir taip: naudojant priklausomus bandymus, esant teigiamai
koreliacijai mums pavyksta i?skirti grei?iau reik?mingus skirtumus. Tas
pats rezultatas gaunasi jei su kiekvienu bandymu mes fiksuosime t1i, t2i ir
skai?iuosime (ti, i=1,2,……..,K. fakti?kai gauname atsitiktinius dyd?ius. (t
= 1/K[pic](ti; S2((ti)=[pic][[pic](ti2-1/K([pic](ti)2]
S2(((t)=S2((ti)/K; S(((t)= S((ti)/(K
((t — tp S(((t) < m((t) < ((t + tp S(((t)
Jei ?is intervalas apima 0, tai negalima sakyti, kad viena programa geresn?
? kit?. Ir prie?ingai, jei neapima 0, tai yra pagrindo teigti, kad viena
programa yra geresn? u? kit?.Binarinis ?terpimo algoritmas
Ie?kant elementui vietos jau sur??iuotoje sekoje mes galima naudoti
binarin? paie?kos metod?.
Iterpiant i+1 element? ? i-tojo dyd?io sur??iuot? s?ra?? reikia atlikti
(log i ( + 1 = (log(i+1)( palyginim?. Visada reiks atlikti max palyginim?,
nes ?terpiamo dyd?io tame s?ra?e n?ra. R??iuojant n-tojo dyd?io s?ra?? mums
reik?s atlikti [pic](log(i+1)( palyginim?.
[pic](log(i+1)( = [pic](log(i)( = n(log(n)]-2(logn( + 1 tokio algoritmo
sud?tingumas ((nlogn).R??iavimas i?rinkimu
I? prad?i? i?renkame did?iausi? element?. J? sukei?iame su paskutiniu.
Paskui i? likusios dalies i?renkame did?iausi? ir sukei?iame su
prie?paskutiniu ir t.t.
Palyginim? sk. tokiam algoritmui yra [pic](n-i)=[pic]i=n(n-1)/2, tai ?io
algo-ritmo sud?tingumas: ((n2).?is alg. gali b?ti geriausias vienu metu
ie?kant max ir min.R??iavimas piramide
?is algoritmas susideda i? dviej? dali?:1. I? duotos sekos sudaryti
r??iavimo med?. 2. Sukeisti pirm? element? su paskutiniu ir atstatyti
r??iavimo med?. R??iavimo med? pradedame sudarin?ti nuo (n/2(, o kiekviena
narys A(i) (A(2i) ir A(i) (2i+1, ir [1(i(n/2] arba [1(i(n/2]. Did?iausias
elementas tampa med?io ?aknis. Pastatome did?iausi? element? ? sekos gal?
ir kadangi jis jau savo vietoje, tod?l jis daugiau nenagrin?jamas, o sek?
suma?iname 1 ir turime jau ne r??iavimo med?. Mums v?l reikia atstatyti
r??iavimo med?, kad pirmasis elementas b?t? did?iausias t.y. pradedant nuo
n/2 eiti link pirmo ir kiekvien? element? reikia sukeisti vietomis su
didesniu s?numi. Taigi mums reikia tam tikr? element? perstumti per ka?kiek
lygi?. Perstumiant element? per 1 lyg? reikia atlikti 2 palyginimus: (2i)
ir (2i+1) tarpusavyje ir did?iausi? i? j? su palyginamu elementu.
Perstumiant element? per n lygi? reikia atlikti 2n palyginim?, tod?l
blogiausiu atveju, perstumiant n element?, palyginim? sk. nevir?ins 2nm.(m-
lygi? sk. , be pirmos vir??n?s). Kai reikiia perstumti 1 element?,
maksimaliai reikia f(n)(2(log n( palyginim?. Tiksliau: f(n) ( (log n( +
(log (n-1)(. Perstumiant n vir??ni? maksimaliai tur?tume 2n(log n(
palyginim?. Algoritmo sud?tingumas bus ((n log n). Ta?iau ?rodyta, kad
pirmoje dalyje reik?s ne daugiau kaip 2n-4 palyginim?, tod?l pirmos dalies
algoritmo sud?tingumas yra tiesinis, nes ?ia reikia per?i?r?ti tik n/2
element?, o visumoje ?io algoritmo sud?tingumas ((n log n).R??iavimas suliejimu (sujungimu)
n element? dalinami ? 2 dalis: [pic] ir [pic] ?ios dalys tur?t? b?ti
sur??iuojamos ir sujungiamos. Ta?iau jos v?l savo ruo?tu suskaidomos iki
vieno vieno elemento ir atliekamas j? sujungimas. Tai palyginim? sk. ?iame
metode:
f(n)=[pic]
?ios rekurentin?s lygties sprendimas yra toks: f(n)=n (log n( — 2 (log n(
+1
?i rekurentin? formul? sutampa su binarinio algoritmo ?terpimo blogiausiu
atveju.
Paai?kinimas algoritmo: next — indeksas, ? kur? mes ra?omelower 1 — pirmos
dalies pirmas indeksas. Tr?kumas: reikia papildomos atminties masyvui Save.R??iavimas suskaldymu (quick sort).
Turime sek? i? n element?. I(1, o J(n. Lyginame A(I) su A(J). Jei A(I) <
A(J), tai J(J-1, bet jei A(I) > A(J) tai sukei?iame juos vietomis ir I(I+1
ir t.t.. Taip palyginus su visais elementais, gausime, kad kair?je pus?je
elemento su kuriuo mes lyginome bus elementai ma?esni u? j?, o de?in?je
didesni, t.y. suskald?m sek? jo at?vilgiu. Elementas pagal kur? atlikome
palyginimus yra pirmasis ir vadinamas generaliniu. ?ia generalinis
elementas visada buvo pirmas, ta?iau tai neb?tina. Gaima paimti bet kur?.
Generaliniai elementai gali b?ti parenkami ?vairiai: pirmas, atsitiktinis,
mediana (vidurinis). Skaidyti pagal median? geriausia. Galima paimti
nedideli? imt? i? keli? sekos element? ir surasti median?. Imant visada
pirm? element?, blogiausias atvejis gaunasi, kada seka yra sur??iuota. Tada
seka suskaldoma ? vien? element? ir vis? likusi?. Gausis taip kaip ir
kituose algoritmuose. Tuo atveju algoritmo sud?-tingumas ((n2), o visais
kitais atvejais ?ymiai geriau. ?is algoritmas gerai veikia didel?m sekom, o
taip pat reikia tinkamai parinkti generalin? element?. Vid. veiksm? sk.
yra:
[pic]
c-koef., cn-veiksm? sk. atliekant pirm? suskaldym?. Generalinis elem.
atsiranda i-ojoje vietoje ir gaunam dvi sekas (i-1) ir (n-i). Veiksm? sk.
skaldant sek? (i-1) yra (i(1n f(i-1), o sek? (n-i) yra (i(1n f(n-i). 1/n-
i su vienoda tikimybe gali atsirasti bet kurioje vietoje.
(i(1n [f(i-1)+ f(n-i)](f(0)+ f(n-1)+ f(1)+ f(n-2)+…+ f(n-2)+ f(1)+ f(n-
1)+f(0)( 2 f(0)+2f(1)+…+2f(n-2)+2f(n-1)(2(i(1nf(i)
f(n)(cn + 2/n(i(0n-1 f(i), kai n>1
f(0)(f(1)(b
f(2)(2c+2/2[f(0)+f(1)](2c+2b(k
f(3)(3c+2/3[f(0)+f(1)+f(2)](3c+2/3[2b+2c+2b](3c+8/3b+4/3c((8b+13c)/3.
?rodyta, kad visada galioja lygyb? f(n) < kn ln n. Tod?l QUICKSORT
algoritmo vidutinis sud?tingumas yra ((n ln n). ?ia nevertinta, kad ma?os
sekos gali b?ti r??iuojamos kitu b?du, kas dar pagreitina ?? algoritm?.Optimalus r??iavimas. Jei yra n element?, tai variant? i? viso gali b?ti
n!. n=3, 3!=6 Minimalus palyginim? sk. blogiausiu atveju = 3. Ir laikom,
kad ?i schema optimali. Tegul S(n) — minimalus palyginim? sk. blogiausiu
atveju, r??iuojant n element?: S(3)=3 Pilname k-tojo lygio binariniame
medyje, paskutiniame lygyje yra 2K mazg?. K=S(n).
n! =< 2 S(n), tada S(n) >= (log n!( =n log n — n/ln2+1/2 log n + (
( — paklaida. (Stirlingo formul?)
Minimalus palyginim? sk. blogiausiu atveju yra apie nlogn . Palyginus
(log n!( su f(n) = n (log n( — 2 (log n( + 1 pasirodo, kad suliejimo
metodas pagal minimal? palyginim? sk. n?ra minimalus.I?RINKIMAS
Maksimalaus elemento i?rinkimas i? n element? sekosRadus max element?,
reikia atlikti n-1 palyginim?. O kiek reikia priskyrim?? Jei seka —
ma??janti, tai reik?s 1 prisky-rimo. Jei seka — did?janti, tai reik?s n
priskyrim?. O koks vidutinis priskyrim? sk, jei bet kokia seka i? n
element? vienodai galima?
Hn=1 +[pic] P[ai > aj] ( 1 = 1+ [pic]1/2 ( 1 = [pic][pic] = ln n + ( +1/2n
+ (
?i eilut? diverguojanti, t.y. did?jant n, jos reik?m? did?ja.(Eulerio
formul?) ?ia ((0,577; (- paklaida.Sekan?io did?iausio elemento radimas (2-? max radimas). Norint surasti max
element?, reikia n-1 palyginim?. Po to j? pa?alinam ir surandame kit? max.
Tam reikia n-2 palyginim?. Tod?l i? viso palyginim? sk: 2n-3. ?? algoritm?
galima pagerinti suskald?ius n element? ? 2 dalis: (n/2( ir (n/2( Ie?kome
max element?: I dalyje max el. surasti reik?s (n/2( — 1 palygini-m?, II
dalyje — (n/2( palyginim?. Po to juos reik?s tarpusavyje palyginti. I? viso
reik?s [pic] palyginim?. Paskutiniame lygyje pralai-m?jus? element? reik?s
palyginti su pra-laim?jusiais elementais, lyginant su mak-simaliu. Taip
rasim kit? max element?. Reikia [pic] palyginim?. Toliau galima kelti
klausim?, ar negalima ??jimo sek? padalinti ? 4, 8 ir t.t. dali?, kol
neprieisim algoritmo, kuris atitinka piramidin? r??iavim?. Lai I faz?je
lyginame po 2 elementus: n=8
a1
a1 a6
a1 a3 a6 a7
a1 a2 a3 a4 a5 a6 a7 a8
Ie?kant kito max elemento, reikia a6 ly-ginti su pralaim?jusiais, randant
a1Jei a6 > a3, tai reikia palyginti ir ar a6 > a2
Jei a6 < a3, tai reikia palyginti ir ar a3 > a6
Radom max per 2 palyginimus. Pirami-d?je radom per n-1 palyginim?. Tai yra
sekantis randamas per (log n( -1 palygi-nim?. Gauname, kad ?iuo metodu
palygi-nim? sk. yra optimalus: n + (log n( — 2 .Geriausio (max) ir blogiausio (min) elemento i?rinkimas
Galima si?lyti suskaidyti sek? n ? 2 dalis ir sura?yti ?iose dalyse max ir
min elementus. Palyginus max-ius elementus gaunamas max-is elementas, min-
ius -min-is. Rekursyviai galima suskaidyti iki 1,2 element?. Palyginant 2
elementus tarpusavyje i? karto gauname max ir min elementus. Rekurentin?
lygtis, apra?anti tok? akgoritm?:
f(n)=[pic]
Bendras ?ios srities sprendinys:
|[pic|(n-2(log |
|] |n()/2, kai|
| |n =<3 * |
| |2(log n(-1|
| | |
| |(2(log |
| |n(+1-n)/2,|
| |kitais |
| |atvejais |k-ojo didesnio elem. I?rinkimas[be ru?iavimo]
1.Alg. — i?rinkimas su randomizacija: pa?mus ?-aj? elem ir elementu seka
suskaidoma ? 2 dalis: (i-1)- S1, i, (n-i)-S3. Jeigu pataikeme paimti
skaidymui elem. k-uoju, tai jis atsiduria savo vietoje ir algor. baigia
darba. Jei nepataikeme tai tolimesniam skaidymui imame poaib?, kuriame yra
ie?komas elem. ir j? skaidome toliau: Jei i>k, tai imame S1, kuriame yra (i-
1) ele-t?. Jei i<k, tai imame S3 kuriame yra (n-i) elem. Antru atveju
imamas poabis S3 , taciau ie?komas elem., kuris yra(k-i), o skaidymui
naudojamas tas pats alg. Kadangi skaidydami gali buti parinktas bet kuris
elem.i, kuris gali b?ti lygus i =1,2..n su vienoda tikimybe 1/n, tai vid.
palyginim? sk. bus
f(n)=n-1+1/n [(i=1k-1 f(n-i)+(ni=k+1 f(i -1)]=n-1+1/n [(n-1i=n-k+1 f(i)+
[(i=kn-1 f(i )]
?ia ?rodyta, kad f(n)<= 4n , t.y vidutini?kai ?is alg, yra tiesinis ((n).
Jeigu nevykusiai pasirenkame skaidymui elem, tokio alg, sud?tingumas ((n2).
I?rinkimas be randomizacijos.
Naudojan 1-m? alg geriau b?t? ?inoti median? ir pagal j? suskaidyti aib?,
bet reik surasti median?.Si?lomas apytikslis b?das rasti median?-
padalinsime aib? po 5 elem. Surandame kiekveinos dalies median? ir pagal ??
elem, skaidome vis? aib?. Ta?iau ?ia matom, kad generalinio elem. suradimui
naudojamas ma?ininis laikas, tai rei?kia kad sunaudotas laikas b?t? ma?as
palyginti su tuo, k? i?lo??m i? geresnio aibes skaidymo.?ia -pana?u ? bin.
Paei?k?, tik skaidome per pus?. Aibei i? 5 medianos rekia 6 palyginim?.
Medianos (n/5( grupi? radimui reikia 6*(n/5( palyginim?.
Medianai i? median? radimui reikia f((n/5() palyginim?.
Suskaidymui reikia n-1 palyginim?. Atlikus suskaidym? ir atmetus ma?iausiai
(3n+5)/10 elem, lieka (7n+5)/10 elem, kuriems tolimesniam skaidymui reikia
i? atitinkaami f(((7n+5)/10() palyginim?. Todel u?ra?ome rekurentin? lyg?:
f(n)<f(((7n+5)/10()+f((n/5()+6*(n/5(+(n-1)
Gavome sud?ting? rekurentin? lygt?, kuri? sunku i?spresti, ta?iau ?rodyta,
kad : f(n)<=20n. ?ia blogiausiaa atvejis ir sud?-tingumas ((n). n elementai
u?duoti san-tykiu >( . i1 ,i2 …ik = n. P(i1 ,i2 ..ik ).
Nagrin?jome ?io bendro u?davinio kelis atvejus:
1.ma?iausio elem, radimas P(1,n-1)=n-1. (palyginim? sk ie?kant min =n-1).
2.1-mo ir 2-ro ma?iausio elem, radimas P(1,1,n-2)=n+(log n(-2.
3.ma?. ir did?. elem, radimas
P(1, n-2, 1)=(3/2 n(-2
4.k-tojo didesnio elem, radimas
P(k-1, 1,n-k) = (( n)
5.Dviej? ma?iausi?: P(2,n-2)=n+(log(n-1)(-2
6. trij? ma?iausi?: P(3,n-3)=n+2(log n(-(3|2|1|
?vairiais atvejais priklausomai nuo n.
Galima kelti tokius u?davinius:
a.surasti k ma?iausi? elem, P(k,n-k).
b. surasti k-?j? element? P(k-1,1,n-k).
c. surasti k element? i? eil?s P(1,1,1,..,1,n-k)
P(1,1,1,..,1,n-k)> P(k-1,1,n-k)> P( k,n-k).Veiksmai su aibemis(DS po?iuriu)
U?davinius galima suvesti ? veiksmus su aib?mis. I?analizuojam ?vairias
Duomen? Strukt?ras ir pasirenkam labiausiai tinkam?. Gero alg. Suk?rimas
neatski-riamas nuo tinkamos DS pasirinkimo. Pagr. mat. veiksmai su aib?mis
b?dingi informacin?s paie?kos u?daviniams:
1:PRIKLAUSYTI (a, S). Nustato ar elem.a priklauso aibei S. Jei a priklauso
S, tada TAIP, prie?ingu atveju NE..
2:?STATYTI (a,S).?stato elem, a ? S. Gaunasi aib? S ir elem, a t.y. S({a}.
3:PA?ALINTI (a,S). Pa?alina a elem, i? aib?s S t.y. aib? S pakei?iama ? S-
{a}.
4. APJUNGTI (S1,S2,S3). Atlieka tok? veiksm?: S3= S1(S2.
5:RASTI (a). Reikia rasti aib?, kurioje duotu momentu randasi elem, a. Jei
rast? dvejose aib?se, tada veksmas nenustatytas.
6:SUSKALDYTI (a,S) ?ia aib?selem, u?duoti santykiu <=.?is veiksmas atliks
aib?s S suskaldym? ? S1={b|b<=a, b(S} ir S2={b|b>a}
7:MIN (S) Suranda ma?iausi? aib?s S elem.
?iuos veiksmus reik atlikti tam tikra seka duomen? baz?je.Mus domina laikas
atliekant veiksm? sek? priklausomai DB dyd?io ir nuo veiksm? sekos ilgio.
?is laikinas sud?tingumas paprastai tikrinamas blogiausiu atveju ir
vidutini?ku.
PVZ.
Kraskalo alogoritmas.
Surasti ekonomin? med? neorentuotam grafe. Yra grafas G (V, E).V-vir?.
aib?,E-briaun? aib. Kieikviena briauna i? E turi svor? c. Reikia surasti
graf?-med? G(V,T). T-E poaibis i?. Taip kad ( i (T ci =>min.
Medis grafas be ciklo. Jei medyje S(V,T) pridesime koki? nors briaun?, tai
susidarys vienas ciklas. Grafo G mi?ku vadiname neorentuot? med?i? aib?:
{V1.,T1}, {V2.,T2},…,{Vk.,Tk} . V1 ,V2, .. Vk-suskaldyta aib? V. V=V1
(V2,(..(Vk; V i (Vj =(. Atitinkamai T1,T2,…Tk yra aib?s E poaibiai.
Kraskalo alg sako: reikia med?ius jungti minimalaus ilgio briaunomis ir
apjungti sujungtus med?ius ? vien?. Taip atliekama tol, kol nesigauna
vienas ekonominis medis.
////////// P R O G R A M A—————
(1 ir (2 yra med?iai mi?ke. ?iame algo-me E — grafo briaun? aib?. T-
ekonominio med?io briaun? aib?. VS — grafo mi?ko med?iai kurie apjungiami ?
ekonomin? med?:
I? prad?i? VS- atskiras grafo G vir??nei kaip vieno elem, aibei(viena
vir??n?-vienas mi?ko medis).
Kadangi aib?je E yra sura?ytos briaunos,kurias rekia imti su minimaliu
svoriu. Tai galb?t naudinga atlikti j? sur??iavim?. Tai gali b?ti paimtas
alg, kurio sudetingumas ((eloge).e-briaun? sk.
Tuomet 3-?io operatoriaus sudetingumas proporcingas vir??ni? sk. n ((n).
Laikas reikalingas surasti aibei (1 ir (2 ?kurias ?eina vir??nes V ir ( ir
j? sujungimas, jei priklauso skirtingoms aib?ms yra beveik tu??ias: ((n) .
O jei tiksliau t.y. ((n G(n)), kur G(n) — atvirk?tin? f-jai F(n) =2F(n-1)
Jeigu naudosime s?ra?? strukt?r?, tai (7,8) ?ios dalies alg. sudetingumas
(( MAX(e,n log n)). Tod?l matom, kad visumoje Kraskalo algoritmo
sud?tingumas yra ((e log e), kur? nulemia r??iavimas.Paskirstymo metodas (he?iravimo)
Mes ?ia nagrin?sime duomen? strukt?r? besikei?ian?ioje aib?je S. Nauji
elementai bus ?statomi, seni pa?alinami ir karts nuo karto reik?s atsakyti
? klausim?: ar priklauso duotu momentu konkretus elementas aibei S. Bus
reikalingi tokie veiksmai: PRIKLAUSYTI(a,s), ?STA-TYTI(a,s),
PA?ALINTI(a,s). O elemen-tai, kurie gali b?ti aib?je S, imami i? labai
didel?s aib?s. Panagrin?sime paskirstymo metod?, kuris leid?ia gerai
atlikti ?iuos 3 veiksmus. A
0 h(a)=1
1 h(a)=2h(a)=
m-1 =m-1
A-nuorod? masyvas(kiekvienas elementas — nuoroda ? sara??). Paskirstymo
funkcija h(a) atvaizduoja universalios aib?s elementus ? sveik? skai?i? 0
( m-1 aib?.
Pvz.: h(a)=a mod m, ji gera kai a yra tolygiai pasiskirst?. Vadinasi mums
reikia h(a) pasirinkti pagal a pasiskirstym?. A(i) — nurodo ? sara?o
element? a ( S, kur h(a)=i. Tai operacijos ?STATYTI(a,s) atlikimui reikia
paskai?iuoti h(a) ir po to per?i?r?ti s?ra??, ? kur? nurodo h A[h(a)]. Jei
elem A ten n?ra, tai j? reikia ?statyti sara?o gale. PA?ALINTI(a,s)
atliekama analogi?kai. Tas pats ir PRIKLAU-SYTI(a,s). Blogiausiu atveju
gali atsitikti, kad atliekant operacij? ?STATYTI visoms h(a) gaunasi tas
pats skai?ius ir visi elementai tada rasis viename sara?e. Tuo atveju,
atliekant i-taj? operacij? reik?s laiko, proporcingo i. Ir atliekant
?statymu reik?s ((n2) laiko. ?iuo atveju tai yra tas pats kaip ir paprastas
sara?as. Ta?iau vidutinis laikas bus ?ymiai geresnis. Jei h(a) ?gauna
reik?m? su tikimyb?mis 1/m ir ?statant n<m element?, tai ?statant i-t?j?
element?, vidutin? sara??, ? kur? ?statomas ilgis, yra (i-1)/m < 1. Tod?l
vidutinis laikas, ?statant n element? yra tiesinis ((n).
Jei n operacij? ?STATYTI, PRIKLAU-SYTI atliekama kartu su ?ALINTI, tai
bendras vidutinis laikas bus tiesinis. Da?nai lentel?s dydis m imamas ne
ma?esnis u? element? sk. n. Ta?iau n i? anksto ne?inomas, tod?l ?statym?
eigoje lentel?s dydis m gali kisti. Tegu mums reikia atlkti ( kart?
operacija PRIKLAUSYTI aib?je i? n element?. Jeigu aib? S sura?yta bet
kokiame nesur??iuotame sara?e, tai reik?s per?i?r?ti elementus i? eil?s kol
bus surastas ar pasibaigs sara?as. Sud?tin-gumas (n. (ir blogiausiu ir
vidutini?ku atveju). Paskirstymo metode ( kart? atliekant operacij?
PRIKLAUSYTI jo sud?tingumas vidutini?kai yra (((). (jei n < m) ir
blogiausiu atveju (((n). Kai aib?je u?duota eil? <=, tai galima naudoti
binarin? paie?k?, prie? tai atlikus sur??iavim?. Tada blogiausiu atveju
reikia ne daugiau kaip (log2(n+1)( palyginim?. Ie?kant ( kart?
(log2(n+1)(. Tai lyginant pas-kirstymo metod? su binarine paie?ka, tinkamai
parinkus h(a) da?nai paskirstymo metodas duoda geresnius rezultatus. Tegul
mums reikia atlikti aib?je veiksmus ?STATYTI(a,s), PA?ALINTI(a,s), PRI-
KLAUSYTI(a,s) ir MIN(s). pirmiems trims veiksmams gerai tinka paskirstymo
metodas, bet jame negalime atlikti MIN(s).Tai visiems ?iems vieksmams
atlikti gerai tinka binarin?s paie?kos med?iai.Optimal?s binarin?s paie?kos med?iai
Tegul mums reikia daug kart? atlikti tik 1 operacija PRIKLAUSYTI(a,S).a(S
ir a(S. Tegul yra a1 , a2 … an(S.U?duotos tikimyb?s su kuriomis reik?s
ie?koti atitinkamo elemento p1, p2 ,… pn. q0-tikimyb? ,kad ie?komas
elementas a<a1.
Tikimyb? q1 -tikimyb? ,kad reik?s ie?koti elemento a, kuris a1< a < a2. Ir
qi , kur ai < a < ai+1. qn ,kad reik?s ie?koti a, kuris a>an. Vadinasi yra
u?duotos tikimyb?s q0,q1,…,qn. (pi+(qi(1.Reikia sudaryti optimal?
paie?kos med? ,kuriame vidutini?kai b?t? atliekama ma?iausiai palyginim?,
ie?kant ?vair? element? su u?duotomis tikimyb?s.
a4 0
a3 a5 1
a1 3 4 5 2
0 a2 3
1 2
Fiktyviai pa?ymime elemtus medyje ,kuri? n?ra bet tenka ie?koti. Tikimyb? ,
kad reik?s ie?koti a, kuris a3<a<a4 yra q3.Jei mums reik?s i?koti ai
elemento , tai mums rek?s atlikti GYLIS(ai)+1 palyginima. Jei mums reik?s
ie?koti i-tojo elemento ,kurio n?ra , tai mums reik?s atlikti GYLIS( i )
palyginim? . Tai vid. palyginim? sk. C bus:
C((i(1n pi [GYLIS(ai)+1]+(i(0n qi GYLIS( i )
Nubrai?ome visus galimus med?io variantus ir kurio C ma?iausias ,tai ir bus
optimalus binarin?s paie?kos medis . Tai nesunku atlikti kai element? sk.
nedidelis.Ta?iau ?? u?davin? galima spr?sti naudojant dinamin?
programavim?. Pirmiausia reikia nuspr?sti kur? elementa padaryti ?aknimi. O
po to lieka dar du med?iai. Fakti?kai galime padaryti bet kur? ai element?
i? n element?. Taigi gali b?ti n variant?. Gaunasi labai kompli-kuotas
u?davinys , nes dar 2n pomed?i? su kuriais darom v?l t? pat?. Tod?l
fakti?kai ?? u?davin? reikia spr?sti i? apa?ios. Pa?ym?sime Tij optimal?
pomed? , kur 0( i ( j( n.Tai dabar ?iame pomedyje yra elementai: (ai+1 ,
ai+2 , …,aj ). ai n?ra, nes pomedis prasideda nuo fiktyvaus elemento,
baigiasi tai pat fiktyviu aj. Pa?ymim Cij jo vidutin? palyginim? sk.
(kain?) . ?io pomed?io ?aknis yra rij . Pa?ym?sim dar kiekvienam pomed?iui
Tij svor? wij , kuris yra lygus:
wij ( qi + (pi+1 + qi+1) +(pi+2 +qi+2) +…+(pj+qj). Tij turi ?akn? ak tada
jis turi kair? pomed? Ti, k-1 ? kur? ?eina (ai+1, ai+2 ,…,ak-1) ir
de?in? pomed? Tkj ? kur? ?eina elementai (ak+1, ak+2, …aj ) . Fakti?kai
yra taip :Gali b?ti taip ,kad i(k-1, tada kairys pomedis tu??ias ir gali b?ti k(j,
tada de?inys pomedis tu??ias. Tu??io pomed?io kurio indeksai sutampa Tii
, kaina Cii(0, o svoris wii (qi. Tada galima para?yti taip: Ci j (wi , k-
1+pk + wk j+Ci , k-1+Ck j(wi j+Ci, k-1+Ckj .Fakti?kai mums reikia rasti
reik?m? , kuri minimizuoja Ci j .Kadangi ?ia fig?ruoja wij , kuri nuo k
nepriklauso, tai fakti?kai reikia minimizuoti sum? Ci, k-1+Ck, j . Tai,
ie?kant optiamlaus med?io Tij reikia skai?iuoti kiekvienam k , kuris i< k (
j med?io kain? su ?aknimi ak ir pomed?iu Ti, k-1 ir Tk ,j .
?io skai?iavimo algoritmas (1) yra: …..(patys surasit)
Optimal? binarin?s paie?kos med? sudaro procedura (2) MEDIS( i, j) ….
(patys surasit)
Pirmas (1) algoritmas paskai?iuoja visus Ci j ir ri j visiem 0( j ( i ( n
vis did?jant skirtumui j-i . Po to (2) algoritmas prasideda proced?ra
MEDIS(0,n) ir rekursyviai sudaro optimal? binarin?s paie?kos med?.
Optimalaus binarin?s paie?kos med?io algoritmo sud?tingumas yra ((n3)
.Proced?ros MEDIS(i, j) sud?tingumas yra tiesinis , nes ji i??aukiama n
kart?.
8-tame operatoriuje ie?kant m reikia palyginti sumas Ci, k-1+Ck, j . Toki?
sum? yra j-1. tod?l ?ios dalies sud?tingumas yra ((j-i). j ?gija reik?m? n
, o i-nul?. tai maksimalu atveju. I?orinis ciklas 4-10 atliekamas n kart?
, o vidinis ciklas 5-10 nedaugiau n kart? kiekvienai i?orinio ciklo
iteracijai . Tod?l algoritmo sud?tingumas su gera atsarga yra ((n3).OPERACIJ? APJUNGTI IR RASTI ATLIKIMO ALGORITMAS
Kruskalo algoritm? ypatumai:
1.Apjungiamos visada nepersikertan?ios aib?s.
2.Aibi? elementai tai vir??ni? numeriai nuo 1 iki n.
?ia u?davinio sprendimui yra papras-?iausiai duomen? strukt?ra — masyvas
i? n element?. R(i), (i=1,2,…,n).
?ia kiekvienas elementas R(i) yra i-ta vir??n?. I? prad?i? kiekvienas
elementas sudaro atskir? aib?, tod?l sura?oma R(i)=i ir tai rei?kia aib?s
numer?, kuriai priklauso ?is elementas. Operacija RASTI(i) atliekama
tiesioginiu kreipimosi ? R(i). ir gaunamas aib?s numeris, kuriai priklauso
?is elementas. Kreipimosi laikas pastovus, tod?l atliekant n toki?
operacij?, sud?tingumas yra tiesinis ((n). ?ia yra geriausias atvejis.
Norint atlikti operacij? APJUNGTI(A,B,C) reikia per?i?r?ti vis? masyv?
R(i). suradus reik?mes A arba B jas pakeisti reik?me C. atliekant ?i?
operacij? vien? kart? , laikas proporcingas masyvo dyd?iui n, o atliekant n
kart? ?i? operacij?, sud?tingumas yra ((n2). ?i? duomen? strukt?r? galima
pagerinti naudojant susijusius s?ra?us ir apjungiant aibes — ma?esn?
prijungiant prie didesn?s. ?ia reikia skirti vidinius aibi? vardus nuo
i?orini?, kurie fig?ruoja operacijoje APJUNGTI. ?io algoritmo sud?tingumas:
perkeliant element? i? ma?esnio s?ra?o ? didesn?, jis atsiduria galutiniame
s?ra?e, ma?iausiai 2 kartus didesniame negu buvo. Tod?l jokio elemento
negalime perkelti daugiau kaip log n kart?, tod?l laikinai sud?tingumas
vienam elementui ((log n), o visiems n elementams ((nlog n). Jei atliekama
m operacij? RASTI n iki n-1 karto apjungti, tai laikinai sud?tingumas yra
((MASK m,n(log n)), jei m >=nlog n, tai ?is algoritmas i? tikr?j? yra
optimalus, o kai m<<nlog n, tada yra geresni algoritmai.
Aibes galima vaizduoti med?iais:
aib? A atvaizudojama neorntuotu med?iu TA , kurio vir??n?s — aib?s
elementai. ?io med?io ?aknies vardas yra aib?s vardas. Tuo atveju operacija
APJUNGTI(A,B,C) atliekama sujungiant med?ius. Jai A<B , TA ?akn? reikia
padaryti med?io TB ?aknies s?numi. Be to TB ?aknies vard? pakesti ? C.
Operacija RASTI(i) atliekama einat nuo i- tosios vir??n?s ? med?io ?akn?,
kur yra patalpintas aib?s vardas.?ia operacija APJUNGTI atliekama per
pastov? laik? o RASTI sud?tingumas yra eil?s , nusakomas kelio ilgiu nuo i
? med?io vir??n?.?iuo atveju bedr? sud?tingum? nusako veiksmas RASTI.
Galima dar patobulinti ?? algoritm?: einant i? vir??n?s i ? ?aakn? r ,
pereinama per vir??nes : i, v 1,v2,…, vn,r . Galima padaryti visas ?ias
vir??nes taip pat ?aknies r s?numis. Tegul reikia atlikti operacijas
APJUNGTI ir RASTI aibi? rinkinyje kuri? elementai yra sveiki skai?iai nuo
1 iki n.Prad?ioje aib?s susideda ?s 1 elemento. Algoritmas susideda i? 3
dali?:1. Pradin?s strukt?ros organizavimas ;2. Operacija RASTI; 3.
Operacija APJUNGTI.
1. Kiekvienam elementui i kur 1( i (n sudaro mazg? Vi . Sudarome masyv?
SAKAI?IUS[VI ](1, VARDAS [VI](i T?VAS[Vi ](0 (kiekviena vir??n? Vi yra
medis ). Masyvas ?AKNIS[i] nurodo i-tos aib?s ?akn?. Masyvas ELEMENTAS[i ]
nurodo vir??n? , kuriai priklauso elem. i .
2. Algoritmas RASTI[ i ]…………….
Vidinio ciklo pagalba pereinama nuo duotos vir??n?s iki ?aknies .
Kiekviena vir??n? padaroma ?aknies s?numi for sakiniu.
3. Algoritmas APJUNGTI( i, j, k )……….
Prie didelio med?io prideda ma??. ?ia surandamos didesnio ir ma?esnio
med?io ?aknys ir didesnio med?io ?aknis padaroma ma?esnio med?io s?numi.
?io algoritmo sud?tingumas beveik tiesinis. Jei neb?t? kiekvienas pereitas
mazgas padaromas ?aknies s?numi , tai tokio algoritmo sud?tingumas b?t? ((n
log n ), o atlikus APJUNGTI proced?ra beveik tiesinis.ALGORITMAI GRAFUOSE
Paie?ka ? gyl?
Neorentuotame grafe paie?ka ? gyl? atliekama taip:Paimam pradin? vir?un? v.
Toliaui paimam jai incidentin? briaun? (v,w). Pereiname ? vir?un? w. Ir
t.t.Toliau i? w pereinam incidentine briauna ? nauj? vir??n?, jei ji nebuvo
aplankyta.
Jeigu esant eilin?je vir??n?je, einant visomis incidentin?mis briaunomis w
j? nesant, negalim patekti ?nauj? neaplankyt? vir??n?, tai gr??tam ?
ankstesn? vir??n?. Ir tt. kol neaplankom vis? vir??ni?. Briuanos, kuriomis
?jome per grafo G(V,E) vir?unes sudaro med?. G1(V,T) T-med?io briaunos.
Ne??jusios ? med?io briaunas, briauna vadiname atbuline.
Proced?ros PAIE?KA(v): ?ia grafas G(V,E) t?ri b?ti pateiktas kiekvienai
vir??nei incidentiniu briaun? s?ra?u L(v) visiems v(V. Algoritmo darbo
rezultate gaunam aib? T, kurioje sura?ytos visos med?io briaunos, likusios
briaunos atbulin?s. Sud?tingumas 7 ir 8-ame operatoriuose naujos vir??n?s
paie?ka reikalauja ((n) ?ingsni?. Proced?ra PAIE?KA(V), jei neskaityti
rekursyvyni? sav?s i?kvietim? per?i?ri tiek vir??ni?, kiek briaun?
incidenti?k? tai vir??nei. Pati proced?ra kiekvienai vir??nei i?kvie?iama 1
kart?, tuo b?du algoritmo sud?tingumas yra ((MAX(n, e)) n-vir?uni? sk e-
briaun? sk. t.y. sud?tingumas tiesinis. Paie?koje vir??nes galima
sunumeruoti taip kaip jos buvo aplankytos. Tarp 6 ir 7-to operatoriaus
statom operatori? SKAI?IUS(1; O tarp 1 ir 2 VIR_NR[v](SKAI?IUS;
SKAI?IUS(SKAI?IUS+1;
Bus pernumeruotos vir??n?s (pagal tai kaip aplankytos vir??n?s nuo 1 iki
n). Esant tokiam numeravimui visada v<w (t?vo Nr.<s?naus Nr.).Grafo labiausiai susijusi? dali? i?skyrimo algoritmas. Labiausiai
susijusios grafo dalys priklauso tai pa?iai ekvivalenti?kumo klasei.
Kiekvienai vir??nei galima para?yti APAT[v]=MIN({v}U{w}) w-vir??n? i?
labiausiai susijusios komponent?s. Jeigu surasime vis? vir??ni? APAT[v],
tai automati?kai i?skirsim susijusias dalis. Kiekvienos vir??n?s v skai?i?
APAT[v] kai bus per?i?r?tos visos ?emesn?s vir??n?s, gausime taip:
APAT[v] = MIN ({v}U{APAT[s] | s-vir??n?s v s?nus}U{APAT[w] | briauna v,
w(B (atbulini? briaun? aib?)} (1).
?ia vir??n?s sunumeruotos pagal paie?kos ? gyl? algoritm?.
Algoritmas t.y. fakti?kai skai?iavimas pagal (1) formul? arba
pakoreguota paie?kos ? gyl? proced?ra. Proced?ros paai?kinimas ?ia
atliekamas vir??ni? pernumeravimas. v<w jeigu v yra w prot?vis. 4 eil.
dyd?iui APAT[v] suteikiama pradin? reik?m? max gailma (jos Nr.) taip iki 9
operando. Toliau rekursyviniai i??aukiama ta pati proced?ra, kol
nepasiekiama grafo lapo. Tada L(v) tu??ia ir pereinam prie ankstesn?s
vir??n?s (paskutin?s nutr?kusios proced?ros). Kai 5 eilut?je paimama
vir??n? w, briauna (v,w) talpinam ? stek?, jei jos ten dar n?ra. (v,w)
briauna sutinkama 2 kartus, 1 kart? einant ? vir??n? v, kur w(L(v). 2
kart?, kai einam ? vir??n? w, nes v(L(w). Nustatyti ar briauna (v,w) pateko
? stek? galima ?itaip: jei v<w (w-“sena”) arba v>w (w=T?VAS[v] ). Tod?l kai
gr??tama prie nutr?kusios proced?ros paimama sekanti briauna, kuri gali
vesti ? nauj? vir??n? arba ? sen?. Tada 12 ir 13 operacijos pakuoreguoja
APAT[v] reik?m?. ?ita briauna taip pat patenka ? stek?. 12 op. pataikrina
ar ?i briauna patekusi ? med?.10 op. tikrina ar APAT[w] >=VIRNR[v], jei ne
tai 11 op. pakuoreguoja APAT[v]. Jei taip tai rei?kia aptikta labiausiai
susijusi komponent?, o i? steko i?stumia briaunas ?einan?ias ? j?
(komponent?) ir taip pat i?stumiama paskutin?.Paie?ka ? gyl? orentuotame grafe
Naudojant paie?kos ? gyl? grafuose algoritm? orentuotame grafe galima
i?skirti orentuot? med?i? mi?k?, jei kiekvienam mazgui v suskaupsime s?ra??
L[v], t.y. pasiekiame vir??ni? v aib? per 1 ?ingsn?. PVZ
V1 V2
V3
V5 V4V7 V8
V6
V1 V6
V2 V5 V7 V8
V4 V3
I?skirtas grafo mi?kas (med?i? linijos i?tisin?s, kitos punktyrin?s)
Paimam vir??n? v1. I? jos pasiekiam v2. PIE?KA(v2) i??aukia PIE?KA(v3). ?ia
Stop, niekur negalim patekti. Gr??tam ? v2 ir pereinam ? v4. V?l niekur
negalim patekti. Gr??tam ? v1. ?ia i??aukiama PAIE?KA(v5). I? ?ios vir??n?s
niekur negalim patekti, tod?l paimama sekanti “nauja” vir??n? v6 ir t.t.
Gauasi du med?iai.
Tokio algoritmo darbo rezultate gauname 4 tip? lankus:
1. Med?io lankai, kurie paie?kos metu veda ? naujas vir??nes 2.
Tiesioginiai lankai vedantieji nuo prot?vi? ? tiesioginius palikuonis (jei
(v,w) — tiesioginis lankas v<w) 3. Atbuliniai lankai vedantieji nuo
palikuoni? ? prot?vius 4. Skersiniai lankai, jungiantieji vir??nes, kurios
n?ra nei prot?viai nei palikuonys viena kitai (jei (v,w) – skersinis
lankas, tai v>w).Stipriai susijusi? dali? is?kyrimas orentuotame grafe
Stipriai susijusios dalys orentuotame grafe, tai i? bet kurios vir??n?s
egzistuoja kelias ? bet kuri? kit?. Kiekvienai orentuoto grafo vir??nei
skai?iuosime APATRY?YS[v]( MIN({v}U{w | kuri priklauso skersiniam arba
atbuliniam lankui (v,w) }). ?ia vir??ni? numeracija pagal pai?k? ? gyl?,
surandant med?ius. Vir??n? v orentuoto grafo stipriai susijusios dalie
?aknis bus tada, kai APATRY?YS[v](v. Atliekant paie?k? ? gyl? galima
apskai?iuoti APATRY?YS[V], o taip pat i?skirti stipriai susijusias dalis,
tam grafo vir??n?s talpinamos ? stek?, kai apeinant graf? sutinkamos.
Kiekvien? kart?, kai aptinkama stip. susijusios dalies ?aknis, visos
vir??n?s iki ?ios ?aknies i?stumiamos i? steko ir jos yra stipriai
susijusios dalies vir??n?s. Modifikuotos proc. paai?kinimas: APATRY?YS[v]
skai?iuojamas 4,9 ir 11 eilut?je 4 operacijoje suteikiama pradin? reik?m?
(vir??n?s Nr.). 9op. Priskiriam APATRY?YS[v](MIN(APATRY?YS[v], APATRY?YS[w]
)-tai lankams ?einantiems ? med?. 10 op. i?ai?kina ar n?einantis ? med?
lankas (v,w) yra atbulinis ar skersinis, o tai pat i?ai?kinama ar w( stekui
;priklauso stipriai susijusiai grafo daliai. 11 op. koreguojama reik?m?
APATRY?YS[v] (MIN(VIRNR[w], APATRY?YS[v] ). ?io algoritmo sud?tin-gumas yra
((MAX(n,e)) – tiesin?s, n-vir??ni? sk. e-lank? sk.Graf? susietumo matrica.
G(V,E) V-vir??ni? aib?, E-lank? aib?.
Susietumo matrica: |0 1 1 0|
( C ) ( |0 0 0 0|
|0 1 0 0|
|1 1 0 0|
cij ( {0, jei n?ra lanko i? i ? j 1,jei yra lankas i j
Susietumo matric? daugyba. Tegul turime grafus G1(V,E 1 ) ir G2 (V, E 2 )
su tom pa?iom vir??n?m, bet skirtingais lankais. Sudauginsime j? susietumo
matricas C(C1*C2 . Susietumo matrica C atitinka multigrafas sudarytas taip:
i? vi ? vj eina tiek lank?, kiek yra keli? i? vi ? vj , susidedan?i? i? 2
lank?: pirmas lankas (G1 , antras (G2. ?rodymas: ar egzistuoja vi ? vj
kelias vi vk vj per tarpin? vir??n? vk . Galima patikrinti tokiu b?du
c1ik*c2kj(1; c1ik(G1 , o c2kj(G2 . Kei?iant k nuo 1 iki n patikrinam ar
egzistuoja kelias per visas tarpines vir??nes. Sumuojant, gaunam toki?
keli? sk. cij((k(1 n c1ik* c2kj. O tai atitinka matric? daugyba, cij yra
matricos C elementai. Tegul C yra graf? susietumo matrica. Tada C*C
elementai parodo kiek yra skirting? keli? i? vir??n?s vi ? vj ,
susidedan?i? i? dviej? lank?.
|0110| |0110| |0100|
( C )*( C ) ( |0000| |0000| ( |0000|
|0100| |0100| |0000|
|1100| |1100| |0110|
c12(1 rodo keli? v1 v3 v2 .
( C )( C )( C ) Parodo kiek keli? yra vj ir vi susidedan?i? i? 3 lank?.
|0100| |0110| |0000|
(C)(C)(C)( |0000| |0000| ( |0000|
|0000| |0100| |0000|
|0110| |1100| |0100|
1 rodo, kad tarp v4 ir v2 yra kelias susidedantis i? 3 lauk?, tai v4 v1 v3
v2 . (C)4 rodyt? keli? sk. susidedan?i? i? keturi? lank?, ?ia n?ra toki?
keli?. Kai n?ra cikl?, tai gauname nulin? matric?. (C)n – yra tikslas
skai?iuoti iki (C). Toliau bus rodomi tik ciklai. Jei susumuosime visas
(C)+(C)2+…+(C)n+
|10..0|
+ |01..0|
…
|00..1|
matricas, tai gausime keli? sk. i? vi ? vj . Jei atitinkamas elemntas
cij>0, tai tas rodo, kad yra kelias tarp vir??ni? vi vj . Matricos (n*n)
daugybai reikia atlikti n3 daugybos veiksm?. Matricai (C)n gauti, reikia
~n4daugybos veiksm?. Kartais keliamas u?davinys surasti ar egzistuoja
kelias tarp vis? grafo vir??ni?. T.y. surasti matric? (L), kurios
lij({0, jei n?ra kelio tarp vi ir vj 1, jei yra toks kelias.
Matom, kad toks u?davynys gali b?ti i?spr?stas dauginant ir sudedant
matricas. Grafas atitinkantis susietumo matric? (L) vadinamas refleksiniu
-tranzitiniu grafo u?darymu.
Paai?kinimas (L) matricos radimo algoritmo: ?ia visada ckij(1, jei yra
daugiau keli?. Tod?l 5 op. 1+1(1. T.y. atliekami veiksmai su 0 ir 1. ?ia 5
op. atliekamas n3 kart?, nes kartu atliekamas sumavimas.Trumpiausio kelio radimas
Min kelio tarp vir??ni? radimo algoritmas:
begin
1. for i(1 until n do c0ii(0;
2. for 1( i,j( n ir (j do c0ij(cij;
3. for k(1 until n do
4. for 1( i, j( n do
5. ckij( MIN(ck-1ij , ck-1ik +ck-1kj);
6. for 1( i, j( n do lij(cnij
end
V2 1 ir 2 op. duos matric? Cij0
V1 2 | 2 8 5|
5 V3 (Cij)( |3 ( (|
|( 2 (|
| 0 8 5| k(1 |0 8 5|
(C0 ij)(| 3 0 8| (C1ij)(|3 0 8|
|( 2 0| |( 2 0|
C112(MIN(C012 , C011+C012)(8
C123(MIN(C023 , C021+C013)(8 ?vertina mas kelias v2v1v3 per v1.
k(2 |0 8 5| C231(MIN(C131 ,C132+
(C2 ij)(| 3 0 8| + C121)(5
|5 2 0| ?vertinamas kelias v3v2v1 per v2.
k(3 |0 7 5| C312(MIN(C212 ,C213+
(C2 ij)(| 3 0 8| + C232)(7
|5 2 0| ?vertinamas kelias v1v3v2 ,
kuris trumpesnis negu tiesioginis v1v2.
?io algoritmo sud?tingumas ((n3),nes ? op. atliekamas n3 kart? , o ? op. n2
kart?. 1,2 op.taip pat n2 kart?.U?davinys su vienu ?altiniu ( Deiks-tros algoritmas)
Randami trumpiausi atstumai nuo vienos vir??n?s iki kit? garfo vir??ni?.
Grafas G=(V,E), pradin? vir??n? v0(V. Duotos reik?m?s l(vi ,vj ) ir l(vi
,vj )= +(, jei n?ra lanko vi vj . Sprend?iant ?? u?davin?, sudaroma
vir??ni? aib? S(V.Taip trumpiausias atstumas nuo v0 iki v(S eina per
vir??nes (S.V0 2 V1
7 3
10 6 V5
4
V4 5 V3I_| S_ |w|D[w]|D[v1]|D[v2]|D[v3]|D[v4]
Prad?.| {v0} | — | — | 2 | +( | +( | 10
1. |{v0,v1} | v1| 2 | 2 | 5 | +( | 9
2. |{v0,v1,v2} | v2 | 5 | 2 | 5 | 9 | 9
3. |{v0,v1,v2,v3} | v3 | 9 | 2 | 5 | 9 | 9
4. |{v0,v1,v2,v3,v4}| v4 | 9 | 2 | 5 | 9 | 9begin
1. S({v};
2. D[v](0;
3. for v(V,kaiS={v}do D[v](l(v,v)
4. while S(V do
begin
5. paimti vir??n? w(V, nepriklausan?i? S, kuriai D[w]-mminimali (w(V-S)
6. prid?ti vir?un? w prie aib?s S;
7. for v(V-S do
8. D[v](MIN(D[v];D[w]+l(w,v));
end;
end;
5 op. atliekamas n kart? (n-vir??ni? ksai?ius), 7,8 operatoriai
atliekami n kart? (max). 4 op. wile ciklas ?stato kiekivien? vir??n? ? S.
Tod?l ciklas i? 4,5,6,7,8 operatori? atleikamas n2 kart?, tod?l algoritmo
sud?tingumas ((n2) ( 3 operatorius atleikamas n kart?, tod?l algoritmo
sud?tingumui ?takos neturi ).
