3-Mustaqil ishi reja: p va np sinflar,np-to`liq masalalar tushunchasi

Algoritmni baholash mezonlari Og’irlikni o’lchashning yagona mezoni (RVC) algoritmning har bir bosqichi vaqtning birligida va xotira xujayrasi bitta hajm birligida (doimiyga aniq) bajarilishini taxmin qiladi. Logarifmik o’lchov mezoni (LCV) ma’lum bir operatsiya bilan ishlov berilgan operand hajmini va xotira hujayrasida saqlanadigan qiymatni hisobga oladi. LCV vaqt murakkabligi l (O p ) qiymati bilan belgilanadi , bu erda O p – operandning qiymati. LCV ning sig’im murakkabligi l (M) qiymati bilan belgilanadi , bu erda M – xotira xujayrasining kattaligi. 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, 8. C ^ N, C> 1 9. N!

• Algoritmni baholash mezonlari Og’irlikni o’lchashning yagona mezoni (RVC) algoritmning har bir bosqichi vaqtning birligida va xotira xujayrasi bitta hajm birligida (doimiyga aniq) bajarilishini taxmin qiladi. Logarifmik o’lchov mezoni (LCV) ma’lum bir operatsiya bilan ishlov berilgan operand hajmini va xotira hujayrasida saqlanadigan qiymatni hisobga oladi. LCV vaqt murakkabligi l (O p ) qiymati bilan belgilanadi , bu erda O p – operandning qiymati. LCV ning sig’im murakkabligi l (M) qiymati bilan belgilanadi , bu erda M – xotira xujayrasining kattaligi. 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, 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. Algoritmlarni tahlil qilish; eng yaxshi, eng yomon va o'rtacha ish vaqti. Bitta masalani echishning turli xil algoritmlarini ko'rib chiqsak, ular qancha hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil qilish va eng samaralisini tanlash foydalidir. Albatta, hisoblashning qaysi modelidan foydalanilganligi to'g'risida kelishib olishimiz kerak.

• 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. Algoritmlarni tahlil qilish; eng yaxshi, eng yomon va o'rtacha ish vaqti. Bitta masalani echishning turli xil algoritmlarini ko'rib chiqsak, ular qancha hisoblash resurslarini (ishlash vaqti, xotira) talab qilishini tahlil qilish va eng samaralisini tanlash foydalidir. Albatta, hisoblashning qaysi modelidan foydalanilganligi to'g'risida kelishib olishimiz kerak.