| 2. Ketma-ket qidirish algoritmi
Qidirish algoritmlarida qandaydir maqsad elementini roʻyxatdan qidirish jarayoni qiziqtiradi. Ketma-ket qidirishda biz doim roʻyxat saralanmagan deb faraz qilamiz, ammo ayrim qidirish algoritmlari saralangan roʻyxatlarda yaxshi unumdorlik koʻrsatadi.
Ketma-ket qidirish algoritmi roʻyxat elementlarni birinchisidan boshlab to maqsad elementi topilgunga qadar birma bir koʻrib chiqadi. Ravshanki, aniq kalit qiymati qanchalik uzoqda joylashgan boʻlsa, shunchalik uni qidirishga koʻp vaqt sarflanadi. Buni ketma-ket qidirish algoritmi tahlilida hisobga olish kerak.
Ketma-ket qidirish algoritmining umumiy koʻrinishi quyidagicha:
SequentialSearch(list,target,N)
list ko’riladigan ro’yxat
target maqsad qiymati
N ro’yxat elementlari soni
for i=1 to N do
if (target=list[i])
return i
end if
end for
return 0
Eng yomon holat tahlili
Ketma-ket qidirish algoritmida ikkita eng yomon hol uchraydi. Birinchi holda maqsad elementi roʻyxatning eng oxirida joylashgan boʻladi. Ikkinchisida u roʻyxatda umuman boʻlmaydi. Bu ikki holda ham N solishtirishlar bajariladi (N – roʻyxat elementlari soni). Tushunarliki, istalgan qidirish algoritmi uchun N qiyinlikning yuqori chegarasini beradi. Agar solishtirishlar N dan katta boʻlsa,u holda solishtirish qaysidir elementda ikki marta bajarilgan, demak, ortiqcha harakatlar qilingan va algoritmni yaxshilash kerak.
Qiyinlik yuqori chegarasi va qiyinlikning eng yomon holi tushunchalari orasida farq bor. Yuqori chegara masaladan bogʻliq boʻlsa, eng yomon hol esa uni yechuvchi ma’lum algoritmdan bogʻliqdir. Eng yomon holi koʻrsatilgan yuqori chegara N dan kichik boʻlgan qidirish algoritmi bilan tanishamiz.
Oʻrtacha hol tahlili
Qidirish algoritmlari uchun ikki oʻrtacha hol mavjud. Birinchisida qidirish muvaffaqiyatli yakunlanadi, ikkinchisi maqsad qiymati roʻyxatda umuman boʻlmagan hol.
Agar maqsad qiymati roʻyxatda mavjud boʻlsa, u holda u mumkin boʻlgan N imkoniyatlarning birini egallaydi: u birinchi, ikkinchi, uchinchi va h.k. boʻlishi mumkin. Biz bu barcha holatlarni teng ehtimolli deb faraz qilamiz va ularning har biri 1/N ga teng. Natijada oʻrtacha holdagi qiyinlik uchun quyidagi tenglikka ega boʻlamiz
Agar maqsad qiymati roʻyxatda uchramasa, u holda imkoniyatlar soni N + 1 gacha oʻsadi. Ma’lumki, bu holda qidirish N solishtirish talab qiladi. Agar barcha N +1 imkoniyatlar teng ehtimolli deb faraz qilsak, u holda quyidagiga ega boʻlamiz:
(N juda katta boʻlsa 1/(N + 1) qiymat 0 ga yaqinlashadi.)
Koʻrinib turibdiki, elementning yoʻqligi oʻrtacha holni qiyinligini 1/2 ga oshiradi.
|
