|
Algoritm va dasturlarning murakkabligini baholash
|
| bet | 4/4 | | Sana | 30.07.2023 | | Hajmi | 21.76 Kb. | | #77669 |
Bog'liq 1 Algoritm murakkabligini statik va dinamik o‘lchovlari Vaqt va Boymamatova Rayhona Abduhalil qizi, erkin-iqtisodiy-hududlarni-tashkil-etishda-jahon-tajribasi, H , 1. Пул ва банклар НЎД, KOSMONAVTIKA KUNI, kllqNsMrYUpx59jvw5Q9TAFI6iBIlR1COmUr54Nc, Mavzu Jismoniy madaniyat nazariyasi va metodikasi fan sifatida, McDonald\'s kompaniyasi, Sayyoramizni asrang!, 1701192845, EVTANAZIYA VA PALLIATIV YORDAM ETIK MUAMMOLAR SIFATIDA, Talabalardagi psixologik stress holatini yengishning tarbiyaviy -fayllar.org, Talabalardagi psixologik stress holatini yengishning tarbiyaviy -fayllar.org (1), 1 Aylantiruvchi moment formulasini korsating?-fayllar.orgAlgoritm va dasturlarning murakkabligini baholash.
Bog'liqlikni tiklash algoritmlari.
Ba'zi hollarda dasturning tuzilishi noma'lum va siz faqat turli o'lchamdagi kirish ma'lumotlari uchun uning ishlash vaqtini aniqlashingiz mumkin. T(N) (sek.)
Dasturning, funksiyaning murakkabligining analitik bog'liqligini qurish T(N) ba'zi bir intervalda [ Nmin, Nmax] ... Keyinchalik, ba'zi bir analitik funktsiyaning topilgan egri chizig'i funksiya parametrlarining o'zgarishi va yaqinlashish xatosining taxmini bilan yaqinlashtiriladi.
Algoritmning ishlash vaqti, ya'ni vaqt murakkabligi yuqoridan ma'lum darajada ko'phad bilan chegaralangan bo'lsa, u ko'pnomli deyiladi. T(N)= O(Nm) ... Keyin bunday algoritm bilan yechilgan barcha masalalar P-sinf masalalarni tashkil qiladi. Bu vazifalar R.ga kiritilganligi aytiladi.
Eksponensial vaqt murakkabligi bilan bog'liq muammolar ( T(N)= O(KN) ) R ga kiritilmagan.
Izoh : Chiziqli murakkablikdagi masalalar P ga kiritilganligini ko'rsatish mumkin
T(N)= O(N1 )
Keling, deterministik bo'lmagan algoritm yordamida polinom vaqtida yechish mumkin bo'lgan NP-muammolar sinfini kiritamiz.
Algoritm holatini hozirda bajarilayotgan buyruq manzili va jarayon holati vektoriga ekvivalent bo'lgan barcha o'zgaruvchilar qiymatlari to'plami sifatida belgilaymiz. Shuning uchun ko'pchilik algoritmlar deterministikdir, ya'ni ularda har qanday holat uchun faqat bitta ruxsat etilgan keyingi holat (shart va tanlash operatsiyalari) mavjud. Bu shuni anglatadiki, bunday algoritm bir vaqtning o'zida bitta ishni bajarishi mumkin.
V deterministik bo'lmagan algoritm (NDA) har qanday holat uchun bir nechta ruxsat etilgan keyingi holat bo'lishi mumkin, ya'ni bunday algoritm bir vaqtning o'zida bir nechta operatorni bajarishi mumkin.
NDA tasodifiy yoki ehtimolli algoritm emas. Bu ko'plab shtatlarda bo'lishi mumkin bo'lgan algoritmdir (bu ko'plab variantlar bilan parallel ravishda muammoni hal qilishga teng).
Yechim algoritmini toping E * funksiyalarga qaraganda oddiyroq E... Ammo shu bilan birga, maqsadga muvofiqligini isbotladi E *, biz asl funktsiyaning qoniqarliligini isbotlaymiz E.
Maxsus holat: K = 2 uchun funktsiya E R ga kiritilgan.
|
| |
