|
Muhammad Al-Xorazmiy nomidagi
Toshkent axborot texnologiyalari universiteti
Mustaqil ish
Algoritmlarni loyihalash
Mavzu: “Algoritmlarning eng yomon va o’rtacha holatlarda baholash”
Bajardi: Sultoniyon Yovar
Tekshirdi: Qo’ldoshev Hakim Murodilloevich
Toshkent 2022
Reja:
Algoritmning eng yaxshi ishlashi
Eng yomon holat va amortizatsiya qilingan va o'rtacha ko'rsatkich
Amaliy oqibatlar
Xulosa
Adabiyotlar
Kirish
Informatika fanida berilgan algoritmning eng yaxshi, eng yomon va oʻrtacha holatlari mos ravishda kamida, koʻpi va oʻrtacha resurslardan qanday foydalanishni ifodalaydi. Odatda ko'rib chiqilayotgan resurs ish vaqti, ya'ni vaqt murakkabligi, lekin xotira yoki boshqa manba ham bo'lishi mumkin. Eng yaxshi holat - bu n elementning kirish ma'lumotlari bo'yicha minimal qadamlar sonini bajaradigan funksiya. Eng yomon holat - n o'lchamdagi kirish ma'lumotlarida maksimal qadamlar sonini bajaradigan funktsiya. O'rtacha holat - bu n ta elementning kirish ma'lumotlari bo'yicha o'rtacha sonli qadamlarni bajaradigan funktsiya.
Haqiqiy vaqtda hisoblashda, eng yomon holatda bajarish vaqti ko'pincha alohida tashvish tug'diradi, chunki eng yomon holatda algoritm har doim o'z vaqtida tugashini kafolatlash uchun qancha vaqt kerakligini bilish muhimdir.
Algoritm tahlilida o'rtacha ishlash va eng yomon ko'rsatkichlar eng ko'p qo'llaniladi. Kamroq topilgani eng yaxshi samaradorlikdir, lekin uning qoʻllanilishi bor: masalan, alohida topshiriqlarning eng yaxshi holatlari maʼlum boʻlgan joylarda ulardan umumiy eng yomon holat tahlilining aniqligini oshirish uchun foydalanish mumkin. Kompyuter olimlari kutilgan ish vaqtini aniqlash uchun ehtimollik tahlili usullaridan, ayniqsa kutilgan qiymatdan foydalanadilar.
Atamalar boshqa kontekstlarda ishlatiladi; masalan, epidemiyaning eng yomon va eng yaxshi natijasi, elektron kontaktlarning zanglashiga olib keladigan eng yomon harorati va hokazo. Belgilangan bardoshlik komponentlaridan foydalanilganda, qurilmalar eng yomon holatlar kombinatsiyasi bilan to'g'ri ishlashga mo'ljallangan bo'lishi kerak. bardoshlik va tashqi sharoitlar.
Algoritmning eng yaxshi ishlashi
Optimal sharoitlarda algoritmning harakatini tavsiflash uchun kompyuter fanida eng yaxshi ish samaradorligi atamasi qo'llaniladi. Masalan, ro'yxatdagi oddiy chiziqli qidiruv uchun eng yaxshi holat kerakli element ro'yxatning birinchi elementi bo'lganda sodir bo'ladi.
Algoritmlarni ishlab chiqish va tanlash kamdan-kam hollarda eng yaxshi samaradorlikka asoslanadi: ko'pchilik akademik va tijorat korxonalari o'rtacha ishlarning murakkabligi va eng yomon ish faoliyatini yaxshilashga ko'proq qiziqishadi. Algoritmlar, shuningdek, cheklangan kirishlar to'plamiga qattiq kodlash yechimlari orqali eng yaxshi ish vaqtiga ega bo'lish uchun ahamiyatsiz tarzda o'zgartirilishi mumkin, bu esa o'lchovni deyarli ma'nosiz qiladi.
Eng yomon holat va amortizatsiya qilingan va o'rtacha ko'rsatkich
Eng yomon holatda ishlash tahlili va o'rtacha ish faoliyatini tahlil qilish ba'zi o'xshashliklarga ega, ammo amalda odatda turli xil vositalar va yondashuvlarni talab qiladi.
Oddiy kiritish nimani anglatishini aniqlash qiyin va ko'pincha bu o'rtacha kiritish matematik jihatdan tavsiflashni qiyinlashtiradigan xususiyatlarga ega (masalan, matn satrlarida ishlash uchun mo'ljallangan algoritmlarni ko'rib chiqing). Xuddi shunday, ma'lum bir "o'rtacha holat" ning oqilona tavsifi mumkin bo'lganda ham (bu faqat algoritmdan ba'zi foydalanish uchun qo'llanilishi mumkin), ular tenglamalarni yanada qiyinroq tahlil qilishga moyil bo'ladi.
Eng yomon holat tahlili xavfsiz tahlilni beradi (eng yomon holat hech qachon kam baholanmaydi), lekin haddan tashqari pessimistik bo'lishi mumkin, chunki bu ko'p qadamlarni qo'yadigan (haqiqiy) kirish bo'lmasligi mumkin.
Ba'zi hollarda xavfsizlikni ta'minlash uchun pessimistik tahlildan foydalanish kerak bo'lishi mumkin. Biroq, ko'pincha, pessimistik tahlil juda pessimistik bo'lishi mumkin, shuning uchun haqiqiy qiymatga yaqinlashadigan, ammo optimistik bo'lishi mumkin bo'lgan tahlil (ehtimol, muvaffaqiyatsizlik ehtimoli kamligi bilan) ancha amaliy yondashuv bo'lishi mumkin. Akademik nazariyadagi eng yomon holat va o'rtacha holat tahlili o'rtasidagi bo'shliqni bartaraf etish uchun zamonaviy yondashuvlardan biri silliqlashtirilgan tahlil deb ataladi.
Ko'pincha bajarish uchun oz vaqt ketadigan, lekin vaqti-vaqti bilan ancha kattaroq vaqtni talab qiladigan algoritmlarni tahlil qilganda, amortizatsiya qilingan tahlil operatsiyalar seriyasidagi (ehtimol cheksiz) eng yomon ish vaqtini aniqlash uchun ishlatilishi mumkin. Ushbu amortizatsiya qilingan xarajat o'rtacha xarajatga yaqinroq bo'lishi mumkin, shu bilan birga ish vaqtining kafolatlangan yuqori chegarasini ta'minlaydi. Shunday qilib, masalan. Onlayn algoritmlar ko'pincha amortizatsiya qilingan tahlilga asoslanadi.
Do'stlaringiz bilan baham: |
