O`zbekiston respublikasi axborot texnologiyalar va kommunikatsiyalarni rivojlantirish vazirligi

Umumiy qiyinchiliklarni baholash xususiyatlari

Endi biz murakkablikni hisoblash uchun eng ko'p ishlatiladigan ba'zi funktsiyalarni sanab o'tamiz. Vazifalar murakkablikning ortib boradigan tartibida keltirilgan. Ushbu ro'yxatdagi funktsiya qanchalik yuqori bo'lsa, bunday taxminga ega algoritm tezroq bajariladi.

1. 
   C doimiy
   
2. 
   log (log (N))
   
3. 
   log (N)
   

4. N ^ C, 0

5. 
   N
   
6. 
   N * log (N)
   

7. N ^ C, C> 1

8. C ^ N, C> 1

9. N!

Agar murakkablik tenglamasi ushbu funktsiyalarning bir nechtasini o'z ichiga olgan algoritmning murakkabligini baholashni istasak, tenglamani jadvalda joylashgan funktsiyaga kamaytirish mumkin. Masalan, O (log (N) + N!) = O (N!).

Agar algoritm kam miqdordagi ma'lumotlarga kamdan-kam hollarda chaqirilsa, O (N ^ 2) murakkabligini maqbul deb hisoblash mumkin, ammo agar algoritm real vaqtda ishlayotgan bo'lsa, O (N) ishlash har doim ham etarli bo'lmaydi.

Odatda, N * log (N) murakkablikdagi algoritmlar yaxshi tezlikda ishlaydi. N ^ C murakkablikdagi algoritmlardan faqat S ning kichik qiymatlari uchun foydalanish mumkin, ularning tartibi C ^ N va N funktsiyalari bilan belgilanadigan algoritmlarning hisoblash murakkabligi! juda katta, shuning uchun bunday algoritmlardan faqat oz miqdordagi ma'lumotlarni qayta ishlash uchun foydalanish mumkin.