6,-7-Mavzu: Ketma-ket qidiruv. Indeksli ketma-ket qidiruv. Ketma-ket qidiruvning samaradorligi Reja

Qidiruvni mukamallashtirish usullari
Umuman olganda, jadval har bir elementni qidirish ehtimolligin qandaydir bir qiymat bilan izohlash mumkin. Faraz qilaylik, jadvalda qidirilayotgan element mavjud emas. U holda qidiruv amalga oshirilayotgan barcha jadvalni diskret holatga ega tizim sifatida qarash mumkin hamda qidirilayotgan elementni topish ehtimolligi – bu tizim i-chi holati ehtimolligi p(i) deb olish mumkin.

Jadvalni diskret tizim sifatida qaraganimizda, undagi taqqoslashlar soni diskret tasodifiy miqdorlar qiymatlarini matematik kutilmasini ifodalaydi.

Z=Q=1p(1)+2p(2)+3p(3)+…+np(n)

Iloji boricha p(1) p(2) p(3) … p(n) bo’lsa, maqsadga muvofiq bo’ladi.

Bu shart taqqoslashlar sonini kamaytirib, samaradorlikni oshiradi. Sababi, ketma-ket qidiruv birinchi elementdan boshlanganligi uchun eng ko’p murojaat qilinadigan elementni birinchiga qo’yish lozim.