Proceedings of International Conference on Educational Discoveries and Humanities
Hosted online from Plano, Texas, USA.
Date: 1
st
November, 2022
ISSN: XXXX-XXXX
Website: econferenceseries.com
215 |
P a g e
Agar qidirilayotgan element ro‘yxatda bo‘lsa,
u holda N marta mumkin bo‘lgan
holatlardan biriga teng bo‘ladi: birinchi, ikkinchi, uchinchi va h.k. Bu holatlarning
barchasini teng ehtimolli deb faraz qilamiz, ya‘ni qidirilayotgan
element mavjud
holatlarning birida uchrashi ehtimoli
1/N ga teng bo‘ladi.
Ushbu xulosalardan kelib chiqqan holda quyidagi savollar tug‘iladi:
1. Agar qidirilayotgan element ro‘yxatda birinchi turgan bo‘lsa,
necha marta
taqqoslash bajariladi?
2. Ikkinchi bo‘lsa-chi?
3. Uchinchisi bo‘lsa-chi?
4.
N-element bo‘lsa-chi?
Agar yuqorida aytilgan fikrlardan kelib chiqadigan bo‘lsak, ushbu savollarga javob
tayyor, chunki har bir holat uchun mos ravishda 1, 2, 3 va
N marta taqqoslash
bajariladi. Bu esa
N ta holatdan har biri qidirilayotgan elementning ro‘yxatda
joylashish tartibiga mos kelishini bildiradi.
Natijada, o‘rtacha holatlar uchun
quyidagi tenglikga erishamiz:
A(N) = 1 f, = 1.
N(N
+
1)
= N+1 ,
(i)
N : N 2
2
' ’
Agar qidirilayotgan element ro‘yxatda mavjud bo‘lmasa
taqqoslashlar soni N+1
gacha oshib ketadi. Element ro‘yxatda mavjud bo‘lmasa, u holda qidiruv uchun
N
ta taqqoslash zarurligini yuqorida ko‘rib chiqdik. Agar barcha
N+1 taqqoslashlar
teng ehtimolli deb faraz qilsak, u holda quyidagi formula kelib chiqadi:
Agarda ro‘yhat
elementlari soni N juda katta son bo‘lsa u holda 1/(
N+1) ning
qiymati 0 ga yaqin son bo‘ladi.
