Algoritmlar samaradorligini tahlil qilish

Исбот: a1, b1, a2, b2 ихтиёрий ҳақиқий сонлар бўлиб, қуйидаги тасдиқ ўринли

• Исбот: a1, b1, a2, b2 ихтиёрий ҳақиқий сонлар бўлиб, қуйидаги тасдиқ ўринли

Агар a1 <= b1 ва a2 <= b2 бўлса, a1 + a2<=2max{b1, b2} бўлади.

бўлгани учун баъзи ижобий с константалар мавжуд бўлса ва баъзи бир ноаниқ бутун сон n1 мавжудки

Шунингдек бўлгани учун, тенгсизлик ўринлидир.

каби белгилаб, эканлигини кўриб чиқамиз. Уларни қўшсак қуйидаги келиб чиқади.

Исбот:

Демак, муносабат ўринли бўлади. O Тариф учун зарур бўлган с ва n0 константалар мос равишда

Демак, муносабат ўринли бўлади. O Тариф учун зарур бўлган с ва n0 константалар мос равишда

ўринлидир.

Бу шуни англатадики, алгоритмнинг умумий самарадорлиги юқорироқ ўсиш тартибига эга бўлган қисм, яьни унинг энг кам самарали қисми билан белгиланади.

Ўсиш тартибларини таққослаш учун лимитлардан фойдаланиш

О, Ω ва Ө ларнинг таърифлари уларнинг мавҳум хусусиятларини исботлаш учун ажралмас бўлсада, улар иккита ўзига хос функциянинг ўсиш тартибларини солиштириш учун камдан-кам қўлланилади. Буни амалга оширишнинг анча қулай усули бу иккита функция нисбати чегарасини ҳисоблашга асосланган. Бунда 3 та ҳолат юзага келиши мумкин.
0 - t(n) g(n) га нисбатан кичикроқ ўсиш тартибига эга эканлигини билдиради.
С- t(n) g(n) билан бир хил ўсиш тартибига эга эканлигини билдиради.
∞ - t(n) g(n) га нисбатан каттароқ ўсиш тартибига эга эканлигини билдиради

Ўсиш тартибларини таққослаш учун лимитлардан фойдаланиш

• Биринчи ҳолатда
• Иккинчи ҳолатда
• Охирги ҳолатда

Лимитга асосланган ёндашув кўпинча тарифга асосланган ёндашувдан қулайроқдир. Чунки L.Hopitals қоидасига кўра лимитларни ҳисоблаш учун қуйидаги формуладан фойдаланиш мумкин.

Ва Stirling формуласи n нинг катта қийматлари учун

Иккита функциянинг ўсиш тартибини солиштириш учун чегарага асосланган ёндашувдан фойдаланишга оид мисоллар келтирамиз.

• Иккита функциянинг ўсиш тартибини солиштириш учун чегарага асосланган ёндашувдан фойдаланишга оид мисоллар келтирамиз.
• ва ўсиш тартибини солиштиринг.
• Чегара мусбат бўлганлиги сабали фукциялар ўсиш тартиби бир хил.
• ва ўсиш тартибини солиштиринг
• Чегара нолга тенг бўлгани учу log2n √n дан кичикроқ ўсиш тартибига эга.