Saralash algoritmlarini qiyosiy tahlili
Download 11.75 Kb.
|
Saralash algoritmlarini qiyosiy tahlili-fayllar.org (1)
- Bu sahifa navigatsiya:
- Oʻrtacha
|
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 •
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. |
