O‘zbekiston respublikasi axborot texnologiyalari

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 teng 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) 0

5. 
   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: