Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Энг яхши ҳолат
Бўлимнинг номланишидан ҳам кўриниб турибдики, алгоритмлар учун энг яхши ҳолат бу қисқа вақт ичида амалга ошириладиган алгоритмнинг маълумотлар жамланмаси. Бундай жамланма алгоритм энг амал бажарадиган қийматлар комбинациясини ифодалайди. Агар биз излаш алгоритмини текширсак, изланган қиймат биринчи алгоритм текшираётган катакка ёзилган бўлса (одатда мақсадли қиймат ёки калит деб аталади), маълумотлар тўплами энг яхши ҳисобланади. Бундай алгоритмга унинг мураккаблигидан қатьий назар, битта таққослаш керак бўлади. Шуни эслатиш керакки, рўйхатдан излашда, унинг қанчалик узун бўлишидан қатьий назар, энг яхши ҳолат доимий вақтни талаб қилади. Умуман, энг яхши ҳолатда алгоритмни бажариш вақти кичик ёки доимий бўлади, шунинг учун биз бундай таҳлилни кам ўтказамиз.
Энг ёмон ҳолат
Энг ёмон ҳолатни таҳлил қилиш жуда муҳим, чунки у алгоритм ишининг максимал вақтини тасаввур қилишга ёрдам беради. Энг ёмон ҳолатни таҳлил қилганда алгоритм энг кўп иш бажарадиган кириш маълумотларини топиш зарур. Изловчи алгоритм учун бу каби кирувчи маълумотлар – бу шундай рўйхатки, унда изланган калит охирида келади ёки умуман бўлмайди. Натижада N таққослаш керак бўлади. Энг ёмон ҳолатнинг таҳлили танланган алгоритмга қараб дастурнинг ишлаш вақти учун юқори баҳони беради.
Ўртача ҳолат
Ўрта ҳолатнинг таҳлили энг мураккаб ҳисобланади, чунки у кўпгина деталларни ҳисобга олишни талаб қилади. Таҳлил асосини мавжуд бўлган кирувчи маълумотлар тўпламини бўлиб чиқиш лозим бўлган турли гуруҳларни аниқлаш ташкил қилади. Иккинчи қадамда кирувчи маълумотлар тўплами қайси гуруҳга тегишли бўлиш эҳтимоли аниқланади. Учинчи қадамда ҳар бир гуруҳдаги маълумотларга алгоритмнинг иш вақти ҳисобланади. Алгоритмнинг бир гуруҳдаги ҳамма кирувчи маълумотлар учун ишлаш вақти бир хил бўлиши керак, акс ҳолда гуруҳни бўлиш лозим. Ўртача иш вақти
(7.1)

формула орқали ҳисобланади. Бу ерда n - кирувчи маълумотлар ўлчами, m - гуруҳлар сони, p_i - кирувчи маълумотларнинг i сонли гуруҳга тегишлилик эҳтимоли, t_i – i сонли гуруҳдаги маълумотни қайта ишлаш учун алгоритмга керак бўладиган вақт деб белгиланган.

Баъзи ҳолларда биз кирувчи маълумотларнинг ҳар бир гуруҳга тушиш эҳтимолини бир Хилл деб тахмин қиламиз. Бошқача айтганда, агар гуруҳ 5 та бўлса, биринчи гуруҳга тушиш эхтимоли иккинчи ёки бошқа гуруҳга тушиш эхтимолидек, яъни ҳар бир гуруҳга тушиш эхтимоли 0,2 га тенг. Бу ҳолда ишнинг ўртача вақтини аввалги формула Билан ёки унга эквивалент соддалаштирилган барча гуруҳларнинг тенг эхтимоллигида ҳақиқий бўлган
(7.2)

формуладан фойдаланишимиз мумкин.