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

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 га оширади.