Algoritmų teorija su pavyzdžiais

1.Nuosekli paieška Įrašai išdėstyti atsitiktine tvarka kaip buvo įrašyti. Reikia sutvarkyti iš eilės pagal raktinius žodius, t.y surasti duotą įrašą pagal raktą. Nuosekliai ieškant reikia peržiūrėti visus įrašus iš eilės. Vid.peržiūrėų įrašų sk. ieškant yra Lap =L/2. Ap – atsitiktinė paieška. 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. Paieška interpoliavimas Jei sąrašai surūšiuoti ir žinomas pirmo įrašo rakatas 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. 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 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log2n. 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-1F1, tai ieškomas įrašas yra antroje dalyje, kuri mažesnę už pirmąją. 2r-1-1

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!