11-Мавзу: Қидирув алгоритмларининг самарадорлиги Қидирув алгоритмларининг самарадорлик мезонлари

• Режа:
• Қидирув алгоритмларининг самарадорлик мезонлари;
• Қидирув алгоритмларининг самарадорликлари ва уларни мукаммаллаштириш.

• 11-Мавзу: Қидирув алгоритмларининг самарадорлиги

Қидирув алгоритмларининг самарадорлик мезонлари

• Самарадорлик мезонлари

• калитларни таққослашлар сони;
• дастурнинг ишлаб чиқишга кетган вақт;
• дастурни ишлаши учун кетган вақт;
• талаб қилинадиган хотира хажми.

• Изоҳ

• Қидирув алгоритмлари ишлаб чиқилаётганида, кўпроқ, жадвалдаги калитларни таққослашлар сонига эътибор қаратилади.

Эслатма: Массив ва боғланган рўйхатда керакли элементни бор ёки йўқлигини аниқлаш самарадорлиги бир хил, аммо топилган элементни ўчириш ёки бундай элемент жадвалда бўлмаса, уни жадвалга қўйиш талаб қилинган бўлса, у ҳолда қидирувни амалга ошириш рўйхатда самаралироқ бўлади.

• Чизиқли қидирув самарадорлиги

• M=1÷n, Мўртача = (n + 1)/2=O(n).

• Самарадорлик:

• Эслатма: Массив ва боғланган рўйхатда керакли элементни бор ёки йўқлигини аниқлаш самарадорлиги бир хил, аммо топилган элементни ўчириш ёки бундай элемент жадвалда бўлмаса, уни жадвалга қўйиш талаб қилинган бўлса, у ҳолда қидирувни амалга ошириш рўйхатда самаралироқ бўлади.

• Чизиқли қидирувни мукаммаллаштириш усуллари

• Фараз қилайлик жадвалда қидирилаётган элемент мавжуд. У ҳолда қидирув амалга оширилаётган барча жадвални дискрет холатга эга тизим сифатида қараш мумкин хамда унда қидирилаётган элементни топиш эхтимоллиги – бу тизим i-чи холати эхтимоллиги p(i) деб олиш мумкин.

• Жадвални дискрет тизим сифатида қараганимизда, ундаги таққослашлар сони дискрет тасодифий миқдорлар қийматларини математик кутилмасини ифодалайди:
• Z=С=1p(1)+2p(2)+3p(3)+…+np(n).

• Эслатма. Юқоридаги шарт таққослашлар сонини камайтириб, самарадорликни оширади.

• бўлса, мақсадга мувофиқ бўлади.

• Мукамаллаштириш усуллари

• Топилган элементни жадвал бошига қўйиш орқали жадвални қайта тартиблаш;
• Транспозиция усули.

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

• Транспозиция усулида топилган элемент жадвалда битта олдинги элемент билан ўрин алмаштирилади. Агарда мазкур элементга кўп мурожаат қилинса, биттадан олдинга сурилиб бориб натижада жадвал бошида бўлади.
• Ушбу усул нафақат рўйхатда, балки массивда хам қулай (сабаби фақатгина иккита ёнма-ён турган элемент ўрин алмаштирилади).

• Индексли кетма-кет қидирув самарадорлиги

• С = (m+1)/2 + (p+1)/2

• бу ерда: m – индекс ўлчови; m = n / p; p – қадам ўлчови.

• Самарадорлик:

• Изоҳ

• Агар бўлиши мумкин барча холатлар тенг эхтимолли бўлса, у ҳолда индексли қидирув самарадорлигини қуйидагича мукаммаллаштириш мумкин.

• p2=n

• dС/dp=(d/dp)(n/2p+p/2+1)=-n/2p2 +1/2=0

• С=(m+1)/2+(p+1)/2=(n/p+1)/2+(p+1)/2=n/2p+p/2+1 (*)

• ни (*) га қўйсак қуйидагини ҳосил қиламиз:

• Бинар қидирув

• a1 ≤ a2 ≤ a3 ≤… aN .

• С = O(log2n).

• Самарадорлик:

11-Мавзу бўйича назорат саволлари

• Қидирув алгоритмларининг самарадорлик мезонлари
• Чизиқли қидирувнинг самарадорлиги
• Чизиқли қидирув самарадорлигини ошириш йўллари
• Индексли кетма-кет қидирувнинг самарадорлиги
• Индексли кетма-кет қидирувнинг мукаммал самарадорлигини аниқлаш
• Бинар қидирувнинг самарадорлиги