Algoritmai



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/. 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/. Jei ieškomo įrašo nėra, tai paieška nutraukiama kai eilinis raktas bus didesnis už užduotą. Atliekant k įrašų paiešką 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)naudojama surūšiuotame masyve. Jis dalinamas pusiau ir ieškomas raktas lyginamas su vidurio raktu. Idealus masyvo dydis 2n-. Jei 31 įrašas reikės žingsnių, kad surasti įrašą 31=25-. Bendru atveju 2n-1-1< n £ 2n-. Kai įrašų sk. Bet koks, tai naudojami tokie alg.
- Microsoft Word 59 KB
- 2012 m.
- 3 puslapiai (7881 žodžiai)
- Atėnė
-