www.spargalkes.lt

PAIEŠKA PAPRASTAME SĄRAŠE

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ėtų įrašų sk. 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 vid. peržiūrėtų įrašų sk. 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 vid. peržiūrėtų įrašų sk. 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 vid. peržiūrėtų įrašų sk. L_kap= k * L / 2.

Failai:

Failas	Failo dydis	Parsisiųsta
Algoritmų analizė ir sudarymas špera	64 Kb	0