Algoritmlarni baholash mezonlari Reja: I. Kirish Algoritm tushunchasi va uning ta’rifi. II. Asosiy qism Algoritmlarni baholash

Algoritmlarni baholash mezonlari

Reja:
I.Kirish
1.Algoritm tushunchasi va uning ta’rifi.
II.Asosiy qism
2.Algoritmlarni baholash.
3. Algoritmlarni tahlil qilish; eng yaxshi, eng yomon va o'rtacha ish vaqti.
III.Xulosa
IV.Foydalanilgan adabiyotlar.

Kirish.
Har qanday dasturchi uchun algoritmlar nazariyasining asoslarini bilish juda muhim, chunki algoritmlarning umumiy xususiyatlarini va ularni namoyish etish uchun rasmiy modellarni o'rganadigan fan. Hatto informatika darslaridan bizga kelajakda maktabga qaraganda murakkabroq topshiriqlarni yozishda yordam beradigan oqim jadvallarini tuzishga o'rgatiladi. Hech kimga sir emaski, deyarli har doim ma'lum bir muammoni hal qilishning bir necha yo'li mavjud: kimdir ko'p vaqt sarflashni, boshqalari resurslarni sarflashni o'z ichiga oladi, boshqalari esa deyarli echim topishga yordam beradi.
Siz har doim vazifaga muvofiq, xususan, muammolar sinfini hal qilish algoritmlarini ishlab chiqishda eng maqbul variantni izlashingiz kerak. Shuningdek, algoritm turli xil hajmlar va miqdorlarning boshlang'ich qiymatlarida o'zini qanday tutishi, unga qanday resurslar kerakligi va yakuniy natijani olish uchun qancha vaqt kerakligini baholash ham muhimdir.
Algoritm tushunchasi va uning ta’rifi.
Ma'lumotni qayta ishlash algoritmi - bu kompyuter fanida muammoni hal qilish usulining tavsifi bo'lib, uni keyinchalik tanlangan dasturlash muhitida amalga oshirish mumkin.
Algoritmni tahlil qilish - bu baholashni o'rganadigan informatika sohasidirishlash algoritmlari .
Algoritmning murakkabligi bu algoritmni tahlil qilishda hisobga olinadigan elementar operatsiyalar sonidir.
A algoritmi bilan belgilangan operatsiyalarning eng ko'p soni og'irlikning eng yomon holati bo'lib , u ma'lum bir o'lchovdagi D kirishlarni kiritadi .
Laboriousness eng yaxshi ishi algoritm operatsiyalar kichik soni A barcha yozuvlari da bir D ma'lum o'lchov n .
Laboriousness o'rtacha ishi algoritm operatsiyalar o'rtacha soni A barcha yozuvlari da bir D ma'lum o'lchov n .
Algoritmning murakkabligi funktsiyasi - algoritmning murakkabligi bu D kirishidagi A parametr parametrlariga bog'liqligi .
Algoritmning vaqt murakkabligi eng yomon holatga algoritmning murakkablik funktsiyasini asimptotik baholashdir.
Xotira hajmi - D kirish uchun A algoritmini amalga oshirishda ishtirok etadigan xotira joylarining maksimal soni .
Algoritmning kapasitiv murakkabligi bu algoritmning eng yomon holatdagi xotira funktsiyasini asimptotik baholashdir.
Algoritmning eng yomon, o'rta va eng yaxshi holatlaridagi resurslarning murakkabligi vaqt va funktsiyalar sinflarining tartiblangan juftligi.asemptomatik belgi bilan aniqlanadigan va ko'rib chiqilayotgan holatga mos keladigan sig'im murakkabligi .
Ma'lumotlar tuzilmalari bilan ishlash algoritmlari bu olinadigan asosiy tamoyillar va metodologiyani aniqlaydigan algoritmlardirma'lumotlarni qayta ishlash usullarini tushunish .
Saralash algoritmlari massivlar va fayllarni tartibga solish uchun mo'ljallangan algoritmlardir.
Qidiruv algoritmlari bu katta ma'lumotlar to'plamida ma'lum elementlarni qidirish uchun mo'ljallangan algoritmlar.
Graf algoritmlari bu amalga oshirish uchun mo'ljallangan algoritmlardirgrafik ayirish va qidirish strategiyalari .
Simlarni qayta ishlash algoritmlari bu belgilar ketma-ketligini qayta ishlash uchun bir qator usullarni o'z ichiga olgan algoritmlardir.
Geometrik algoritmlar bu geometrik ob'ektlardan foydalangan holda muammolarni echish uchun algoritmlardir.
Algoritmni baholash
Algoritmning murakkabligini o'lchashning bir necha usullari mavjud. Dasturchilar odatda algoritm tezligiga e'tibor qaratishadi, ammo boshqa ko'rsatkichlar ham bir xil ahamiyatga ega - xotira hajmiga, diskdagi bo'sh joyga talablar. Tez algoritmdan foydalanish, agar kompyuter ishlashi kerak bo'lganidan ko'proq xotirani talab qilsa, kutilgan natijalarga olib kelmaydi.
Xotira yoki vaqt
Ko'pgina algoritmlar xotira hajmi va tezligi o'rtasida tanlovni taklif qiladi. Muammoni tezroq, katta hajmdagi xotiradan foydalangan holda yoki ozroq hajmni olib, sekinroq hal qilish mumkin. Bu holatda odatiy misol eng qisqa yo'llarni qidirish algoritmi hisoblanadi. Tarmoq shaklida shahar xaritasini taqdim etib, siz ushbu tarmoqning har qanday ikkita nuqtasi orasidagi eng qisqa masofani aniqlash uchun algoritm yozishingiz mumkin. Bu masofalarni kerak bo'lganda hisoblamaslik uchun barcha nuqtalar orasidagi eng qisqa masofani ko'rsatib, natijalarni jadvalga saqlashimiz mumkin. Berilgan ikkita nuqta orasidagi eng qisqa masofani aniqlashimiz kerak bo'lsa, biz shunchaki jadvalning tugagan masofasini olishimiz mumkin. Natija bir zumda olinadi, ammo bu juda katta hajmdagi xotirani talab qiladi. Katta shahar xaritasida o'n minglab fikrlar bo'lishi mumkin. Keyin, yuqorida tavsiflangan jadvalda 10 milliarddan ortiq hujayralar bo'lishi kerak. Bular Algoritmning ishlashini yaxshilash uchun qo'shimcha 10 Gb xotirani ishlatish kerak. Ushbu qaramlikdan kosmik-vaqt murakkabligi g'oyasi kelib chiqadi. Ushbu yondashuv bilan, algoritm bajarilish tezligi va iste'mol qilinadigan xotira nuqtai nazaridan baholanadi. Vaqtinchalik murakkablikka e'tiborni qaratamiz, ammo shunga qaramay, biz iste'mol qilingan xotiraning hajmini aniq belgilaymiz.
Buyurtmani baholash
Turli xil algoritmlarni taqqoslashda ularning murakkabligi kirish ma'lumotlari miqdoriga bog'liqligini bilish muhimdir. Masalan, bitta usul yordamida saralashda ming sonlarni qayta ishlash 1 s., Va million sonlarni qayta ishlash uchun 10 s vaqt kerak bo'ladi, boshqa algoritmdan foydalanish esa 2 s vaqtni talab qilishi mumkin. va 5 s. navbati bilan Bunday sharoitda qaysi algoritm yaxshiroq ekanligini aniq aytish mumkin emas. Umumiy holda, algoritmning murakkabligini kattalik tartibida baholash mumkin. Agar kirish ma'lumotlarining o'lchamlari oshgani sayin, algoritmning bajarilish vaqti f (N) funktsiyasi bilan bir xil tezlikda oshsa, algoritmda O (f (n)) murakkablik bor. A [NxN] matritsasi uchun har bir satrda maksimal elementni topadigan kodni ko'rib chiqing.