Muhammad Al-Xorazmiy nomidagi Toshkent Davlat Axborot Texnologiyalari Universiteti
Telekommunikatsiya Texnologiyalari fakulteti
MUSTAQIL ISH
Mavzu: Algoritmlarni baholash mezonlari.Vaqt va hajm bo’yicha baholashga misollar.
Guruh:410-21
Bajardi:Farhodov Behzod Nasriddin o’g’li
Tekshirdi: Qo’ldoshev Hakim Murodilloevich
Reja:
1. Algoritmlarni loyihalashtirishga kirish..
2.Algoritmlarni vaqt va hajm mezonlari bo’yicha baholash.
3.Keltirilgan misollar.
Algoritmning murakkabligi(Algoritmni baholash) - bu algoritmni bajarish uchun qancha vaqt yoki qancha xotira talab qilinishini ko'rsatadigan miqdoriy xarakteristikasi.
Texnologiyaning rivojlanishi xotiraning muhim manba bo'lishdan to'xtaganiga olib keldi. Shuning uchun, odamlar algoritmning murakkabligini tahlil qilish haqida gapirganda, ular odatda uning qanchalik tez ishlashini anglatadi.
Biroq, algoritmning bajarilish vaqti qaysi qurilmada ishlayotganiga bog'liq. Turli xil qurilmalarda ishlaydigan bir xil algoritm turli vaqtlarda bajariladi.
Keyin algoritmlarning murakkabligini elementar bosqichlarda o'lchash taklif qilindi - uni bajarish uchun qancha amallarni bajarish kerak. Har qanday algoritm ma'lum bir qator qadamlarni o'z ichiga oladi va u qaysi qurilmada ishlashidan qat'i nazar, qadamlar soni o'zgarishsiz qoladi. Bu fikr odatda Big O (yoki O-notatsiyasi) shaklida ifodalanadi.
Ko'pgina algoritmlar xotira hajmi va tezligi o'rtasida tanlovni taklif qiladi. Muammoni tez, katta hajmdagi xotira yordamida yoki sekinroq, kamroq joydan foydalanib hal qilish mumkin.
Bunday holatda odatiy misol eng qisqa yo'lni topish algoritmidir. Shahar xaritasini tarmoq sifatida ifodalab, ushbu tarmoqning istalgan ikkita nuqtasi orasidagi eng qisqa masofani aniqlash uchun algoritm yozishingiz mumkin. Ushbu masofalarni har safar kerak bo'lganda hisoblash o'rniga, biz barcha nuqtalar orasidagi eng qisqa masofalarni chiqarishimiz va natijalarni jadvalda saqlashimiz mumkin. Berilgan ikkita nuqta orasidagi eng qisqa masofani aniqlashimiz kerak bo'lganda, biz shunchaki jadvaldan tugagan masofani olishimiz mumkin.
Natija bir zumda olinadi, ammo bu juda katta hajmdagi xotirani talab qiladi. Katta shahar xaritasida o'n minglab nuqtalar bo'lishi mumkin. Keyin yuqorida tavsiflangan jadvalda 10 milliarddan ortiq hujayra bo'lishi kerak. Bular. algoritm tezligini oshirish uchun qo'shimcha 10 GB xotiradan foydalanish kerak.
Ushbu bog'liqlikdan fazo-vaqt murakkabligi g'oyasi kelib chiqadi. Ushbu yondashuv bilan algoritm ham bajarish tezligi, ham iste'mol qilingan xotira nuqtai nazaridan baholanadi.
Biz vaqtning murakkabligiga e'tibor qaratamiz, ammo shunga qaramay, biz iste'mol qilinadigan xotira miqdorini aniq belgilaymiz.
Tepadagi rasmda algoritmning asosiy xossalari keltirib o’tilgan.
Algoritmni vaqt va hajm jihatidan baholash informatika va dasturiy injiniringning muhim vazifasi hisoblanadi. Turli xil algoritmlarning ishlashini tahlil qilish va solishtirish uchun ishlatilishi mumkin bo'lgan turli xil texnika va usullar mavjud, masalan:
1. Asimptotik tahlil: Bu kirish hajmi oshgani sayin algoritm ishlashining yuqori yoki pastki chegarasini baholash uchun foydalaniladigan usul. Asimptotik tahlil algoritmning vaqt yoki makon nuqtai nazaridan murakkabligini tavsiflash uchun "Katta O", "Katta Omega" yoki "Katta Teta" belgilaridan foydalanishni o'z ichiga oladi. Masalan, vaqt murakkabligi O(n) bo'lgan algoritm uning ishlash vaqti kirish hajmiga qarab chiziqli ravishda oshishini bildiradi.
2. Eksperimental tahlil: Bu algoritmni turli xil kirishlar bo'yicha ishga tushirish va uning ishlashini bajarish vaqti va makondan foydalanish nuqtai nazaridan o'lchashni o'z ichiga olgan usul. Ushbu usul muayyan muammo uchun eng yaxshi algoritmni aniqlashga yordam beradi. Biroq, katta ma'lumotlar to'plamida eksperimental tahlilni o'tkazish qimmat va ko'p vaqt talab qilishi mumkin.
Algoritmlarni vaqt va hajm jihatidan baholashda bir nechta asosiy omillarni hisobga olish kerak:
1. Vaqt murakkabligi: Bu kirish hajmi oshgani sayin algoritmni ishga tushirish uchun ketadigan vaqt miqdorini bildiradi. Odatda u algoritm tomonidan qabul qilingan vaqt bo'yicha yuqori chegarani beradigan "katta O" belgisi bilan o'lchanadi. Masalan, vaqt murakkabligi O(n) bo'lgan algoritmni ishga tushirish uchun taxminan n vaqt birligi kerak bo'ladi, bu erda n - kirish hajmi.
2. Bo'shliqning murakkabligi: Bu kirish hajmi o'sishi bilan algoritm tomonidan talab qilinadigan xotira miqdorini bildiradi. Bundan tashqari, katta O belgisi yordamida o'lchanadi.
3. Kirish hajmi: Algoritm ishlashi kerak bo'lgan ma'lumotlar hajmi ham uning ishlashini baholashda muhim rol o'ynaydi. Misol uchun, O(n^2) vaqtni talab qiladigan algoritm kichik kirishlar uchun yaxshi ishlashi mumkin, lekin juda katta kirishlar uchun amaliy bo'lmasligi mumkin.
4. Eng yomon holat va o'rtacha holat: Algoritmning ishlashini baholashda eng yomon holat stsenariysi bilan bir qatorda o'rtacha stsenariyni ham hisobga olish muhimdir. Masalan, vaqt murakkabligi O(n^2) boʻlgan algoritm oʻrtacha yaxshi ishlashi mumkin, lekin maʼlum kiritish konfiguratsiyasi uchun juda uzoq vaqt talab qilishi mumkin.
5. Benchmarking: Nihoyat, algoritmlarni baholashda ularning nisbiy ishlashini baholash uchun ularni boshqa tez-tez ishlatiladigan algoritmlar yoki evristika bilan solishtirish foydalidir. Buni turli xil kirish o'lchamlari va konfiguratsiyasi uchun ularning bajarilish vaqtlari va bo'sh joy talablarini solishtirish orqali amalga oshirish mumkin.
Turli xil algoritmlarni solishtirganda, ularning murakkabligi kiritilgan ma'lumotlar miqdoriga qanday bog'liqligini bilish muhimdir. Masalan, bitta usul bilan saralashda ming sonni qayta ishlash 1 s, million raqamni qayta ishlash 10 s, boshqa algoritmdan foydalanganda esa 2 soniya vaqt olishi mumkin. va 5 s. mos ravishda. Bunday sharoitda qaysi algoritm yaxshiroq ekanligini aniq aytish mumkin emas.
Umuman olganda, algoritmning murakkabligi kattalik tartibida baholanishi mumkin. Agar kirish ma'lumotlarining o'lchami N ortishi bilan algoritmning bajarilish vaqti f(N) funksiyasi bilan bir xil tezlikda ortib borsa, algoritm O(f(n)) murakkablikka ega. A[NxN] matritsasi berilganda har bir satrda maksimal elementni topadigan kodni ko'rib chiqing.
|
