Išsami teorija apie algoritmus

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. 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=ë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-1F1, tai ieškomas įrašas yra antroje dalyje, kuri mažesnę už pirmąją. 2r-1-12. 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

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!