1-laboratoriya ishi. Algoritmni asosiy ta`riflari, xossalari va ularning turlari. Hisoblash modellari va algoritmlarning murakkabligi. Murakkablikning asosiy resurslari: vaqt, xotira. Oddiy klassik algoritmlarni murakkabligi baholash

1-laboratoriya ishi. Algoritmni asosiy ta`riflari, xossalari va ularning turlari. Hisoblash modellari va algoritmlarning murakkabligi. Murakkablikning asosiy resurslari: vaqt, xotira. Oddiy klassik algoritmlarni murakkabligi baholash. Algoritmlarni yomon, o`rta, yaxshi holatlari
Algoritmlar nazariyasining asoslarini bilish har qanday dasturchi uchun juda muhimdir, chunki aynan shu fan algoritmlarning umumiy xususiyatlarini va ularni namoyish etishning rasmiy modellarini o'rganadi. Hatto informatika darslaridan boshlab ham bizga jadvallarni tuzishni o'rgatmoqdalar, bu keyinchalik maktabga qaraganda ancha murakkab masalalarni yozishda yordam beradi. Bundan tashqari, ma'lum bir muammoni hal qilishning deyarli har doim bir necha yo'li borligi sir emas: ba'zilari ko'p vaqt, boshqa resurslarni sarflashni o'z ichiga oladi, boshqalari esa faqat taxminiy yechim topishga yordam beradi.

Siz har doim topshiriqqa muvofiq ravishda eng maqbul narsani izlashingiz lozim, xususan, muammolar sinfini hal qilish algoritmlarini ishlab chiqishda.

Algoritmni har xil hajm va miqdorlarning boshlang'ich qiymatlari bilan qanday ishlashini, qanday manbalarga ehtiyoj borligini va yakuniy natijani chiqarish uchun qancha vaqt ketishini baholash ham muhimdir.

Bu algoritmlar nazariyasi bo'limining mavzusi - algoritmlarni asimptotik tahlil qilish nazariyasi.

Ushbu mavzuda asosiy baholash mezonlarini tavsiflash va eng oddiy algoritmni baholashga misollar keltiramiz.

Ko'pincha, algoritm tahlili bir xil masalani yechish uchun ikki xil algoritmlarni taqqoslash yoki algoritmning amaliy qo'llanilishini aniqlash uchun ishlatiladi.

Algoritmlarni bajarish vaqti bo'yicha baholashga to'xtalamiz. Algoritmlarni bajarish vaqtiga qarab baholashning yondashuvlaridan biri bu algoritmni oddiygina kompyuterda ishga tushirish va uni u yoki bu tarzda vaqtga solishdir.

Ushbu yondashuvning ko'plab kamchiliklari mavjud. Birinchidan, bajarish vaqti algoritm ishlayotgan kompyuterga juda bog'liq. Ikkinchidan, bunday taxmin kiritish ma'lumotlarining ma'lum bir o'lchovi uchun faqat bitta qiymatni beradi. Agar bizda har xil o'lchovlar bo'yicha taxminiy jadval mavjud bo'lsa ham, undan ish vaqtining kirish ma'lumotlarining o'lchamiga funksional bog'liqligini olish juda muammoli.

Shuning uchun algoritmni bajarilish vaqti bo'yicha baholash uchun kirish ma'lumotlarining o'lchamlari bo'yicha bajarilgan elementar amallar sonining funksional bog'liqligini topishga harakat qilishdir.