Hisoblash modellari, algoritmlar va ularning murakkabligi Algoritm tushunchasi. Avvalo algoritm

Yomon, oʻrtacha yoki eng yaxshi darajadagi murakkablik tushunchalari mavjud. Odatda, eng yomon holatning murakkabligi baholanadi.
Eng yomon holatda vaqt murakkabligi - bu berilgan kattalikdagi masalani yechishda algoritm ishlashi davomida bajariladigan amallarning maksimal soniga teng boʻlgan kirish kattaligining funksiyasidir.
Eng yomon sigʻimli murakkablik - bu kirish hajmining ma‘lum hajmdagi muammolarni yechishda erishilgan maksimal xotira yacheykalari soniga teng funksiyasi.
Algoritm murakkabligini baholash kriteriyalari. Bir xil me‟yorda oʻlchash kriteriyasi algoritmning har bir bosqichi bir vaqt birligida, xotira yacheykasi esa hajmning bir birligida (konstanta boʻyicha aniqlikda) bajarilishini nazarda tutadi.
21
Logarifmik oʻlchash kriteriyasi ma‘lum amal bilan qayta ishlanadigan operand oʻlchamini va xotira yacheykasida saqlanadigan qiymatni hisobga oladi.
Misol. Faktorialni hisoblashning murakkabligini baholash.
#include
using namespace std;
int main()
{
int n = 20;
long long result=1;
for (int i=2; i<=n; i++)
result *=i;
cout<
return 0;
}
Berilgan masalaning kirish kattaligi n ekanligini aniqlash oson. Qadamlar soni (n - 1). Shunday qilib, bir xil me‘yorda oʻlchash kriteriyasi uchun vaqt murakkabligi O(n) dir.
Logarifmik oʻlchash kriteriyasi bilan vaqt murakkabligi. Shu nuqtada, baholanishi kerak boʻlgan amallarni ajratib koʻrsatish kerak. Birinchidan, bu taqqoslash amallari. Ikkinchidan, oʻzgaruvchi qiymatiga ta‘sir qiluvchi amallar (qoʻshish, koʻpaytirish, boʻlish, ayirish). Oʻzlashtirish (ta‘minlash) amali hisobga olinmaydi, chunki ular bir zumda amalga oshiriladi deb taxmin qilinadi.
Shunday qilib, ushbu masala uchta amal ajratilgan:
1) i-qadamda ni olamiz. Qadamlar soni ta boʻlgani uchun ushbu amalning murakkabligi ga tengdir.
2) i++; i-qadamda ni olamiz.
22
Ushbu holatda, quyidagicha yigʻindi hosil boʻladi: Σ
3) result *=i; i-qadamda ( ) ni olamiz.
Ushbu holatda, quyidagi yigʻindi hosil boʻladi: Σ ( ) (Π )
Agar biz barcha olingan qiymatlarni yigʻsak va n ning oʻsishi bilan asta sekin oʻsadigan atamalarni bekor qilsak, (Π )
biz yakuniy ifodasini olamiz.