Mavzu: Algoritmlarni vaqt bo’yicha va hajmiy murakkabligini baholash uchun tekis va logarifmik baholash usullari. Bajardi: Abdusattorov Anvar; Tekshirdi: Begimov O’ktam
Download 223.27 Kb.
|
Algoritmlarni vaqt va hajmiy marakkabligini baholashda tekis va logorifmik solishtirma mezonlari
- Bu sahifa navigatsiya:
- Foydalanilgan adabiyotlar
|
Algoritmni o'sish tartibi
Murakkablikning o'sishi tartibi (yoki aksiomatik murakkablik) katta kirish o'lchamiga ega bo'lgan algoritmning murakkablik funktsiyasining taxminiy xatti-harakatlarini tavsiflaydi. Bundan kelib chiqadiki, vaqtning murakkabligini baholashda elementar operatsiyalarni ko'rib chiqishga hojat yo'q, algoritmning bosqichlarini ko'rib chiqish kifoya qiladi. Algoritmning bosqichi bu ketma-ket joylashgan elementar operatsiyalar to'plami bo'lib, ularning bajarilish vaqti kirish hajmiga bog'liq emas, ya'ni u yuqorida qandaydir doimiy bilan chegaralangan. Asimptotik baholash turlari O - eng yomon holat F (n)> 0 murakkabligini , g (n)> 0 tartibidagi funktsiyani , kirish o'lchamini n> 0 ko'rib chiqing . Agar f (n) = O (g (n)) va o'zgarmas kattaliklar ham bor c> 0 , n Vaqtning murakkabligi logarifmik og'irlik mezoni bilan Ushbu paragrafda baholanishi kerak bo'lgan operatsiyalar ko'rsatilishi kerak. Birinchidan, bu taqqoslash operatsiyalari. Ikkinchidan, o'zgaruvchan parametrlarning ishlashi (qo'shish, ko'paytirish). Belgilanish operatsiyalari hisobga olinmaydi, chunki u darhol sodir bo'ladi deb taxmin qilinadi. Shunday qilib, ushbu vazifada uchta operatsiya ajratiladi Logarifmik og'irlik mezoni bilan sig'im murakkabligi Bunday holda, xotira hujayrasida bo'lishi mumkin bo'lgan maksimal qiymatni ko'rib chiqing. Agar qiymat aniqlanmasa (masalan, operand i> 10 bilan), u holda V maksimal qiymatining chegarasi bor deb hisoblanadi . Ushbu muammoda qiymati n (i) dan oshmaydigan o'zgaruvchi va qiymati n dan oshmaydigan o'zgaruvchi mavjud ! (natija) . Shunday qilib, bal O (log (n!)) . Algoritmlarning murakkabligini o'rganish juda qiziqarli vazifadir. Hozirgi vaqtda eng oddiy algoritmlarning tahlili IT sohasidagi informatika va amaliy matematikaga jalb qilingan texnik mutaxassisliklar o'quv dasturiga kiritilgan (aniqrog'i "Informatika va kompyuter injiniringi" yo'nalishi). Murakkablikka qarab, har xil vazifalar sinflari ajralib chiqadi: P , NP , NPC . Ammo bu endi algoritmlarni asimptotik tahlil qilish nazariyasi muammosi emas. lgoritmlarning resurs samaradorligini baholash usullari Asosiy algoritmik konstruktsiyalar protsessual dasturlash quyidagilardan iborat:dallanma va pastadir. Belgilangan kirish o'lchamiga ega bo'lgan eng yaxshi, o'rta va eng yomon holatlar uchun murakkablik funktsiyalarini olish uchun asosiy algoritmik dizaynlarni baholashda farqlarni hisobga olish kerak. 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. Ushbu ta'lim, bir model sifatida, eng qismi uchun, biz oddiy bir protsessor foydalanish tasodifiy kirish mashinasi ( tasodifiy - kirish mashinasi , RAM operatsiyalar parallel ijro uchun taqdim emas). Ishlash vaqti ( ish vaqti ) algoritmi ostida biz bajaradigan elementar qadamlar sonini anglatadi. Aytaylik, psevdokodning bir qatorida belgilangan miqdordagi operatsiyalar talab etiladi (agar ba'zi bir xatti-harakatlarning og'zaki tavsifi bo'lmasa - masalan, "hamma nuqtalarni x- koordinata bo'yicha saralash "). Qo'ng'iroq qilish ( qo'ng'iroq qilish ) protsedurasini (ma'lum miqdordagi operatsiyalarni o'z ichiga olgan) va uning bajarilishini ( bajarilishini ) uzoq vaqt davomida ajratib turishingiz kerak . Algoritmning murakkabligi bu vazifaning o'lchamiga qarab talab qilinadigan manbaning kattaligi tartibini (vaqt yoki qo'shimcha xotira) aks ettiradigan qiymatdir. Shunday qilib, biz algoritmning vaqtinchalik T ( n ) va fazoviy V ( n ) murakkabligini ajratamiz. Murakkablikni baholashni ko'rib chiqishda biz vaqtinchalik murakkablikdan foydalanamiz. Fazoviy murakkablik ham shunga o'xshash tarzda baholanadi. Baholashning eng oson usuli - bu eksperimental, ya'ni algoritmni dasturlash va natijada olingan dasturni bir nechta vazifalar bo'yicha bajarish, dasturlarning bajarilish vaqtini baholash. Biroq, bu usul bir qator kamchiliklarga ega. Birinchidan, eksperimental dasturlash, ehtimol qimmat jarayon. Xulosa. Ushbu mustaqil ishni bajarish davomida algoritmlarni samaradorligini va murakkabligini baholash to’g’risida ko’plab ma’lumotlarga ega bo’lindi. Turli masalalar orqali alagoritmlarni samaradorligi va murakkabligi ko’rildi va solishtirildi. Foydalanilgan adabiyotlar: ALGORITMLASH VA DASTURLASH ASOSLARI Azamatov A.R. https://moodle.tuit.uz/ sayti Algoritmlarni loyihalash fanida berilgan dars materiallari. https://pdfslide.net/ sayti. Internet manbalari. Download 223.27 Kb. Do'stlaringiz bilan baham: 
|