Saralash algoritmlarini qiyosiy tahlili

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.

---