Алгоритмы

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 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-11 dideliems n).

Balansavimas (skaidymas į vienodas dalis). Reikia surūšiuoti n ilgio masyvą didėjimo tvarka. 1.surandam min, kurį sukeičiam su pirmu, po to iš (n-1) elemento surandam min ir sukeičiam su antru ir t.t.. Rekursyvinė lygtis aprašanti palyginimų sk.: T(n)  {0, n1T(n-1)+n-1, n>1 ;

T(n)  n(n-1)/2, o algoritmo sudėtingumas (n2). Čia skaldymas į dvi nelygias dalis: į vieno elemento ir (n-1).2. Gaunamas suskaldžius uždavinį į dvi lygias dalis  n/2. Tarkim, kad n  2k. Viena dalis nuo x1 iki xn/2 , o kita nuo xn/2+1 iki xn. Šias dalis surūšiuojam ir sujungiam palyginant minimalius elementus. Sujungimui reiks maksimum n-1 palyginimų. Tokį skaidymą galima rekursyviai tęsti toliau, kol lieka dalyse po 1 elementą. Rekursyvinė lygtis aprašanti tokį algoritmą yra:

T(n)  {0, n1 2T(n/2) + n - 1, n>1.

Šio algoritmo sudėtingumas ( n log n).

Dinaminis programavimas.

Kartais galima efektyvius algoritmus gauti naudojant dinaminį programavimą. Šiuo būdu reikėtų skaičiuoti visus dalinius uždavnius, bet sprendžiami nuo mažų prie didelių. Atsakymai prisimenami lentelėje ir uždaviniai jungiami, kad būtų išspręstas visas uždavinys ir gautas optimumas. Pvz. sudauginant n matricų yra labai svarbus daugybos eiliškumas, kuris nulemia bendrą veiksmų skaičių. Pažymim mi j minimalus veiksmų sk. dauginant matricas: Mi*Mi+1*...*Mj, kur 1  i < j  n. Kai M  M1*M2*...*Mn, tai jų matiškumas yra r0*r1*r2*...*rn.

mi j  {0, ij MIN( mik + mk+1, j + ri-1 rk rj ), j > i, i  k < j (1).

M` Mi*Mi+1*...*Mk, [ri-1*rk]. Min vei-ksmų sk. mi,k.

M``Mk+1 *Mk+2 *... * Mj, [rk*rj].

Atliekant šią daugybą min veiksmų sk. mk+1, j, o sudauginant M` su M``, min veiksmų sk. ri-1 rk rj. Tai atliekam tol kol negaunam m1n.1-a lygtis ya dinaminio programavimo rekurentinė lygtis. mi,j reikšmės skaičiuojamos tvarka, kai didėja indeksų sk. Iš pradžių skaičiuojam mi,i 0 (visiem i), toliau mi, i+1, po to mi, i+2, kol neprieinam m1n.

RŪŠIAVIMO ALGORITMAI

K-mačių kortežų rūšiavimas

Tegul mes turime seką A1 A2 ... An k-mačių kortežų, t.y., A erdvinis Ai elementas, sudarytas iš ai1 ai2 ... aik.Reikia šią seką rūšiuoti taip: B1 B2 ... Bn, kad visiem i Bi  Bi+1. Rūšiavimas atliekamas k kartų pereinant per duotą seką. Pirmą kartą atliekamas rūšiavimas pagal k-ąją komponentę. Antrą kartą pagal (k-1) komponentę ir t.t. Prėjus pagal i-ąją, turėsim sūrušiuotą seką. Kiekviena skiltis ai j yra nuo 0 iki m-1. Reikia organizuoti m pagalbinių eilių Q(j), kur j  0,...,m-1, kurios iš pradžių turi būti tuščios. Duomenis A1 A2 ... An iš pradžių surašom į sąrašą EILĖ. Paimam eilinį kortežą Ai iš EILĖS ir patalpinam į pagalbinę eilę Q(j) pagal analizuojamos komponentės reikšmę. Taip darom tol, kol bendra EILĖ ištuštėja. Visi kortežai atsiduria pagalbinėse eilėse. Po to jie suduriami: Q(0) Q(1)...Q(m-1) ir jie sudaro vieną bendrą eilę EILĖ. Kai praeinam pro visas komponentes, tai EILĖ bus surūšiuota. Algoritmo sudėtingumas yra tiesinis [(n+m)/k]. Naudoti šį metodą neverta, kai n yra mažas.

Nevienodo ilgio kortežų rūšiavimas

Kad suvienodinti kortežų ilgius galima priekyje prirašyti nulius, tačiau tai ne efektyvu, nes bus bereikalingų daug peržiūrėjimų. Tuomet tegul lmax- kortežų maksimalus ilgis, tai reikia iš pradžių surūšiuoti maksimalaus ilgio kortežus pagal l max paskutinę komponentę. Reikės lmax kartų rūšiuoti visus kortežus.Antrą kartą reikia rūšiuoti kortežus, kurių ilgis lmax -1 ir jau surūšiuotus pagal paskutinę komponentę, kurių ilgis lmax. Ir paskutinį kartą lmax perėjus per visą sąrašą, bendram sąraše bus surūšiuota seka. Pastabos: 1. Prieš naudojant šį algoritmą, visi kortežai turi būti išskirstyti pagal ilgius. Tam formuojami sąrašai ILGIS(l), kur l  1,...,lmax, kuriuose surašyti atitinkamo ilgio kortežai. Pirmame žingsnyje rūšiuojamas tik sąrašas ILGIS(lmax) pagal paskutinę komponentę. 2. Be to matom, kad praėjus kartą pro vieną komponentę gali būti daug pagalbinių eilių Q(i) (kur i  0,1,...,m-1) tuščios. Nežiūrint to jas visas reikia jungti į bendrą sąrašą, todėl naudinga būtų iš pradžių nustatyti kurios pagalbinės eilės bus netuščios ir tik jas jungti į vieną bendrą sąrašą.

Rūšiavimas lyginant elementus

“Burbuliuko” metodas. Paprastai elementai rūšiuojami pagal raktinį žodį.

Tarkim turim K1..K16 elementų ir lyginame K1 >K2. Jeigu daugiau sukeičiam vietom. Jeigu ne nieko nedarom ir t.t. Paskutinis palyginimas bus Km > Kn. Po 1 iteracijos didžiausias skaičius atsiranda pabaigoje. Sekanti iteracija vyksta su n-1 elementu, nes paskutinio neimame ir t.t.

Pirmoje iteracijoje bus (n-1) palyginimų. Antroje iteracijoje (n-2), i-tojoje iteracijoje (n-i).

Tuomet bendras palyginimų skaičius bus

Kadangi ne visuomet elementai sukeičiami,