www.spargalkes.lt

Algoritmai špera 2

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. Vidutinis peržiūrėtų įrašų skaičius 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 vidutinis peržiūrėtų įrašų skaičius Lap=L*p0i=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 vidutinis peržiūrėtų įrašų skaičius 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 vidutinis peržiūrėtų įrašų skaičius Lkap = k * L / 2.

Failai:
FailasFailo dydisParsisiųsta
Parsisiųsti šį failą (ecaad6fc02c0ef908f5611b908887179.zip)Algoritmai špera 250 Kb0
Neteisinga

 
Informatika Algoritmai špera 2
www.kvepalai.ltkvepalai.ltwww.spargalkes.ltspargalkes.ltwww.tytuvenai.lttytuvenai.lt