Mavzu: Algoritmlarni vaqt bo’yicha va hajmiy murakkabligini baholash uchun tekis va logarifmik baholash usullari. Bajardi: Abdusattorov Anvar; Tekshirdi: Begimov O’ktam

1 ni qo‘sh
TAKRORLANSIN 16 MARTA
1 ni qo‘sh
TAMOM
Endi bu algoritmning samaradorligi 17 ga, murakkabligi esa 17 emas, 3 ga teng. Askarlar va qayiq masalasi algoritmida 60 ta askarni daryodan o‘tkazish uchun 240 qadam bajariladi, algoritm matni esa 5 satrdan iborat. Bu algoritmning samaradorligi 240 ga, murakkabligi esa 5 ga teng. Baqa uchun tuzilgan “Baqa toq sondagi n ta bargli nilufarning 1 tartib raqamli bargiga tushdi. U barcha pashshalarni yeb 2 tartib raqamli barg ustiga borish algoritmini tuzing.” masalani algoritmida qadamlar sonini hisoblaymiz:
son + 1 + son — 1 = (n —1):2 + (n — 1):2 = n — 1.
Demak, har qanday n toq son uchun algoritmni samaradorligi n - 1 ga teng ekan. Algoritmning murakkabligi esa n toq son nechaga teng bo‘lishidan qat’iy nazar, 5 ga teng bo‘ladi!
Baqa masalasiga oid algoritmlarning samaradorligi faqat n sonining qiymatiga bog‘liq. Chunki masala shartida Baqa har bir bargdagi pashshani yeb chiqishi talab qilinadi. U holda barglar soni n ta ekanligi va Baqa biror bargning ustida turgandan keyin harakat boshlanganligidan qadamlar soni doimo n-1 ta bo‘lishi kelib chiqadi.
Haqiqatan, masalan, agar 1 tartib raqamli bargdan 4 tartib raqamlibargga o‘tish кегак bo‘lsa, u holda barcha imkoniyatlarni 1.1—1.2-rasmlarda, agar 1 tartib raqamli bargdan 5 tartib raqamli bargga o‘tish kerak bo‘lsa, u holda barcha imkoniyatlarni 1.3—1.5-rasmlardan ko‘rishimiz mumkin.


1.1-rasm




1.2-rasm



1.3-rasm



1.4-rasm
1
.5-rasm

Va nihoyat, yana bir izoh. Samaradorlik va murakkablik talabi ko‘pincha bir-biri bilan ziddiyatga kirishadi. Bu mutlaqo tabiiy. Axir, mashina sotib olayotgan bo‘lsangiz, eng chiroyli va qulay mashinaning eng arzon bo‘Iishiga umid qilmaysiz. Algoritmlashda ham shunday. Agar sizga juda samarador algoritm kerak bo‘lsa, bu algoritm boshqalariga nisbatan ancha murakkabroq bo’lishi ehtimoli katta. Amaliyotda esa oqilona murosaga kelishga to ‘g‘ri keladi.

Hisoblash qobiliyati. Ko'plab muammolarda uchraydigan yana bir xususiyat - bu ularning asosan diskretligi. Ko'plab muammolarda uchraydigan yana bir xususiyat-bu ularning asosiy ajralib turishi. Boshqacha qilib aytganda, bu shunday masalalarki, ularda yechim kombinatorial variantlarning keng to'plamidan qidirib topiladi; maqsad aniq belgilangan shartlarni qanoatlantiradigan echimni samarali topishdir.
Hisoblash samaradorligi tushunchasini aniqlash uchun, biz birinchi navbatda ish vaqtining samaradorligiga e'tibor qaratamiz: algoritmlar tez ishlashi kerak. Ammo algoritmlar boshqa resursrlardan foydalanish nuqtai nazaridan ham samarali bo'lishi mumkinligini tushunish muhimdir. Xususan, algoritm tomonidan ishlatilinadigan xotira miqdori ham samaradorlikning muhim jixati bo'lishi mumkin.
Algoritm samaradorligi. (1)T: algoritm samarali deb ataladi agar real kirish ma'lumotlari uchun u tezkor amalga oshirilsa.
(2)T: algoritm samarali deb ataladi agar u sifatli bajarilishni “to’liq qidirish”(полнiy перебор)ga nisbatan tezroq ta'minlasa.
"To'liq qidirish" usuliga qaraganda ancha yaxshi ishlashni ta'minlaydigan algoritmlar, deyarli har doim qimmatli evristik g'oyani o'z ichiga oladi, buning natijasida ushbu yaxshilanishga erishiladi; Bundan tashqari, ular ko'rib chiqilayotgan masalaning ichki tuzilishi va hisoblash qobiliyati haqida foydali ma'lumotlarni taqdim etadilar.
Polinomial vaqt samaradorlik ko'rsatkichi sifatida. Tabiiy kombinatorial masalalarda qidirish vaqti, kirish ma'lumotlari N hajmiga nisbatan eksponensional o'sishga moyildir; agar o'lcham bittaga ko'paysa, unda imkoniyatlar xajmi bir necha marta ko'payadi. Bunday masalalarni yechish uchun yaxshi algoritm yanada samarali miqyoslash modeliga ega bo'lishi kerak; kirish ma'lumotlarining kattalashib borishi bilan o’zgarmas ko’paytuvchiga(aytaylik, ikki baravar) oshishi bilan algoritmning bajarilish vaqti ham qandaydir o’zgarmas S ko’paytuvchiga ko'payishi kerak.
(3)T: Agar algoritm polinomial bajarilish vaqtiga ega bo'lsa, u samarali deb ataladi.
Lekin, polinomial vaqt d ning katta qiymatlarida yaxshi natija bermasligi mumkin, masalan d>=100 holatda bu son juda katta bo’ladi, natijada polinomial bajarilish vaqti kattalashib ketadi. Algoritm ishlayveradi. Bu xolda N^d faqat chegara vazifasini o’taydi.
Algoritmning vaqti va hajmiy murakkabligi, algoritmda ishlatilgan operatsiyalar soni va ularning har birining vaqti bilan bog'liqdir. Bu yuzdan, bir algoritmning vaqti va hajmiy murakkabligini baholash uchun, odatda algoritmdagi har bir operatsiyani bajarish uchun kerak bo'lgan vaqtni hisoblash kerak.

Algoritmlarni tekis solishtirish usuli, algoritmdagi har bir operatsiyani bajarish uchun kerak bo'lgan vaqtni hisoblashga asoslanadi. Bunda, algoritmni bajarish uchun kerak bo'lgan eng katta vaqtli operatsiya topiladi va bu operatsiya uchun kerak bo'lgan vaqtni hisoblash uchun o'zgaruvchilar yordamida yechiladi. Boshqa operatsiyalar esa bu o'zgaruvchilarga qo'shiladi. Bunday qilib, algoritmning umumiy vaqti topiladi.

Logarifmik solishtirish usuli esa algoritmdagi har bir operatsiyani bajarish uchun kerak bo'lgan vaqtni hisoblashda logarifmik funksiyalardan foydalanadi. Bu usul, algoritmdagi operatsiyalar soni katta bo'lgan holatlarda foydali bo'ladi. Bunda, algoritmning umumiy vaqti logarifmik funksiyalar yordamida yechiladi.

Bunday solishtirish usullari foydali bo'lishi uchun, algoritmlarning murakkabligi vaqti va hajmiy murakkabligi bilan bog'liq bo'lgan holatlarda qo'llaniladi. Bunday holatlarda, algoritmning murakkabligi vaqti va hajmiy murakkabligi ko'payib, algoritmni bajarish vaqtini keltirib chiqarishi mumkin.

1.Algoritmning samaradorlik ko’rsatkichlari
1. To'g'ri ishlash: Algoritmning samaradorligi, to'g'ri ishlashni ko'rsatadi. Bu, algoritmning har bir qadamini to'g'ri bajarish orqali ma'lumotlarni to'g'ri hisoblashga imkon beradi.

2. Ishonchli bo'lish: Samaradorlik, ishonchli bo'lishni talab qiladi. Algoritmning to'g'ri ishlashi uchun, dasturchi va foydalanuvchilar bu algoritmdan ishonchli bo'lishlari kerak.

3. Ishonchli ma'lumotlar: Samarador algoritm, ishonchli ma'lumotlar bilan ishlashni talab qiladi. Bu, algoritmda ishlatilayotgan ma'lumotlarning to'g'ri, aniq va to'liq bo'lishini ta'minlashga yordam beradi.

4. Tog'ri va aniqligi: Samarador algoritm, har bir qadamni to'g'ri va aniqligiga e'tibor qaratadi. Bu, algoritmda xatoliklar yuzaga kelmasligi va natijalarning aniq bo'lishi yordam beradi.

5. Yoritish: Samarador algoritm, yoritishni ta'minlashni talab qiladi. Bu, dasturchi va foydalanuvchilar uchun algoritmda qanday ishlov berishlarini tushuntirishda yordam beradi.

6. Ishonchli va to'g'ri natijalar: Samarador algoritm, ishonchli va to'g'ri natijalarni ta'minlashni talab qiladi. Bu, algoritmda aniqlanmagan xatoliklar yuzaga kelmasligi va natijalar to'liq va to'g'ri bo'lishi yordam beradi.

7. Tezlik: Samarador algoritm, tezlikni ham ko'rsatadi. Bu, algoritmda ishlov berishning tezligini oshirish yordam beradi va ishlab chiqishning tezligini ham oshiradi.

8. Murakkabligi: Samarador algoritm, murakkabligini ham aniqlashni talab qiladi. Bu, algoritmda ishlatilayotgan ma'lumotlar soni, qadam soni va boshqa faktorlar kabi muhim narsalarni ko'rsatish yordam beradi.
2.Algoritmning murakkabligini aniqlash.
Algoritmlarning murakkabligini aniqlash uchun, algoritmda ishlatiladigan operatsiyalar soni, o'zaro aloqadorliklar soni va algoritmning ishga tushirish vaqti kabi ma'lumotlarni olish kerak. Bunday ma'lumotlar, algoritmlarning murakkabligini tushunish va optimallashtirish uchun juda muhimdir. Murakkab algoritmlar, ishga tushirish vaqti va resurslarni ko'p sarflaydi, shuning uchun optimallashtirish kerak bo'ladi.
3. Algoritmning hisoblash qobiliyati. Algoritmning hisoblash qobiliyati, algoritmda ishlatiladigan operatsiyalar soni va o'zaro aloqadorliklar soni bilan belgilanadi. Bu qobiliyat, algoritmda ishlatilgan operatsiyalar va o'zaro aloqadorliklar soni ko'paytikca, algoritmdagi hisoblash jarayoni murakkablashadi. Shuning uchun, algoritmlar hisoblash qobiliyati ko'paytikca murakkablashadi va ishga tushirish vaqti ham ko'payadi. Hisoblash qobiliyati, algoritmlarni optimallashtirish uchun muhim ma'lumotlardan biridir.
Logarifmik solishtirma mezonlari, algoritmlarning murakkabligini baholashda katta ahamiyatga ega. Bu mezonlar, algoritmlarning ishga tushirish vaqti va xotirani kamaytirishda yordam beradi. Algoritmlarning murakkabligini oshirish uchun, logarifmik solishtirma mezonlari, qidiruvchi algoritmlar va sortirovka algoritmlari kabi ko'p maqsadli algoritm turlarida foydalaniladi.

Logarifmik solishtirma mezonlari, ma'lumotlar sonining kattaligiga nisbatan murakkabligi kamaytiriladi. Bunday mezonlar, ma'lumotlar soni kattalashtikda ham murakkablikni oshirmaydi. Misol uchun, bir massivni tartiblashda yoki bir elementni qidirishda logarifmik solishtirma mezonlariga e'tibor qaratiladi.

Logarifmik solishtirma mezonlari, O(log n) shaklida ifodalangan. Bu shaklda "n" ma'lumotlar sonini anglatadi. Bunda "log" esa logarifmni ifodalaydi. Shuning uchun, algoritmlar murakkabligi O(log n) bo'lgan paytda yaxshi natijalar ko'rsatadi.

4.Algoritmni baholashda tekis solishtirma mezonlari:
1. Ishlatilayotgan ma'lumotlar soni: Algoritmning murakkabligini aniqlash uchun, ishlatilayotgan ma'lumotlar soni katta bo'lsa, bu algoritmda ko'p qadam va hisoblashlar amalga oshirishi mumkin. Bunday holatda, murakkabligi yuqori bo'ladi.

2. Qadam soni: Algoritmning murakkabligi, ishlatilayotgan qadam soniga bog'liq bo'ladi. Agar algoritm ko'p qadamli bo'lsa, bu murakkabligini oshiradi.

3. Boshqa faktorlar: Algoritmda foydalanilayotgan boshqa faktorlar, masalan, ishlatilayotgan dasturlash tillari yoki ko'rsatilayotgan ma'lumotlarning turi ham murakkabligi ta'sir etishi mumkin.

Bularning har biri algoritmlarning murakkabligini baholashda muhim hisoblanadi. Shuningdek, murakkablikni kamaytirish uchun optimallashtirish va boshqa yondashuvlar ham foydali bo'ladi.

5. Mavjud algoritmlarning ko’pchilig xotira va tezlik o’rtasida tanlovni taklif 
qiladi. Masala tez ishlashi va katta xotira egallashi yoki sekin ishlashi va kichik 
xotira hajmini egallashi mumkin. Bu holatda eng odatiy misollardan biri eng 
qisqa masofani topish masalasi bo’la oladi. Bunda siz o’zaro bog’liq bo’lgan 
shahar orasidagi istalgan ikki nuqta orasidagi eng qisqa masofani topishingiz 
kerak bo’ladi. Bunda biz barcha nuqtalar orasidagi qisqa masofalarni aniqlab 
ularni jadval shaklida saqlab qo’yishimiz mumkin. Va biz eng qisqa masofani 
aniqlashimizga to’g’ri kelganda shunchaki jadvaldan ma’lumotni olib qo’yishimiz mumkin bo’ladi. Natijani shu zahoti olishimiz mumkin, ammo bu juda katta hajm talab qiladi. Masalan biror katta xaritada 10 minglab nuqtalar bo’lishi mumkin va 
bizning jadvalimiz buning uchun 10 milliarddan ortiq ma’lumotni saqlashiga 
to’g’ri keladi va bu taxminan 10GB ga yaqin xotirani band etishi mumkin. 
Ushbu holatdan hajm-vaqt murakkabligi kelib chiqadi. Shunda algoritm 
vaqt bo’yicha ishlash tezligi yoki hajm bo’yicha ishlash tezligi bilan baholanadi. 
Biz asosiy e’tiborni vaqt bo’yicha murakkablikka qaratamiz lekin shu 
bilan birga foydalaniladigan xotira hajmini ham aniq belgilashimizga to’g’ri 
keladi.