Реферат Алгоритмы
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
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 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). 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ą 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), 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(n\c)+f(n), kur a≥1, c≥1, f(n)-teigiama f-ja. 1) Jei f(n)= q(n(logca)-e) ,tai T(n)= q(nlogca). 2) Jei f(n)= q(nlogca) ,tai T(n)= q(nlogca . log n. 3) Jei f(n)= q(n(logca)+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=1T(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: 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 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 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
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ų:
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:
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, …. tk. Vidurkis bus t = 1/Kåi=1K (ti), vidurkis - atsitiktinis dydis.
Dirpersija bus : S2(t)=
Š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 [
P {|`t - m |/S(`t)<e / S(`t)}=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
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`t2, S2(t2), `t2 +- e2
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 ± 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, `t2, S2(t1)=
Tarpusavio momentai M1=
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(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: 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
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
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
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:
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=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 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ų 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 +
Š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
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=kn-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|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 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.,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--------------
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) =2F(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
h(a)=
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 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:
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+Ck, 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(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 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,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ų 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}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 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ė 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 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; 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 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 v0 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 ).
