Ахборот тизимлари ва технологиялари Кириш

2-Чизма.


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² + 1/2 = 0
Бу ердан
p²=n ;

(*)ифодада р ўрнига р_оптни қўйиб қуйидаги таққослашлар сонини оламиз:

Q = +1
Демак, индексли кетма-кет қидирувни самарадорлигитартиби O ( ) бўлади.
5. Қидирувни мукаммаллаштириш усуллари
Умуман олганда, жадвалда хар бир элементни қидириш эхтимоллигини қандайдир бир қиймат билан изоҳлаш мумкин. Фараз қилайлик жадвалда қидирилаётган элемент мавжуд. У ҳолда қидирув амалга оширилаётган барча жадвални дискрет холатга эга тизим сифатида қараш мумкин хамда унда қидирилаётган элементни топиш эхтимоллиги – бу тизим i-чи холати эхтимоллиги p(i) деб олиш мумкин.

Жадвални дискрет тизим сифатида қараганимизда, ундаги таққослашлар сони дискрет тасодифий миқдорлар қийматларини математик кутилмасини ифодалайди.
Z=Q=1p(1)+2p(2)+3p(3)+…+np(n)
Иложи борича p(1)p(2) p(3) …p(n) бўлса, мақсадга мувофиқ бўлади.
Бу шарт таққослашлар сонини камайтириб, самарадорликни оширади. Сабаби, кетма-кет қидирув биринчи элементдан бошланганлиги учун энг кўп мурожаат қилинадиган элементни биринчига қўйиш лозим.
Қидирув жадвалини қайта тартиблашни энг кўп ишлатиладиган иккита усули мавжуд. Уларни бир боғламли рўйхатлар мисолида кўриб чиқамиз.