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

1.3.3. Эҳтимоллик

Биз алгоритмларни кирувчи маълумотларга боғлиқ равишда таҳлил қилмоқчимиз, бунинг учун у ёки бу кирувчи маълумотлар тўплами қанчалик тез учрашини баҳолашимиз керак. Айниқса, у ёки бу шартларни қондирадиган кирувчи маълумотлар эҳтимолликлари билан ишлашга тўғри келади. У ёки бу ҳодисанинг эҳтимоллиги ўзида нол ва бир орасидаги сонни билдиради, яъни 0 эҳтимоллик ҳодисанинг умуман рўй бермаслигини, 1 эҳтимоллик эса ҳодисани муқаррар рўй беришини билдиради. Агар бизга турли хил мумкин бўлган кирувчи қийматлар аниқлиги 10 га тенглиги маълум бўлса, у ҳолда биз тўлиқ ишонч билан айтишимиз мумкинки – ҳар бир бундай киришлар эҳтимоллиги 0 ва 1 орасида ва бу барча эҳтимолликлар йиғиндиси 1 га тенг ҳамда улардан бири албатта рўй бериши керак. Агар ҳар бир кириш рўй бериш имконияти бир хил бўлса , у ҳолда уларнинг ҳар қайсиси эҳтимоллиги 0.1 га (10 дан бири ёки 1/10) тенг.

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

1.3.4. Йиғиндини ҳисоблаш формулалари

Алгоритмлар таҳлили чоғида қандайдир ўлчовлар тўламини йиғишимизга тўғри келади. Келинг бизда циклли алгоритм бўлсин. Агар ўзгарувчи 5 қиймат қабул қилса, у ҳолда цикл 5 марта бажарилади, агар қиймат 20 қабул қилса у ҳолда 20 марта. Умуман, агар цикл ўзгарувчиси қиймати М га тенг бўлса, у ҳолда цикл М марта бажарилади. Агар цикл ўзгарувчиси 1 то N гача қийматларни қабул қилса, у ҳолда циклнинг барча бажарилишлари йиғинди сони 1 дан N гача булган натурал сонлар йиғиндисига тенг бўлади. Биз бу йиғиндини шаклда ёзамиз. Белгининг пастки қисмида ўзгарувчининг бошланғич қиймати турибди, устки қисмида эса – унинг сўнгги қиймати. Агар қандайдир қиймат йиғинди шаклида ёзилган бўлса, уни бошқа ўхшаш ифодалар билан солиштириш учун соддалаштириш керак. Икки ва сонлардан каттасини аниқлаш осон эмас. Шу сабабли йиғиндиларни соддалаштириш учун қуйидаги формулалардан фойдаланамиз. Бунда С– i га боғлиқ бўлмаган доимий.