Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari univesiteti

 

---

Rekursiv algoritmlarni baholash 
Oddiy rekursiya. 
Rekursiv funksiyalar bu o’z-o’zini chaqiruvchi funksiyalardir. Rekursiv 
algoritmlarni baholash juda murakkabdir. Ularning murakkabligini baholash 
nafaqat ichki foydalanilgan funksiyalar, yana rekursiyaning takrorlanishiga 
ham bog’liq bo’ladi. Keling oddiy rekursiya misolida faktorialni hisoblash 
funksiyasini ko’raylik: 
Ushbu rekursiv funksiyada ortiqcha sikllar va ortiqcha funksiyalar 
mavjud emas shuning uchun bu funksiya faqat N marta takrorlanadi va uning 
murakkabligi O(N) ga te
ng bo’ladi. Ushbu dasturning ishlash vaqti 
quyidagicha: 
Bundan tashqari rekursiv funksiyalarda rekursiya chuqurligi ya’ni 
rekursiyaning qancha marotaba takrorlanishi muammosi mavjuddir. Bu esa 
mashinaning xotira bilan bog’liq muammolariga bog’liqdir. 
Xulosa 
Xulosa o’rnida aytadigan bo’lsak, algoritmlar asosan quyidagicha 
ko’rinishdagi murakkabliklarda bo’ladi va barcha algoritmlarni baholashimiz 
uchun mana shu murakkabliklar yetarli bo’ladi: 
1. C yoki O(1) - 
algoritm o’zgarmas vaqtda bajariladi. 
2. O(log(log(N))) 
3. O(log(N)) 
4. O(N^C) 05. O(N) 
6. O(N*log(N)) 
7. O(N^C) C > 1 

---

8. O(C^N) C > 1 
9. O(N!) 
Agar biz ushbu murakkablikni aniqlaydigan bo’lsak: 
O(log(N) + N!) = O(N!). Bunda f(N) = N! funksiya f(N) = log(N) funksiyadan 
ko’ra tezroq o’suvchi. Shuning uchun algoritmning murakkabligini O(N!) deb 
olishimiz yetarli bo’ladi. Quyida murakkabliklarning turli kiruvchi 
ma’lumotlardagi bajarilish vaqti keltirilgan: