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

Маълумотлар синфлари
Алгоритмларни таҳлили чоғида кирувчи маълумотлар танлови унинг ишига жиддий таъсир кўрсатиши мумкин. Айрим саралаш алгоритмлари агар кирувчи рўйхат сал кам сараланган бўлса жуда тез ишлайди, у ҳолда ушбу рўйхатда бошқа алгоритмлар жуда оддий натижа кўрсатади. Тасодифий рўйхатда эса тескари нтижага олиб келади. Шу сабабли биз битта кирувчи маълумотларда алгоритмларнинг таҳлили билан чекланмаймиз. Амалиётда биз алгоритмнинг бажарилишига энг тезликни ва энг секинликни таъминловчи маълумотларни излаймиз. Бундан ташқари биз алгоритмнинг барча мумкин бўлган маълумотлар тўпламидаги ўртача самарадорлигини баҳолаймиз.
Энг яхши ҳол
Алгоритм учун энг яхши ҳолат шундай кирувчи маълумотлар тўпламики, бунда алгоритм энг кам вақтда бажарилади. Бундай маълумотлар тўплами ўзида шундай қийматлар комбинациясини намоён қиладики бунда алгоритм энг кам ҳаракатлар бажаради. Агар биз қидириш алгоритмини қарасак, у ҳолда кирувчи маълумотлар энг яхши ҳисобланади – агар қидирилаётган қиймат (одатда мақсад қиймат ёки калит дейилади) текширилаётган тўпламнинг бринчи ўринида ёзилган бўлса. Бундай алгоритм учун унинг қанчалик мураккаблигидан қатъий назар битта солиштириш талаб қилинади. Сезиш мумкинки, рўйхатда қидиришда у қандай узунликда бўлишидан қатъий назар энг яхши ҳол доимий вақтни талаб қилади. Умуман энг яхши ҳолатда алгоритмнинг бажарилиш вақти кичик ёки оддий доимий бўлади, шунинг учун бундай таҳлилни кам олиб борамиз.
Энг ёмон ҳол
Энг ёмон ҳолатни таҳлил қилиш энг муҳим ҳисобланиб, у алгоритмнинг максимал бажарилиш вақтини намоён қилади. Энг ёмон ҳолни таҳлил қилиш чоғида алгоритм энг узоқ вақт талаб қиладиган кирувчи маълумотларни қидириш керак. Қидириш алгоритми учун мос кирувчи маълумотлар бу шундай рўйхатки унда қидирилаётган калит энг охиририда жайлашган ёки умуман мавжуд бўлмаган ҳолатдир. Натижада N солиштиришлар талаб қлиниши мумкин. Энг ёмон ҳолни таҳлил қилиш танланган алгоритмдан боғлиқ равишда бизнинг дастуримиз қисмининг ишлаш вақти учун юқори баҳолашларини беради.
Ўртача ҳол
Ўртача ҳолни таҳлил қилиш энг мураккаб ҳисобланиб, у турли тафсилотларни ҳисобга олишни талаб қилади. Ушбу таҳлил асосида мумкин бўлган кирувчи маълумотлар тўламини ажратувчи гуруҳларни аниқлаш ётади. Иккинчи қадамда кирувчи маълумотлар тўпламининг ҳар бир гуруҳга тегишлилик эҳтимоли аниқланади. Учинчи қадамда алгоритмнинг ҳар қайси маълумотлардаги бажарлиш вақти ҳисобланади. Алгоритмнинг бир гуруҳдаги барча маълумотлардаги бажарлиш вақти бир хил бўлиши керак, акс ҳолда гуруҳни қайта бўлиш керак. Алгоритм бажарилиш вақтининг ўртача вақти қуйидаги формула бўйича ҳисобланади:
(1.1)
бунда n билан кирувчи маълумотлар ўлчови, т билан гуруҳлар сони, p_i билан кирувчи маълумотларнинг i рақамли гуруҳга тегишлилик эҳтимоли, t_i билан эса i рақамли гуруҳ маълумотларини алгоритм томонидан қайта ишлашга кетадиган вақт белгиланган.
Айрим ҳолларда биз кирувчи маълумотларнинг ҳар қайси гуруҳларга тушиш эҳтимоли бир хил деб тахмин қиламиз. Бошқача қилиб айтганда, агар гуруҳлар 5 та бўлса, у ҳолда биринчи гуруҳга тушиш эҳтимоли иккинчи гуруҳга тушиш эҳтимолидек ва ҳ.к., яъни ҳар бир гуруҳга тушиш эҳтимоли 0.2 га тенг. Бу ҳолда ўртача бажарилиш вақти юқоридаги формула орқали топилади ёки унга эквивалент тенг эҳтимолли барча гуруҳларга оид қисқа формуладан фойдаланиш мумкин
(1.2)