algoritmai

-1-PAIEŠKA PAPRASTAME SĄRAŠE1.1. Nuosekli paieškaTegu į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 interpoliavimasJei sąrašai surušiuoti ir žinomas pirmo iraš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škaNaudojama 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.:

-9-RŪŠIAVIMO ALGORITMAIK-mačių kortežų rūšiavimasTegul mes turime seką A1 A2 … An k-mačių kortežų, t.y., A erdvinis Ai elementas, sudarytas iš ai1 ai2 … aik.Reikia šią seką ruš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žiu turi buti tuščios. Duomenis A1 A2 … An iš pradžiu surašom i sąrašą EILE. Paimam eilini kortežą Ai iš EILĖS ir patalpinam į pagalbinę eilę Q(j) pagal analizuojamos komponentės reikšmę. Taip darom tol, kol bendra EILĖ ištuštėja. Visi kortežai atsiduria pagalbinėse eilėse. Po to jie suduriami: Q(0) Q(1)…Q(m-1) ir jie sudaro vieną bendrą eilę EILĖ. Kai praeinam pro visas komponentes, tai EILĖ bus surūšiuota. Algoritmo sudėtingumas yra tiesinis [(n+m)/k]. Naudoti šį metodą neverta, kai n yra mažas.

-17-t2t1i+t1t2)= [ t1it2i – t1t2i – t2t1i + K t1t2] = [ t1it2i-1/K t1i t2i] ; ti= t1i – t2i ; D(t)=D(t1)+ D(t2)-2M12 (1); Koreliacijos koef. K12 = M12 / (t1)(t2); Jis gali kisti nuo -1 iki +1. M12=K12(t1)(t2). Jei K12=1, tai reiškia teisinę funkcinę priklausomybę. Jei K12=1 ir (t1)=(t2), tai jei įstatysim į 1 -ają formulę, tai gausime D(t)=0. Tačiau tai idealus atvejis, o praktiškai K12 < 1. Jei K12 > 0, tai t = t1- t2, S2(t)S2(t1)+ S2(t2)-2M12 t.y. dispersija mažesne nei nepriklausomu dydžiu atvju. S2(t) S2(t1)/K+ S2(t2)/K – 2K12S(t1) * S(t2)= S2(t1)/K+ S2(t2)/K – 2M12/S(t1)S(t2)* S(t1)/k * S(t2)/K = S2(t1)/K+ S2(t2)/K – 2M12/K t.y. ir vidurkio dispersija yra mažesne, nes atsiima 2M12/K. Atitinkamai intervalinis įvertinimas: t – tpS(t) F1, tai ieškomas įrašas yra antroje dalyje, kuri mažesnę už pirmąją. 2r-1-1K2. 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 surušiuosime, tai sumalinis pakeitimu sk. bus n(n-1)/4. Algoritmo sudetingumas (n2).

-19-Binarinis įterpimo algoritmasIeškant elementui vietos jau surūšiuotoje sekoje mes galima naudoti binarinį paieškos metodą. Iterpiant i+1 elementą i i-tojo dydžio surušiuotą sąrašą reikia atlikti log i  + 1 = log(i+1) palyginimą. Visada reiks atlikti max palyginimu, nes iterpiamo dydžio tame sąraše nera. Rušiuojant n-tojo dydžio sąrašą mums reikes atlikti log(i+1) palyginimų. log(i+1) = log(i) = nlog(n)]-2logn + 1 tokio algoritmo sudėtingumas (nlogn).Rūšiavimas išrinkimuIš pradžiu išrenkame didžiausią elementą. Ji 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: (n2).Šis alg. gali būti geriausias vienu metu ieškant max ir min.

-5-1) Principas – ‘Skaldyk ir valdyk’Sprendžiant koki nors uždavini kartais jie suskaldomi i du. Rasti ju sprendimai apjungiami ir gaunamas uždavinio sprendimas. Savo ruožtu suskaidyti uždaviniai gali buti toliau skaidomi. Visiems uždaviniams spręsti naudojama ta pati rekursyvi procedura. Pavyzdžiui, reikia rasti aibeje iš N elementu max ir min elementą. Surandant max elementą reikia (n-1) palyginimu. Taip pat ir ieškant min reikia (n-2) palyginimu (su max nelyginam). Ieškant min ir max elementu reikia 2n -3. Tarkim n2k. Visą aibę suskaldom i 2 dalis. Kiekvienoje iš ju 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 procedurą, algoritmo sudetingumas sumažeja.

-13-i patenka į paskutinęprieš pirmąji poziciją elementą (gale)=1/(i+1)(1+2+…+i+i) = 1/(i+1)*((i+1)/i ) /2 + i / ( i + 1 ) = i / 2 + i / ( i + 1 )Tiek pagal max,tiek pagal vidutinį palyginimų skaičių šio algoritmo sudėtingumas yra (n2)

Ekspermentinis statistinis algoritmų tyrima.s Šiuo metodu pvz. tiriant rūšiavimo algoritmus mums reikia parašyti atitinkamą programą, paiimti atsitiktinę seką iš n duomenų ir atlikti skaičiavimus, pvz.: fikstuoti laiką t1, po to paimame kitą seką ir gauname laiką t2 po to paimame kitą seką taip pat iš n duomenu ir gauname laiką t3 ir tokius bandymus kartojame k kartų. Gauname atsitiktinių dydžių imtį t1, t2, …. tk. Vidurkis bus  = 1/Ki1K (ti), vidurkis – atsitiktinis dydis. Dirpersija bus : S2(t)= i-t)2= = ti2-2t ti +t2) = = ti2-

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

-7-Balansavimas (skaidymas į vienodas dalis). Reikia surūšiuoti n ilgio masyvą didėjimo tvarka. 1.surandam min, kurį sukeičiam su pirmu, po to iš (n-1) elemento surandam min ir sukeičiam su antru ir t.t.. Rekursyvinė lygtis aprašanti palyginimų sk.: T(n)  {0, n1T(n-1)+n-1, n>1 ; T(n)  n(n-1)/2, o algoritmo sudėtingumas (n2). Čia skaldymas į dvi nelygias dalis: į vieno elemento ir (n-1).2. Gaunamas suskaldžius uždavinį į dvi lygias dalis  n/2. Tarkim, kad n  2k. Viena dalis nuo x1 iki xn/2 , o kita nuo xn/2+1 iki xn. Šias dalis surūšiuojam ir sujungiam palyginant minimalius elementus. Sujungimui reiks maksimum n-1 palyginimų. Tokį skaidymą galima rekursyviai tęsti toliau, kol lieka dalyse po 1 elementą. Rekursyvinė lygtis aprašanti tokį algoritmą yra: T(n)  {0, n1 2T(n/2) + n – 1, n>1. Šio algoritmo sudėtingumas ( n log n).

-15-P {|t – m |/S(t)< / S(t)}=p. Pažy-mekime tp = / S(t) (2). m- vidurkio matematinė viltis.t – m įvertinimas tada iš formulės (2) išeina, kad  = tp*S(t) = tp . Galim parašyti : t-< m< t+, 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+- 1(intervalinis įvertinimas). Tą patį atlie-kam su kita programat2, S2(t2), t2 +- 2Jei palyginsim tik t1 ir t2 tas dar nerodo, kad vienas iš šių algoritmų yra geresnis, nes t1 ir t2 – atsitiktiniai dydžiai, todel palyginimu rezultatas taip pat gali buti atsitiktinis. Geriau lyginti t1  1 ir t2  2. Jei jie nepersidengia, tai yra pagrindo teigti, kad viena programa yra geresnė už kitą.Arba galima lyginti ir taip:

-23-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>1f(0)f(1)bf(2)2c+2/2[f(0)+f(1)]2c+2bkf(3)3c+2/3[f(0)+f(1)+f(2)]3c+2/3[2b+2c+2b]3c+8/3b+4/3c(8b+13c)/3. Įrodyta, kad visada galioja lygybė f(n) < kn ln n. Todėl QUICKSORT algoritmo vidutinis sudėtingumas yra (n ln n). Čia nevertinta, kad mažos sekos gali buti rušiuojamos kitu budu, kas dar pagreitina ši algoritmą.

Optimalus rūšiavimas. Jei yra n elementų, tai variantų iš viso gali būti n!. n=3, 3!=6 Minimalus palyginimų sk. blogiausiu atveju = 3. Ir laikom, kad ši schema optimali. Tegul S(n) – minimalus palyginimų sk. blogiausiu atveju, rūšiuojant n elementų: S(3)=3 Pilname k-tojo lygio binariniame medyje, paskutiniame lygyje yra 2K mazgų. K=S(n).n! =< 2 S(n), tada S(n) >= log n! =n log n – n/ln2+1/2 log n +   – paklaida. (Stirlingo formulė)

-8-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žu prie dideliu. Atsakymai prisimenami lenteleje ir uždaviniai jungiami, kad butu išspręstas visas uždavinys ir gautas optimumas. Pvz. sudauginant n matricu yra labai svarbus daugybos eiliškumas, kuris nulemia bendrą veiksmu 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 veiksmu 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.

-16-1.paskaičiuojam t=t1-t2 ; D(t ) = D(t1)+D(t2); Jeigu šie atsitiktiniai dy-džiai nepriklausomi.S2(t ) = S2(t1 ) + S2(t2) = S2(t1)/K + S2(t2)/K ; S(t)=((S2(t1)+S2(t2))/K);t – tpS(t ) aj]  1 = 1+ 1/2  1 = = ln n +  +1/2n + Ši eilutė diverguojanti, t.y. didėjant n, jos reikšmė didėja.(Eulerio formulė) čia 0,577; - paklaida.

-6-Rekurentinių lygčių sprendimasT(n)  {b, n1aT(n/c) + bi, n>1 a,b,c-teigiamos const.nck; klog cn.T(1)  bT(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 ac, turim didėjančią geometrinę progresiją. Tuomet T(n) greitai dideja didejant n, tai eksponentinio sudetingumo algoritmas. Uždavini suskaidžius i 4 dalis ir tokiu daliu paemus 4 – ias: a=c=4, gauname (nlog4n), log2n > log4n. Kas bus, kai n≠ck? Išvestos formulės netinka, bet paėmus atvejį, kai n’=ck > n, išvados galioja. Uždavinys gali buti sprendžiamas su rekursija arba be jos, tačiau uždavinio sudetingumas nepasikeičia. Su rekursija algoritmas sprendžiamas šiek tiek ilgiau.

T Apie rekurentinės lygties tipo T(n)=aT(nc)+f(n), kur a≥1, c≥1, f(n)-teigiama f-ja. 1) Jei f(n)= (n(logca)-) ,tai T(n)= (nlogca). 2) Jei f(n)= (nlogca) ,tai T(n)= (nlogca . log n. 3) Jei f(n)= (n(logca)+) ,tai T(n)= (f(n)), jei af(nc)=bf(n) (b>1 dideliems n).

-14-2t ti+Kt2]= = ti2-2( ti)* * ti + K/K2 ( ti)2] = * *[ ti2 – ( 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ę vilti.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|< – t.y. artiname ir reikalaujame, kad jos skirtusį . Kad išraiška turėtų prasmę, mes parašome: P{|t – m |<}=p.Padalinkime abi puses iš vidutinės kvadratinės paklaidos.

-22-Rūšiavimas suskaldymu (quick sort).Turime seką iš n elementu. 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 kuri. Generaliniai elementai gali buti parenkami ivairiai: pirmas, atsitiktinis, mediana (vidurinis). Skaidyti pagal medianą geriausia. Galima paimti nedidelią imti iš keliu sekos elementu ir surasti medianą. Imant visada pirmą elementą, blogiausias atvejis gaunasi, kada seka yra surušiuota. Tada seka suskaldoma i vieną elementą ir visą likusią. Gausis taip kaip ir kituose algoritmuose. Tuo atveju algoritmo sude-tingumas (n2), o visais kitais atvejais žymiai geriau. Šis algoritmas gerai veikia didelem sekom, o taip pat reikia tinkamai parinkti generalini elementą. Vid. veiksmu sk. yra:

-4-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) elementu yra kaireje puseje, o (n-j) dešineje. Istatant (j-1) elementu i kairi pomedi, reikia (j-1) palyginimu su šaknimi plius T(j-1) ((j-1)+T(j-1)). Analogiškai dešiniam pomedžiui reikia (n-j) palyginimu 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.

-12-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 (n2).Vidutiniškai bus mažiau palyginimu.Šiuo budu rušiuojant masyvus (paprastus) patogiau pradeti elemtu lyginimą nuo suruš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: je

-20-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ą i sekos galą ir kadangi jis jau savo vietoje, todel jis daugiau nenagrinejamas, o seką sumažiname 1 ir turime jau ne rušiavimo medi. Mums vel reikia atstatyti rušiavimo medi, kad pirmasis elementas butu didžiausias t.y. pradedant nuo n/2 eiti link pirmo ir kiekvieną elementą reikia sukeisti vietomis su didesniu sunumi. Taigi mums reikia tam tikrą elementą perstumti per kažkiek lygiu. Perstumiant elementą per 1 lygi reikia atlikti 2 palyginimus: (2i) ir (2i+1) tarpusavyje ir didžiausią iš ju su palyginamu elementu. Perstumiant elementą per n lygiu reikia atlikti 2n palyginimu, todel blogiausiu atveju, perstumiant n elementu, palyginimu sk. neviršins 2nm.(m-lygiu sk. , be pirmos viršunes). Kai reikiia perstumti 1 elementą, maksimaliai reikia f(n)2log n palyginimų. Tiksliau: f(n)  log n + log (n-1). Perstumiant n viršūnių maksimaliai turėtume 2nlog n palyginimų. Algoritmo sudėtingumas bus (n log n). Tačiau įrodyta, kad pirmoje dalyje reikės ne daugiau kaip 2n-4 palyginimų, todėl pirmos dalies algoritmo sudėtingumas yra tiesinis, nes čia reikia peržiureti tik n/2 elementu, o visumoje šio algoritmo sudetingumas (n log n).

-2-1) Posąrašio ribu 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 imam apatinę dali, 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-1k, tai imame S1, kuriame yra (i-1) ele-tų. Jei iw).

-29-5.Dviejų mažiausių: P(2,n-2)=n+log(n-1)-26. 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žiausiu elem, P(k,n-k).b. surasti k-ąji 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 i veiksmus su aibemis. Išanalizuojam ivairias Duomenu Strukturas ir pasirenkam labiausiai tinkamą. Gero alg. Sukurimas neatski-riamas nuo tinkamos DS pasirinkimo. Pagr. mat. veiksmai su aibemis budingi informacines 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 rastu dvejose aibese, tada veksmas nenustatytas.

-37-Optimalaus binarinės paieškos medžio algoritmo sudėtingumas yra (n3) .Procedūros MEDIS(i, j) sudėtingumas yra tiesinis , nes ji iššaukiama n kartų. 8-tame operatoriuje ieškant m reikia palyginti sumas Ci, k-1+Ck, j . Tokių sumų yra j-1. todėl šios dalies sudėtingumas yra (j-i). j įgija reikšmę n , o i-nulį. tai maksimalu atveju. Išorinis ciklas 4-10 atliekamas n kartų , o vidinis ciklas 5-10 nedaugiau n kartų kiekvienai išorinio ciklo iteracijai . Todėl algoritmo sudėtingumas su gera atsarga yra (n3).

OPERACIJŲ APJUNGTI IR RASTI ATLIKIMO ALGORITMASKruskalo algoritmų ypatumai:1.Apjungiamos visada nepersikertančios aibės.2.Aibių elementai tai viršūnių numeriai nuo 1 iki n.Čia uždavinio sprendimui yra papras-čiausiai duomenų struktūra – masyvas iš n elementų. R(i), (i=1,2,…,n).Čia kiekvienas elementas R(i) yra i-ta viršūnė. Iš pradžių kiekvienas elementas sudaro atskirą aibę, todėl surašoma R(i)=i ir tai reiškia aibės numerį, kuriai priklauso šis elementas. Operacija RASTI(i) atliekama tiesioginiu kreipimosi į R(i). ir gaunamas aibės numeris, kuriai priklauso šis elementas. Kreipimosi laikas pastovus, todėl atliekant n tokių operacijų, sudėtingumas yra tiesinis (n). čia yra geriausias atvejis. Norint atlikti operaciją APJUNGTI(A,B,C) reikia peržiureti visą masyvą

-45-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 jSusietumo 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šunę 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 .

-31-////////// P R O G R A M A————–1 ir 2 yra medžiai miške. Šiame algo-me E – grafo briaunu aibe. T- ekonominio medžio briaunu aibe. VS – grafo miško medžiai kurie apjungiami i ekonomini medi:Iš pradžiu VS- atskiras grafo G viršunei kaip vieno elem, aibei(viena viršune-vienas miško medis).Kadangi aibėje E yra surašytos briaunos,kurias rekia imti su minimaliu svoriu. Tai galbūt naudinga atlikti jų surūšiavimą. Tai gali būti paimtas alg, kurio sudetingumas (eloge).e-briaunų sk.Tuomet 3-čio operatoriaus sudetingumas proporcingas viršūnių sk. n (n). Laikas reikalingas surasti aibei 1 ir 2 įkurias įeina viršūnes V ir  ir jų sujungimas, jei priklauso skirtingoms aibėms yra beveik tuščias: (n) . O jei tiksliau t.y. (n G(n)), kur G(n) – atvirkštinė f-jai F(n) =2F(n-1) Jeigu naudosime sąrašu strukturą, tai (7,8) šios dalies alg. sudetingumas ( MAX(e,n log n)). Todėl matom, kad visumoje Kraskalo algoritmo sudėtingumas yra (e log e), kurį nulemia rūšiavimas.

-39-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 aibes susideda šs 1 elemento. Algoritmas susideda iš 3 daliu:1. Pradines strukturos 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 sunumi. Šio algoritmo sudetingumas beveik tiesinis. Jei nebutu kiekvienas pereitas mazgas padaromas šaknies sunumi , tai tokio algoritmo sudetingumas butu (n log n ), o atlikus APJUNGTI procedūra beveik tiesinis.

-47-Trumpiausio kelio radimasMin kelio tarp viršūnių radimo algoritmas: begin1. 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 do4. for 1 i, j n do5. 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)8C123MIN(C023 , C021+C013)8 Įvertina mas kelias v2v1v3 per v1.k2 |0 8 5| C231MIN(C131 ,C132+(C2 ij)| 3 0 8| + C121)5 |5 2 0| Įvertinamas kelias v3v2v1 per v2. k3 |0 7 5| C312MIN(C212 ,C213+(C2 ij)| 3 0 8| + C232)7 |5 2 0| Įvertinamas kelias v1v3v2 ,kuris trumpesnis negu tiesioginis v1v2. Šio algoritmo sudėtingumas (n3),nes į op. atliekamas n3 kartų , o š op. n2 kartų. 1,2 op.taip pat n2 kartų.

-32-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-1A-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 i sarašo elementą a  S, kur h(a)=i. Tai operacijos ĮSTATYTI(a,s) atlikimui reikia paskaičiuoti h(a) ir po to peržiureti sąrašą, i kuri nurodo h A[h(a)]. Jei elem A ten nera, tai ji reikia istatyti sarašo gale. PAŠALINTI(a,s) atliekama analogiškai. Tas pats ir PRIKLAU-SYTI(a,s). Blogiausiu atveju gali

-40-ALGORITMAI GRAFUOSEPaieš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. Neiejusios i 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 atbulines. Sudėtingumas 7 ir 8-ame operatoriuose naujos viršūnės paieška reikalauja (n) žingsniu. Procedura PAIEŠKA(V), jei neskaityti rekursyvyniu savęs iškvietimu peržiuri tiek viršuniu, kiek briaunu incidentišku tai viršunei. Pati procedura kiekvienai viršunei iškviečiama 1 kartą, tuo budu algoritmo sudetingumas yra (MAX(n, e)) n-viršunių sk e-briaunų sk. t.y. sudėtingumas tiesinis. Paieškoje viršūnes galima sunumeruoti taip kaip jos buvo aplankytos.

-48-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 ši uždavini, sudaroma viršuniu aibe SV.Taip trumpiausias atstumas nuo v0 iki vS eina per viršūnes S. V0 2 V1 7 3 10 6 V5 4 V4 5 V3I_| S_ |w|D[w]|D[v1]|D[v2]|D[v3]|D[v4]Pradţ.| {v0} | – | – | 2 | + | + | 101. |{v0,v1} | v1| 2 | 2 | 5 | + | 92. |{v0,v1,v2} | v2 | 5 | 2 | 5 | 9 | 93. |{v0,v1,v2,v3} | v3 | 9 | 2 | 5 | 9 | 94. |{v0,v1,v2,v3,v4}| v4 | 9 | 2 | 5 | 9 | 9begin1. S{v}; 2. D[v]0;3. for vV,kaiS={v}do D[v]l(v,v)4. while SV dobegin5. 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 do8. D[v]MIN(D[v];D[w]+l(w,v));end;end; 5 op. atliekamas n kartų (n-viršūnių ksaičius), 7,8 operatoriai atliekami n kartų (max). 4 op. wile ciklas įstato kiekivieną viršūnę į S. Todėl ciklas iš 4,5,6,7,8 operatorių atleikamas n2 kartų, todėl algoritmo sudėtingumas (n2) ( 3 operatorius atleikamas n kartų, todėl algoritmo sudėtingumui įtakos neturi ).

-30-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ą aibes S elem.Šiuos veiksmus reik atlikti tam tikra seka duomenų bazėje.Mus domina laikas atliekant veiksmų seką priklausomai DB dydžio ir nuo veiksmų sekos ilgio. Šis laikinas sudėtingumas paprastai tikrinamas blogiausiu atveju ir vidutinišku.PVZ.Kraskalo alogoritmas.Surasti ekonominį medį neorentuotam grafe. Yra grafas G (V, E).V-virš. aibė,E-briaunų aib. Kieikviena briauna iš E turi svorį c. Reikia surasti grafą-medį G(V,T). T-E poaibis iš. Taip kad  i T ci =>min.Medis grafas be ciklo. Jei medyje S(V,T) pridesime kokią nors briauną, tai susidarys vienas ciklas. Grafo G mišku vadiname neorentuotu medžiu aibe: {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.

-38-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 kartu šią operaciją, sudetingumas yra (n2). Šią duomenu strukturą galima pagerinti naudojant susijusius sąrašus ir apjungiant aibes – mažesnę prijungiant prie didesnes. Č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 i didesni, jis atsiduria galutiniame sąraše, mažiausiai 2 kartus didesniame negu buvo. Todel jokio elemento negalime perkelti daugiau kaip log n kartu, todel laikinai sudetingumas vienam elementui (log n), o visiems n elementams (nlog n). Jei atliekama m operacijų RASTI n iki n-1 karto apjungti, tai laikinai sudėtingumas yra (MASK m,n(log n)), jei m >=nlog n, tai šis algoritmas iš tikrųjų yra optimalus, o kai m<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 buti 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.

-28-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) . 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-24.k-tojo didesnio elem, radimasP(k-1, 1,n-k) = ( n)

-36-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į.

-44-Stipriai susijusių dalių isškyrimas orentuotame grafeStipriai 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ą i gyli galima apskaičiuoti APATRYŠYS[V], o taip pat išskirti stipriai susijusias dalis, tam grafo viršūnės talpinamos į steką, kai apeinant grafą sutinkamos. Kiekvieną kartą, kai aptinkama stip. susijusios dalies šaknis, visos viršūnės iki šios šaknies išstumiamos iš steko ir jos yra stipriai susijusios dalies viršūnės. Modifikuotos proc. paaiškinimas: APATRYŠYS[v] skaičiuojamas 4,9 ir 11 eilutėje 4 operacijoje suteikiama pradinė reikšmė (viršūnės Nr.). 9op. Priskiriam APATRYŠYS[v]MIN(APATRYŠYS[v], APATRYŠYS[w] )-tai lankams įeinantiems į medį. 10 op. išaiškina ar nįeinantis į medį lankas (v,w) yra atbulinis ar skersinis, o tai pat išaiškinama ar w stekui ;priklauso stipriai susijusiai grafo daliai. 11 op. koreguojama reikšmė APATRYŠYS[v] MIN(VIRNR[w], APATRYŠYS[v] ). Šio algoritmo sudėtin-gumas yra (MAX(n,e)) – tiesinės, n-viršūnių sk. e-lankų sk.

-26-Ieškant kito max elemento, reikia a6 ly-ginti su pralaimėjusiais, randant a1Jei a6 > a3, tai reikia palyginti ir ar a6 > a2 Jei a6 < a3, tai reikia palyginti ir ar a3 > a6Radom 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-nimu sk. yra optimalus: n + log n – 2 .

Geriausio (max) ir blogiausio (min) elemento išrinkimasGalima 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

-34-parinkus h(a) dažnai paskirstymo metodas duoda geresnius rezultatus. Tegul mums reikia atlikti aibeje 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žiaiTegul mums reikia daug kartų atlikti tik 1 operacija PRIKLAUSYTI(a,S).aS ir aS. Tegul yra a1 , a2 … anS.Užduotos tikimybes su kuriomis reikes ieškoti atitinkamo elemento p1, p2 ,… pn. q0-tikimybė ,kad ieškomas elementas aan. Vadinasi yra užduotos tikimybes 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

-42-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 i viršunę w, nes vL(w). Nustatyti ar briauna (v,w) pateko į steką galima šitaip: jei vw (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į.

PAIEŠKA PAPRASTAME SĄRAŠE 1.1. Nuosekli paieška 1 1.2. Paieška interpoliavimas 11.3. Binarinė paieška 1 1) Posąrašio ribu nustatymo metodas. 22) Posąrašio dydžio nustatymo metodas 33) Ribos numeris visada 2 laipsnyje 31) Principas – ‘Skaldyk ir valdyk’ 5Rekurentinių lygčių sprendimas 6 T Apie rekurentinės lygties tipo 6Balansavimas (skaidymas į vienodas dalis). 7Dinaminis programavimas. 8RŪŠIAVIMO ALGORITMAIK-mačių kortežų rūšiavimas 9Nevienodo ilgio kortežu rušiavimas 10Rūšiavimas lyginant elementus “Burb” 11Iterpimo metodas. 12Eksper. statistinis algoritm tyrimas 13 Dviejų programų eksperm.- statist. tyrimas 15Binarinis įterpimo algoritmas 19 Rūšiavimas išrinkimu 19Rūšiavimas piramide 20Rūšiavimas suliejimu (sujungimu) 21Rūšiavimas suskaldymu (quick sort). 22Optimalus rūšiavimas. 23 IŠRINKIMASMax element išrinkim iš n elementų sekos 24Sekanč did. element rad. (2-ų max radimas). 25Ger. (max) ir blog. (min) element išrink 26 k-ojo didesn elem. Išrink[be rušiavimo] 27Išrinkimas be randomizacijos. 27 Veiksmai su aibemis(DS požiuriu) 29 Kraskalo alogoritmas. 30Paskirstymo metodas (heširavimo) 32Optimalūs binarinės paieškos medžiai 34 Operacijų apjungt ir rast atlikimo algoritm 37 Aibes galima vaizduoti medžiais: 38ALGORITMAI GRAFUOSEPaieška į gylį 40Grafo labiausiai susijusių dalių išskyrimo algoritmas 41Paieška į gylį orentuotame grafe 42Stipriai susijusių dalių isškyrimas orentuotame grafe 44 Grafų susietumo matrica. 45 Trumpiausio kelio radimas 47Uždavinys su vienu šaltiniu ( Deiks-tros algoritmas) 48