Мундарижа Кириш

Энг ёмон ҳолат таҳлили
Юқорида кўрдикки, рўйхатнинг қолган қисмларида барча ўтишда иккининг даражалари бирга камаяди. Яна циклнинг охирги итерацияси қолган қисм ўлчами 1 га тенг бўлганда бажарилади. Бу эса j = 1 (яъни 2¹-1=1) да бажарилади. Бу шуни кўрсатадики, N=2^k-1 да ўтишлар сони k дан ошмайди. Охирги тенгликдан энг ёмон ҳолда ўтишлар сони га тенглигини топамиз.
Таҳлилда қидириш жараёни учун ечим дарахти ҳам ёрдам бериши мумкин. Ечим дарахти тугунларида мос ўтишда текшириладиган элементлар туради. Етти элементдан иборат рўйхат учун ечим дарахти 2.1-расмда келтирилган. Умумий ҳолда дарахт нибатан баланслаштирилган, яъни биз ҳар доим рўйхат турли қисмларининг ўртасини танлаймиз. Шунинг туфайли солиштиришлар сонини санаш учун 1.3.2 бўлимда бинар дарахтлар учун келтирилган формулалардан фойдаланамиз.
Мадомики биз N=2^k-1 деб фараз қиларканмиз мос келувчи ечим дарахти доим тўлиқ бўлади. Унда k даража, яъни бўлади. Биз ҳар қайси даражада биттадан солиштириш бажаряпмиз, шунинг учун солиштиришлар умумий сони дан ошмайди.

2.1-расм. Етти элементли рўйхатда қидириш учун ечим дарахти


Ўртача ҳол таҳлили
Худди кетма-кет қидириш алгоритмидаги каби таҳлилда икки ҳолатни қараймиз. Биринчиси мақсад қиймат рўйхатда аниқ мавжуд ҳол ва иккинчиси у умуман йўқ ҳолат.
Биринчи ҳолда мақсад қиймат учун мумкин бўлган ҳолатлар N та ва улар тенг эҳтимолли ҳамда уларнинг ҳар бири 1/N га тенг. Агар қидириш жараёнини тавсифловси бинар дарахтни қарайдиган бўлсак, у ҳолда 1 даражада дарахт илдиз элементидан қидириш учун битта солиштириш, иккинчи даражадаги тугунлар элементларидан қидириш учун иккита солиштириш ва учинчи даражада учта солиштириш талаб қилинади. Умуман i даражадаги элементлардан қидириш учун i солиштириш талаб қилинади. 1.3.2 бўлимда кўрсатилганидек, i даражада та тугун мавжуд ва да дарахтда k даража мавжуд. Бу шуки, барча мумкин бўлган ҳоллар учун тўлиқ солиштиришлар сонини ҳар қайси даражадаги солишритиришларни тугунлар сонига кўпаймаларини йиғиндиси ҳисоблаб топиш мумкин. Натижада ўртача ҳол таҳлили қуйидагини беради
( _учун)
.
(1.19) тенгликдан фойдаланиб охирги ифодани соддалаштиришимиз мумкин:

дан _{ни ҳосил қилиб}

N нинг ўсиши билан k/N нинг қиймати нолга яқинлашади ва
( учун )



Энди мақсад қиймат рўйхатда мавжуд бўлмаган ҳолни қараймиз. Элементнин мумкин бўлган ҳолатлари сони N га тенг, аммо бу ҳолда яна N + 1 мақсад қиймат рўйхатда йўқлиги учун имкониятлар бор. Имкониятлар сони N + 1 га тенг, яъни мақсад қиймат рўйхатдаги биринчи элементдан кичик, биринчидан катта иккинчидан кичик, иккинчидан катта учинчидан кичик ва ҳ.к. мақсад қиймат N элементдан катта бўлиши мумкин. Ҳар қайси бу элементлар йўқлиги ҳоллар k солиштиришда бажарилади. Ҳаммаси бўлиб ҳисоблашда 2N + 1 имкониятлар иштирок этади. Ниҳоят, ҳосил қиламиз
<sub>учун.
Юқоридаги каби алмаштиришлар қуйидагини беради

учун.</sub>
Охирги тенглик элемент рўйхатда мавжуд бўлган ҳолда натижани фарқсиз оширади. Масалан 20²⁰-1=1 048 575 элементдан иборат рўйхат учун биринчи ҳолда 19 га яқин натижага, иккинчи ҳолда 19.5 га яқин натижага эга бўламиз.