‘zbekiston respublikasi


Download 308.66 Kb.
bet3/3
Sana21.06.2023
Hajmi308.66 Kb.
#1639810
1   2   3
Bog'liq
Muhammad al xorazmiy nomidagi toshkent axborot texnologiyalari u

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.


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) 06. 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:

Download 308.66 Kb.

Do'stlaringiz bilan baham:
1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling