www.spargalkes.lt

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 L_ap =L/2. Jei įrašo nėra teks peržiūrėti visus įrašus L. Tarkim ieškomo įrašo su tikimybe p₀ nėra sąraše, tada vidutinis peržiūrėtų įrašų skaičius L_ap=L*p₀+Σ_i=1^L (i*p_i ); p_i=1-p₀/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: L_sp=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 L_kap = k * L / 2.

Failai:

Failas	Failo dydis	Parsisiųsta
Algoritmai špera 2	50 Kb	0