Mustaqil ish mavzu: Algoritmlarni vaqt bo’yicha va hajmiy murakkabligini baholash uchun tekis va logarifmik baholash usullari. Bajardi: Pardayev Jonibek Tekshirdi: Narmanov Otabek

(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.