Реферат: Алгоритмы

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=1

L (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 > F

k, 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< 2

k-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 *2

i-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 S

2=ëS1/2û. Si+1=ëSi

/2û ; Ni+1=Ni±éSi+1/2ù .

Jeigu įrašų nėra, tai paskutinėje iteracijoje S

i+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 N

1=2k-1. Gaunam 2 ne vienodas dalis. Jei K<F1, tai

imam pirmą dalį ir elgiamės kaip idealiu atveju. Jei K>F

1, 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 q(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). a

1 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=1

n ((n-1)+T(j-1)+T(n-j)) = n-1+ 1/n åj=1

n (T(j-1) + T(n-j)) = n-1 + 2/n åj=0

n-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 +2

2 +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 = a

2b + 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ą q(n).

Jei a=c, tai algoritmo sudėtingumas q(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 q(nlog4n), log2

n > 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(n\c)+f(n), kur a≥1,

c≥1, f(n)-teigiama f-ja. 1) Jei f(n)= q(n(logc

a)-e) ,tai T(n)= q(nlogca). 2)

Jei f(n)= q(nlogca) ,tai T(n)= q(nlog

ca . log n. 3) Jei f(n)= q(n(logc

a)+e) ,tai T(n)= q(f(n)), jei af(n\c)≤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=1

T(n-1)+n-1, n>1 ;

T(n) = n(n-1)/2, o algoritmo sudėtingumas q(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 q( 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: M

i*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 + r

i-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 r

j. 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 m

i, 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

q[(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 l

max. 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

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 q(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ų:

Pagal tai ir

algoritmo sudėtingumas bus q(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:

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 q(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, .. t

k. Vidurkis bus t = 1/Kåi=1K

(ti), vidurkis - atsitiktinis dydis.

Dirpersija bus : S2(t)=

i-t)2= =

ti2-2`t ti +`t2) = =

ti2-2t

ti+K`t2]= =

ti2-2(

ti)* *t

i + K/K2 (

ti)2] =

* *[ ti

2 - (

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 [

ti] = 1/K2

D(ti) = 1/K*D(t); D - tikroji dispersija;S-įvertinimas.S2

(`t)=S2(t)/K arba ištraukus šaknį: S(t) = S(t)/

; |`t - m|<e - t.y. artiname ir reikalaujame, kad jos skirtusį e. Kad

išraiška turėtų prasmę, mes parašome: P<e=p.Padalinkime abi puses iš vidutinės kvadratinės

paklaidos.

P `t - m =p. Pažy-mėkime tp = e/

S(`t) (2). m- vidurkio matematinė viltis.`t - m įvertinimas tada

iš formulės (2) išeina, kad e = tp*S(`t) = tp

. Galim parašyti : t-e< m< t+e, tada t - tp

< m <`t + tp

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+- e1

(intervalinis įvertinimas). Tą patį atlie-kam su kita programa`t

2, S2(t2), `t2 +- e2

Jei palyginsim tik `t1 ir `t2 tas dar nerodo, kad vienas

iš šių algoritmų yra geresnis, nes `t1 ir `t

2 - atsitiktiniai dydžiai, todėl palyginimų rezultatas taip

pat gali būti atsitiktinis. Geriau lyginti `t1 ± e1

ir `t2 ± e2. Jei jie nepersidengia, tai yra pagrindo

teigti, kad viena programa yra geresnė už kitą.Arba galima

lyginti ir taip:

1.paskaičiuojam Dt=t1-t2 ; D(D`t ) = D(`t1

)+D(`t2); Jeigu šie atsitiktiniai dy-džiai nepriklausomi.

S2(D`t ) = S2(`t1 ) + S2(`t2

) = S2(t1)/K + S2(t2)/K ;

S(D`t)=Ö((S2(t1)+S2(t2))/K);

D`t - tpS(D`t )<m(D`t )< D`t + tpS(D`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, `t

2, S2(t1)=

[t21I

- 1/K(t1I)

2]; S2(t2)=

[t22I

- 1/K(t2i)

2]

Tarpusavio momentai M1=

(t1i-`t1)(t2i-`t2)=

(t1it2i-`t1t2i -`t2t

1i+`t1`t2)=

[ t1it

2i - `t1åt2i - `t2åt1i

+ K `t1`t2] =

[t1it

2i-1/K t1i

t2i] ; Dti= t1i - t2i ; D(Dt)=D(t

1)+ D(t2)-2M12 (1); Koreliacijos koef. K12

= M12 / s(t1)s(t2); Jis gali kisti nuo -1 iki

+1. M12=K12s(t1)s(t2). Jei K12

=1, tai reiškia teisinę funkcinę priklausomybę. Jei K12

=1 ir s(t1)=s(t2), tai jei įstatysim į 1

-ają formulę, tai gausime D(Dt)=0. Tačiau tai idealus atvejis, o

praktiškai K12 < 1.

Jei K12 > 0, tai D`t = `t1- `t2, S2

(Dt)»S2(`t1)+ S2(`t2)-2`M12

t.y. dispersija mažesnė nei nepriklausomų dydžių atvju.

S2(D`t)» S2(t1)/K+ S2(t2

)/K - 2K12S(`t1) * S(`t2)= S2(t

1)/K+ S2(t2)/K - 2M12/S(t1)S(t

2)* S(t1)/Ök * S(t2)/ÖK = S2(t

1)/K+ S2(t2)/K - 2M12/K t.y. ir vidurkio

dispersija yra mažesnė, nes atsiima 2M12/K. Atitinkamai

intervalinis įvertinimas: D`t - tpS(D`t) <m (Dt) < D`t +

tpS(D`t) (1). Kadangi S2(Dt) 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 Dti,

i=1,2,....,K. faktiškai gauname atsitiktinius dydžius. Dt = 1/K

Dti; S2(Dti)=

[Dti2

-1/K(Dti)

2]

S2(D`t)=S2(Dti)/K; S(D`t)= S(Dti)/ÖK

D`t - tp S(D`t) < m(Dt) < D`t + tp S(D`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

élog(i+1)ù palyginimų.

élog(i+1)ù =

élog(i)ù = nélog(n)]-2élogn

ù + 1 tokio algoritmo sudėtingumas q(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

(n-i)=i=n(n-1)/2, tai

šio algo-ritmo sudėtingumas: q(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 q(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 q(n log n).

Rūšiavimas suliejimu (sujungimu)

n elementų dalinami į 2 dalis:

ir Š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)=

Š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 q(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:

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=1

nf(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 q(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 + e

e - 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ų sekos

Radus 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 + P[ai > aj] × 1 = 1+ 1/2 × 1 = = ln n + g +1/2n + e

Ši eilutė diverguojanti, t.y. didėjant n, jos

reikšmė didėja.(Eulerio formulė) čia g=0,577; e-

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

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

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 a1

Jei 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)=

Bendras šios srities sprendinys:

(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 [Si=1k-1 f(n-i)+Sni

=k+1 f(i -1)]=n-1+1/n [Sn-1i=n-k+1 f(i)+ [Si=k

n-1 f(i )]

Čia įrodyta, kad f(n)<= 4n , t.y vidutiniškai šis alg,

yra tiesinis q(n).

Jeigu nevykusiai pasirenkame skaidymui elem, tokio alg, sudėtingumas q(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 q(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) = q( 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<=a, bÌS ir S2=b

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 S 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.,T

2},...,{Vk.,Tk} . V1 ,V2, .. V

k-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--------------

w1 ir w2 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 q(eloge).e-briaunų sk.

Tuomet 3-čio operatoriaus sudetingumas proporcingas viršūnių

sk. n q(n). Laikas reikalingas surasti aibei w1 ir w2

įkurias įeina viršūnes V ir w ir jų sujungimas, jei

priklauso skirtingoms aibėms yra beveik tuščias: q(n) . O jei

tiksliau t.y. q(n G(n)), kur G(n) - atvirkštinė f-jai F(n) =2

F(n-1)

Jeigu naudosime sąrašų struktūrą, tai (7,8)

šios dalies alg. sudetingumas q( MAX(e,n log n)). Todėl matom, kad

visumoje Kraskalo algoritmo sudėtingumas yra q(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)=2

h(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 q(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 q(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 s 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 sn. (ir blogiausiu ir

vidutinišku atveju). Paskirstymo metode s kartų atliekant

operaciją PRIKLAUSYTI jo sudėtingumas vidutiniškai yra q(s).

(jei n < m) ir blogiausiu atveju q(sn). 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 s 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 a

i 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 q(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+C

k, j . Tokių sumų yra j-1. todėl šios dalies

sudėtingumas yra q(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 q(n

3).

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 q(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 q(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 q(log n), o visiems n elementams q(nlog n). Jei atliekama m

operacijų RASTI n iki n-1 karto apjungti, tai laikinai sudėtingumas

yra q(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,v

2,..., 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ų q(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 q(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 q(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}UAPAT[s] Ubriauna 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 V4

V7 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ė v

6 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}Ulankui (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

q(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; c1

ikÎ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 ck

ij=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 q(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 v

0 iki vÎS eina per viršūnes ÎS.

V0 2 V1

7 3

10 6 V5

4

V4 5 V3

I_| 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 | 9

begin

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 q(n2) ( 3 operatorius atleikamas n

kartų, todėl algoritmo sudėtingumui įtakos neturi ).