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

2.1. Қидириш алгоритмлари ва уларни баҳолаш

Керакли маълумотни рўйхатдан қидириш назарий дастурлаштиришнинг асосий масалаларидан бири ҳисобланади. Қидириш алгоритмларни муҳокама қилишда маълумотлар қандайдир рўйхатни ҳосил қилувчи ёзувлардан тузилган деб фараз қиламиз, қайсики дастурдаги маълумотлар массивини намоён қилади. Ёзувлар ёки рўйхат элементлари массивда кетма-кет жойлашади ва улар орасида бўш жой йўқ. Ёзувларнинг барчаси рўйхатда 1 дан N гача рақамланган. Қоидага кўра ёзувлар майдонлардан тузилган бўлиши мумкин, лекин бизни бу майдонлардан калит деб аталувчи қиймат қизиқтиради. Рўйхатлар калит майдон қийматига кўра сараланган ёки сараланмаган бўлиши мумкин. Сараланмаган рўйхатда ёзувлар тартиби тасодифий, сараланганида эса калитнинг ўсиш тартибида жойлашган бўлади.

Сараланмаган рўйхатда керакли ёзувни қидириш бутун рўйхатни ёзув топилгунга қадар кўриб чиқишга олиб келади. Бу қидириш алгоритмларининг оддий кўриниши. Кўришимиз мумкин бу алгоритм унча самарадор эмас, лекин у ихтиёрий рўйхатда ишлайди.

Сараланган рўйхатда иккилик қидиришдан фойдаланиш мумкин. Иккилик қидириш тартибланганликка кўра бир солиштиришда бирдан ортиқ элементларни ташлаб юборишга асосланган. Натижада қидириш самарадор бўлади.

Одатда қидириш нафақат керакли элементни рўйхатда бор йўқлигини аниқлаш учун, балки топилган калит қийматига боғлиқ маълумотларни олиш учун хизмат қилади. Масалан, калит қиймат ходимнинг рақами ёки тартиб рақами ёхуд бошқа исталган ягона идентификатор бўлиши мумкин. Керакли калит топилгандан сўнг, дастур унга боғланган маълумотларни ўзгартириши мумкин ёки бутун ёзувни чиқариши мумкин. Охир оқибатда қидириш алгоритми олдида муҳим вазифа калитнинг ўрнини топиш масаласи туради. Шунинг учун қидириш алгоритмлари керакли калитни сақловчи ёзув индексини беради. Агар калит қиймат топилмаса, у ҳолда қидириш алгоритми массив юқори чегарасидан чиқувчи индекс қийматини беради. Мақсадимиз учун фараз қиламизки, рўйхат элементлари 1 дан N гача рақамланган. Бу агар мақсад элементи топилмаса 0 ни беришга имкон беради. Оддийлик учун калит қиймат такрорланмайди деб фараз қиламиз.
2.1.1. Кетма-кет қидириш алгоритми

Қидириш алгоритмларида қандайдир мақсад элементини рўйхатдан қидириш жараёни қзиқтиради. Кетма-кет қидиришда биз доим рўйхат сараланмаган деб фараз қиламиз, аммо айрим қидириш алгоритмлари сараланган рўйхатларда яхши унумдорлик кўрсатади.

Кетма-кет қидириш алгоритми рўйхат элементларни биринчисидан бошлаб то мақсад элементи топилгунга қадар бирма бир кўриб чиқади. Равшанки, аниқ калит қиймати қанчалик узоқда жойлашган бўлса, шунчалик уни қидиришга кўп вақт сарфланади. Буни кетма-кет қидириш алгоритми таҳлилида ҳисобга олиш керак.

Кетма-кет қидириш алгоритмининг умумий кўриниши қуйидагича:

SequentialSearch(list,target,N)
list кўриладиган рўйхат

target мақсад қиймати

N рўйхат элементлари сони

for i=1 to N do

if (target=list[i])

return i

end if

end for

return 0
Энг ёмон ҳолат таҳлили

Кетма-кет қидириш алгоритмида иккита энг ёмон ҳол учрайди. Биринчи ҳолда мақсад элементи рўйхатнинг энг охирида жойлашган бўлади. Иккинчисида у рўйхатда умуман бўлмайди. Бу икки ҳолда ҳам N солиштиришлар бажарилади (N – рўйхат элементлари сони). Тушунарлики, исталган қидириш алгоритми учун N қийинликнинг юқори чегарасини беради. Агар солиштиришлар N дан катта бўлса,у ҳолда солиштириш қайсидир элементда икки марта бажарилган, демак, ортиқча ҳаракатлар қилинган ва алгоритмни яхшилаш керак.

Қийинлик юқори чегараси ва қийинликнинг энг ёмон ҳоли тушунчалари орасида фарқ бор. Юқори чегара масаладан боғлиқ бўлса, энг ёмон ҳол эса уни ечувчи маълум алгоритмдан боғлиқдир. § 2.2 бўлимда энг ёмон ҳоли кўрсатилган юқори чегара N дан кичик бўлган қидириш алгоритми билан танишамиз.
Ўртача ҳол таҳлили

Қидириш алгоритмлари учун икки ўртача ҳол мавжуд. Биринчисида қидириш муваффақиятли якунланади, иккинчиси мақсад қиймати рўйхатда умуман бўлмаган ҳол.

Агар мақсад қиймати рўйхатда мавжуд бўлса, у ҳолда у мумкин бўлган N имкониятларнинг бирини эгаллайди: у биринчи, иккинчи, учинчи ва ҳ.к. бўлиши мумкин. Биз бу барча ҳолатларни тенг эҳтимолли деб фараз қиламиз ва уларнинг ҳар бири 1/N га тенг. Натижада ўртача ҳолдаги қийинлик учун қуйидаги тенгликка эга бўламиз

(1.15) тенгликдан



Агар мақсад қиймати рўйхатда учрамаса, у ҳолда имкониятлар сони N + 1 гача ўсади. Маълумки, бу ҳолда қидириш N солиштириш талаб қилади. Агар барча N +1 имкониятлар тенг эҳтимолли деб фараз қилсак, у ҳолда қуйидагига эга бўламиз:



( N жуда катта бўлса 1/(N + 1) қиймат 0 га яқинлашади.)

Кўриниб турибдики, элементнинг йўқлиги ўртача ҳолни қийинлигини 1/2 га оширади.