Адабиётлар

 
3. Кетма-кет қидирувни самарадорлиги 
Ихтиѐрий қидирувнинг самарадорлиги жадвалдаги маълумотларнинг 
калитлари билан солиштириш сони – С билан бахоланиши мумкин. Агар 
таққослашлар (солиштириш) сони қанча кичик бўлса, қидирув алгоритми 
самарадорлиги шунча яхши бўлади. 
Массивда кетма-кет қидирувнинг самарадорлиги қуйидагича бўлади: 
C = 1 n, C = (n + 1)/2. 
Умуман олганда рўйхатда хам самарадорлик юқоридаги каби бўлади. 
Гарчи массивда хам боғланган рўйхатда хам қидирув самарадорлиги бир хил 
бўлсада, маълумотларни массив ва рўйхат кўринишда тасвирлашнинг ўзига 
хос камчилик ва афзалликлари мавжуд. Қидирувнинг мақсади - қуйидаги 
жараѐнларни бажарилишидан иборат: 
1)
Топилган ѐзувни ўқиш. 
2)
Қидирилаѐтган ѐзув топилмаса, уни жадвалга қўйиш. 
3)
Топилган ѐзувни ўчириш. 
Биринчи жараѐн (қидирувнинг ўзи) массив учун ҳам рўйхат учун ҳам 
бир хил бўлади. Иккинчи ва учинчи жараѐнда эса қидирув рўйхатли 
тузилмада самаралиқроқ бўлади (сабаби массивда элементларн силжитиш 
лозим).
Агар k массивда элементларни силжитишлар сони бўлса, у холда k = 
(n + 1)/2 бўлади. 
 
4. Индексли кетма-кет қидирувни самарадорлиги
Агар бўлиши мумкин барча холатлар тенг эхтимолли деб олинса, у 
ҳолда қидирув самарадорлигини қуйидагича хисоблаш мумкин: 
Белгилашлар киритиб оламиз: m – индекс ўлчови; m = n / p; p – қадам 
ўлчови 
Q = (m+1)/2 + (p+1)/2 = (n/p+1)/2 + (p+1)/2 = n/2p+p/2+1
(*) 
Q ни p бўйича дифференциаллаб уни нолга тенглаштирамиз:
dQ/dp=(d/dp) (n/2p+p/2+1)= - n / 2 p
2
+ 1/2 = 0 
Бу ердан 
p
2
=n ;
n
p
опт

---

―Маълумотлар тузилмаси ва алгоритмлар‖ фанидан маърузалар матни.
муаллиф: Б.Б.Акбаралиев 
(*) ифодада р ўрнига р
опт
ни қўйиб қуйидаги таққослашлар сонини 
оламиз: 
Q =
n
+1 
Демак, индексли кетма-кет қидирувни самарадорлиги тартиби O 
(
n
) бўлади. 
5. Қидирувни мукаммаллаштириш усуллари 
Умуман олганда, жадвалда хар бир элементни қидириш эхтимоллигини 
қандайдир бир қиймат билан изоҳлаш мумкин. Фараз қилайлик жадвалда 
қидирилаѐтган элемент мавжуд. У ҳолда қидирув амалга оширилаѐтган барча 
жадвални дискрет холатга эга тизим сифатида қараш мумкин хамда унда 
қидирилаѐтган элементни топиш эхтимоллиги – бу тизим i-чи холати 
эхтимоллиги p(i) деб олиш мумкин.
n
1
i
1
i
p )
(
Жадвални 
дискрет 
тизим 
сифатида 
қараганимизда, 
ундаги 
таққослашлар сони дискрет тасодифий миқдорлар қийматларини математик 
кутилмасини ифодалайди. 
Z=Q=1p(1)+2p(2)+3p(3)+…+np(n)
Иложи борича p(1) p(2) p(3) … p(n) бўлса, мақсадга мувофиқ 
бўлади. 
Бу шарт таққослашлар сонини камайтириб, самарадорликни оширади. 
Сабаби, кетма-кет қидирув биринчи элементдан бошланганлиги учун энг кўп 
мурожаат қилинадиган элементни биринчига қўйиш лозим. 
Қидирув жадвалини қайта тартиблашни энг кўп ишлатиладиган иккита 
усули мавжуд. Уларни бир боғламли рўйхатлар мисолида кўриб чиқамиз.