logo

Algoritmlarni tahlil qilish asoslari. Turli xil ishlash baholari algoritmlar

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

24.6455078125 KB
Mavzu:      Algoritmlarni tahlil qilish asoslari. Turli xil ishlash baholari 
algoritmlar.
                                 Reja:
1. Algoritm tushunchasi.
2. Algoritm xossalari.
3. Algoritmlarni tahlil qilish.
      Algoritm  so`zi  va  tushunchasi  IX  asrda  yashab  ijod  etgan  buyuk 
bobokalonimiz  Muxammad  al-Xorazmiy  nomi  bilan  uzviy  bog`liq  bo`lib,  
uning arifmetikaga  bag`ishlangan  “Al  jabr  va  al-muqobala”  nomli  asarining  
dastlabki betidagi  “Dixit  Algoritmic”  (“Dediki  Al  Xorazmiy”ning  lotincha  
ifodasi)  degan jumlalardan kelib chiqqan.
  Algoritm-   bu  aniq  hisoblashlami  bajaruvchi  protsedura  bo’lib unga kirish  
qismida kattalik yoki  kattaliklar berilib chiqishda natijaviy kattalik yoki kattaliklar
olinadi. Demak algoritm hisoblovchi qadamlardan  tashkil  topgan  bo'lib,  
dastlabki  qiymatlarga  ko‘ra natijaviy  kattaliklar  qiymatini  beradi.
  Algoritmning asosiy xossalari quyidagilardan iborat:
1.  Diskretlilik.  Bu xossaning mazmuni-algoritmlarni doimo chekli qadamlardan  
iborat qilib bo`laklash imkoniyati mavjudligidadir. Boshqacha aytganda, uni chekli
sondagi  oddiy  ko`rsatmalar  ketma-ketligi  shaklida  ifodalash  mumkin. 
Algoritmning  bu  xossasi  yuqorida  keltirilgan  hamma  misollarda  yaqqol  
ko`rinib turibdi.  Agar  kuzatilayotgan  jarayonni  chekli  qadamlardan  iborat  qilib
bo`laklay olmasak, u holda uni algoritm deb bo`lmaydi.
2.  Tushunarlilik .  Algoritmning  ijrochisi  hamma  vaqt  inson  bo`lavermaydi. 
Choy damlashni yoki boshqa ishlarni bajarishni faqat odamga emas, balki robotga 
ham  buyurish  mumkin.  Ijrochiga  tavsiya  etilayotgan  ko`rsatmalar  uning  
uchun tushunarli bo`lishi kerak, aks holda ijrochi oddiygina amalni ham bajara 
olmaydi. Bundan tashqari, ijrochi har qanday amalni bajara olmasligi ham 
mumkin. Har  bir  ijrochining  bajara  olishi  mumkin  bo`lgan  ko`rsatmalar  yoki  
buyruqlar birikmasi  mavjud  bo`lib,  u  ijrochining  ko`rsatmalar  tizimi  
(sistemasi)  deyiladi. Shuning  uchun  ijrochi  uchun  berilayotgan  har  bir  
ko`rsatma  ijrochining ko`rsatmalar tizimiga tegishli bo`lishi kerak. Ko`rsatmalarni
ijrochining ko`rsatmalar tizimiga tegishli bo`ladigan qilib ifodalay olishimiz 
muhim ahamiyatga ega. Masalan, pastki sinfning a'lochi o`quvchisi “son kvadratga
oshirilsin”  degan  ko`rsatmani  tushunmasligi  natijasida  bajara olmaydi. Lekin   “son o`zini o`ziga ko`paytirilsin”  shaklidagi ko`rsatmani  bemalol bajaradi.  
Sababi,  u  ko`rsatma  mazmunidan  ko`paytirish  amalini  bajarish  kerakligini 
anglaydi.
3.  Aniqlik.   Ijrochiga  berilayotgan  ko`rsatmalar  aniq  mazmunda  bo`lishi  kerak.
Chunki,  ko`rsatmadagi  noaniqliklar  mo`ljaldagi  maqsadga  erishishga  olib 
kelmaydi. Odam uchun tushunarli bo`lgan “3-4 marta silkitilsin”, “5-10 daqiqa 
qizdirilsin”, “1-2  qoshiq  solinsin”,  “tenglamalardan  biri  yechilsin”  kabi  noaniq
ko`rsatmalar robot  yoki  kompyuterni  qiyin  ahvolga  solib  qo`yadi.  Bundan  
tashqari, ko`rsatmalarning  qaysi  ketma-ketlikda  bajarilishi  ham  muhim  
ahamiyatga  ega. Demak,  ko`rsatmalar  aniq  berilishi  va  faqat algoritmda  
ko`rsatilgan  tartibda bajarilishi shart ekan.
4.  Ommaviylik .  O`ar  bir  algoritm  mazmuniga  ko`ra  bir  turdagi  masalalarning 
barchasi  uchun  ham  o`rinli  bo`lishi  kerak.  Ya'ni,  masaladagi  boshlang’ich 
ma'lumotlar  qanday  bo`lishidan  qat'iy  nazar  algoritm  shu  xildagi  har  qanday  
masalani yechishga yaroqlidir.
5.   Natijaviylik.   O`ar  bir  algoritm  chekli  sondagi  qadamlardan  keyin  albatta 
natija  berishi  shart.  Bajariladigan  amallar  ko`p  bo`lsa  ham  baribir  natijaga  
olib kelishi kerak. Chekli qadamdan keyin qo`yilgan masala yechimga  ega 
emasligini aniqlash  ham  natija  hisoblanadi.  Agar  ko`rilayotgan  jarayon  
cheksiz  davom  etib natija bermasa, uni algoritm deb ayta olmaymiz.  
                       Algoritmning turlari
Algoritmlarni asosan 3 turga bo`lish mumkin:
1)  Chiziqli algoritmlar;
2)  Tarmog`lanuvchi algoritmlar;
3)  Takrorlanuvchi algoritmlar.
                       Chiziqli algoritmlar Chiziqli algoritmlarda asosan hech qanday shart tekshirilmaydi va jarayonlar tartib 
bilan  ketma-ket  bajariladi.  Demak,  chiziqli  algoritmlar  sodda  hisoblashlar  
yoki amallar  ketma-ketligidir.  Chiziqli algoritmlarga  misol  qilib  quyidagi  
formulalar bo`yicha hisoblashlarni keltirish mumkin.
                  Tarmog`lanuvchi algoritmlar.
Biror  shartning  bajarilishi  bilan  bog`liq  ravishda  tuziladigan  algoritmlarga 
tarmog`lanuvchi  algoritmlar  deyiladi.  Tarmog`lanuvchi  algoritmlar  hisoblashlar
ketma-ketligini  aniqlaydigan  shartlarni  o`z  ichiga  oladi.  Blok-sxema  
ko`rinishida bu  shuni  bildiradiki,  blok-sxemada  hech  bo`lmaganda  bitta  romb  
ishtirok  etadi. Masalan:  ko`chaga  qanday  kiyimda  chiqishimiz  ob-havoga,  
avtomatdan  sharbatli  yoki  mineral  suv  ichishimiz  esa  unga  qancha  so`mlik  
“jeton”  bog`liqdir.  Yuqorida  keltirilgan  “Svetofor”  algoritmi  ham  
tarmog`lanuvchi  algoritmga misoldir.
                 Takrorlanuvchi (siklik) algoritmlar.
Ma'lum  bir  shart  asosida  algoritmda  bir  necha  marta takrorlanish  yuz  
beradigan  jarayonlar  ham  ko`plab  uchraydi.  Masalan,  yil  fasllarining  har  yili  
bir  xilda takrorlanib kelishi, har haftada bo`ladigan darslarning kunlar bo`yicha 
takrorlanishi  va  hokazo.  Demak,  takrorlanuvchi  algoritmlar  deb  shunday  
algoritmlarga aytiladiki,  unda  bir  yoki  bir  necha  amallar  ketma-ketligi  bir  
necha  marta  takrorlanadi, bu ketma-ketlik tarmog`lardan iborat bo`lishi ham 
mumkin. Bundan chiziqli va tarmog`lanuvchi algoritmlar takrorlanuvchi 
algoritmlarning xususiy holi ekanligi kelib chiqadi.
       Algoritmni tahlil qilish tushunchasi.
Algoritm tahlilini, qo’yilgan masalani ushbu algoritm bilan еchish qancha vaqt 
talab qilishi darajasi dеb tasavvur qilish mumkin. Har bir qaralayotgan algorimtni 
N o’lchovli boshlang’ich ma'lumotlar massividagi masalalarning qanchalik tеz 
еchilishi bilan baholaymiz. Masalan, saralash algoritmi N ta qiymatdan iborat 
ro’yxatni o’sish tartibida joylashtirish uchun qancha taqqoslash talab qiladi yoki  N*N o’lchamli ikkita matritsani ko’paytirishda qancha arifmеtik amallar 
zarurligini hisoblash7. Bitta masalani turli algoritmlar bilan еchish mumkin. 
Algoritmlar tahlili bizga algoritmni tanlash uchun qurol bo’ladi.
Algoritm tahlilining natijasi – bеlgilangan algoritmning kompyutеrdan qancha vaqt
yoki takrorlash talab qilishini aniq hisoblovchi formula emas. Bunday ma'lumot 
muhim emas, bu holatda kompyutеr turi, u bitta yoki undan ortiq foydalanuvchi 
tomonidan ishlatilyaptimi, uning protsеssori va chastotasi qanaqa, protsеssor 
chipida komandalar to’liqmi va kompilyator bajarilayotgan kodni qay darajada 
amalga oshirmoqda kabi tomonlarni nazarda tutish kеrak. Bu shartlar algoritm 
bajarilish natijasida dasturning ishlash tеzligiga ta'sir qiladi. Yuqoridagi shartlar 
hisobiga dasturni boshqa tеz ishlaydigan kompyutеrga o’tkazilganda algoritm 
yaxshi ishlaganday bajarilishi tеzroq amalga oshadi. Aslida esa unday emas, biz 
shuning uchun tahlilimizda kompyutеrning imkoniyatlarini inobatga olmaymiz.
Oddiy va katta bo’lmagan dasturlarda bajariladigan amallar sonini N ning 
funktsiyasi ko’rinishida aniq hisoblash mumkin. Aksariyat holatlarda bunga 
zaruriyat qolmaydi. 
Algoritm tomonidan bajariladigan jarayonlar borki, biz ularning hammasini 
hisoblab o’tirmaymiz, buning sababi shundaki, hatto uning eng kichik sozlashi 
ham samaradorlikning sеzilmas yaxshilanishiga olib kеladi. 
Algoritm murakkabligini baholash kriteriyalari
Bir   xil   me’yorda   o’lchash   kriteriyasi   algoritmning  har   bir   bosqichi   bir   vaqt
birligida,   xotira   yacheykasi   esa   hajmning   bir   birligida   (konstanta   bo’yicha
aniqlikda) bajarilishini nazarda tutadi.
Logarifmik   o’lchash   kriteriyasi   ma'lum   amal   bilan   qayta   ishlanadigan
operand o’lchamini va xotira yacheykasida saqlanadigan qiymatni hisobga oladi. Faktorialni hisoblashning murakkabligini baholash.
#include <iostream>
using namespace std;
int main()
{
   int n = 20;
   long long result=1;
   for (int i=2; i<=n; i++)
    result *=i;
   cout<<result;
    return 0;
}
Berilgan masalaning kirish kattaligi n ekanligini aniqlash oson.
Qadamlar soni (n - 1).
Shunday qilib, bir xil me’yorda o’lchash kriteriyasi uchun vaqt murakkabligi
O(n) dir.
Logarifmik o’lchash kriteriyasi  bilan vaqt murakkabligi
Shu   nuqtada,   baholanishi   kerak   bo'lgan   amallarni   ajratib   ko'rsatish   kerak.
Birinchidan,   bu   taqqoslash   amallari.   Ikkinchidan,   o'zgaruvchi   qiymatiga   ta’sir
qiluvchi amallar (qo'shish, ko'paytirish, bo’lish, ayirish). O’zlashtirish (ta’minlash)
amali   hisobga   olinmaydi,   chunki   ular   bir   zumda   amalga   oshiriladi   deb   taxmin
qilinadi.
Shunday qilib, ushbu masala uchta amal ajratilgan:
1)i≤n
i-qadamda  log	
( n	)
 ni olamiz. Qadamlar   soni  n−1   ta   bo’lgani   uchun   ushbu   amalning   murakkabligi	
(n−1)∗log	 (n)
 ga tengdir.
2) i + + ;
i-qadamda  log	
( n	)
 ni olamiz.
Ushbu holatda, quyidagicha yig’indi hosil bo’ladi: 	
∑i=2
n	
log	2i=log	2(i!)
3) result *=i;
i-qadamda  log	
(( i − 1	) !)
ni olamiz.
Ushbu holatda, quyidagi yig’indi hosil bo’ladi:	
∑i=2
n	
log	2((i−1)!)=	log	2(∏i=2
n	
(i−1)!)
Agar biz barcha olingan qiymatlarni yig'sak va n ning o'sishi bilan asta sekin
o'sadigan atamalarni bekor qilsak, 	
O(log	2(∏i=2
n	
(i−1)!))
 biz yakuniy ifodasini olamiz.
Bir xil me’yorda o’lchash kriteriyasi  bo’yicha sig'imning murakkabligi
Bu   yerda   hamma   narsa   oddiy.   O'zgaruvchilar   sonini   hisoblashingiz   kerak.
Agar topshiriq massivlardan foydalansa, massivdagi  har bir yacheyka o'zgaruvchi
hisoblanadi.
O'zgaruvchilar   soni   kirish   kattaligiga   bog'liq   bo'lmaganligi   sababli,
murakkablik O (1) bo'ladi.
Logarifmik o’lchash kriteriyasi  ega bo'lgan sig'imning murakkabligi
Bunday   holda,   siz   xotira   yacheykasida   bo'lishi   mumkin   bo'lgan   maksimal
qiymatni   hisobga   olishingiz   kerak.   Agar   qiymat   aniqlanmagan   bo'lsa   (masalan,	
i>10
 operand bo'lganda), u holda 	Vmax  chegaraviy qiymati bor deb hisoblanadi. Ushbu   masalada   qiymati   n   (i)   dan   oshmaydigan   va   n   (result)   qiymatidan
oshmaydigan o'zgaruvchi mavjud. Shunday qilib,  O ( log ( n ! ) )
 ga teng.

Mavzu: Algoritmlarni tahlil qilish asoslari. Turli xil ishlash baholari algoritmlar. Reja: 1. Algoritm tushunchasi. 2. Algoritm xossalari. 3. Algoritmlarni tahlil qilish.

Algoritm so`zi va tushunchasi IX asrda yashab ijod etgan buyuk bobokalonimiz Muxammad al-Xorazmiy nomi bilan uzviy bog`liq bo`lib, uning arifmetikaga bag`ishlangan “Al jabr va al-muqobala” nomli asarining dastlabki betidagi “Dixit Algoritmic” (“Dediki Al Xorazmiy”ning lotincha ifodasi) degan jumlalardan kelib chiqqan. Algoritm- bu aniq hisoblashlami bajaruvchi protsedura bo’lib unga kirish qismida kattalik yoki kattaliklar berilib chiqishda natijaviy kattalik yoki kattaliklar olinadi. Demak algoritm hisoblovchi qadamlardan tashkil topgan bo'lib, dastlabki qiymatlarga ko‘ra natijaviy kattaliklar qiymatini beradi. Algoritmning asosiy xossalari quyidagilardan iborat: 1. Diskretlilik. Bu xossaning mazmuni-algoritmlarni doimo chekli qadamlardan iborat qilib bo`laklash imkoniyati mavjudligidadir. Boshqacha aytganda, uni chekli sondagi oddiy ko`rsatmalar ketma-ketligi shaklida ifodalash mumkin. Algoritmning bu xossasi yuqorida keltirilgan hamma misollarda yaqqol ko`rinib turibdi. Agar kuzatilayotgan jarayonni chekli qadamlardan iborat qilib bo`laklay olmasak, u holda uni algoritm deb bo`lmaydi. 2. Tushunarlilik . Algoritmning ijrochisi hamma vaqt inson bo`lavermaydi. Choy damlashni yoki boshqa ishlarni bajarishni faqat odamga emas, balki robotga ham buyurish mumkin. Ijrochiga tavsiya etilayotgan ko`rsatmalar uning uchun tushunarli bo`lishi kerak, aks holda ijrochi oddiygina amalni ham bajara olmaydi. Bundan tashqari, ijrochi har qanday amalni bajara olmasligi ham mumkin. Har bir ijrochining bajara olishi mumkin bo`lgan ko`rsatmalar yoki buyruqlar birikmasi mavjud bo`lib, u ijrochining ko`rsatmalar tizimi (sistemasi) deyiladi. Shuning uchun ijrochi uchun berilayotgan har bir ko`rsatma ijrochining ko`rsatmalar tizimiga tegishli bo`lishi kerak. Ko`rsatmalarni ijrochining ko`rsatmalar tizimiga tegishli bo`ladigan qilib ifodalay olishimiz muhim ahamiyatga ega. Masalan, pastki sinfning a'lochi o`quvchisi “son kvadratga oshirilsin” degan ko`rsatmani tushunmasligi natijasida bajara olmaydi. Lekin

“son o`zini o`ziga ko`paytirilsin” shaklidagi ko`rsatmani bemalol bajaradi. Sababi, u ko`rsatma mazmunidan ko`paytirish amalini bajarish kerakligini anglaydi. 3. Aniqlik. Ijrochiga berilayotgan ko`rsatmalar aniq mazmunda bo`lishi kerak. Chunki, ko`rsatmadagi noaniqliklar mo`ljaldagi maqsadga erishishga olib kelmaydi. Odam uchun tushunarli bo`lgan “3-4 marta silkitilsin”, “5-10 daqiqa qizdirilsin”, “1-2 qoshiq solinsin”, “tenglamalardan biri yechilsin” kabi noaniq ko`rsatmalar robot yoki kompyuterni qiyin ahvolga solib qo`yadi. Bundan tashqari, ko`rsatmalarning qaysi ketma-ketlikda bajarilishi ham muhim ahamiyatga ega. Demak, ko`rsatmalar aniq berilishi va faqat algoritmda ko`rsatilgan tartibda bajarilishi shart ekan. 4. Ommaviylik . O`ar bir algoritm mazmuniga ko`ra bir turdagi masalalarning barchasi uchun ham o`rinli bo`lishi kerak. Ya'ni, masaladagi boshlang’ich ma'lumotlar qanday bo`lishidan qat'iy nazar algoritm shu xildagi har qanday masalani yechishga yaroqlidir. 5. Natijaviylik. O`ar bir algoritm chekli sondagi qadamlardan keyin albatta natija berishi shart. Bajariladigan amallar ko`p bo`lsa ham baribir natijaga olib kelishi kerak. Chekli qadamdan keyin qo`yilgan masala yechimga ega emasligini aniqlash ham natija hisoblanadi. Agar ko`rilayotgan jarayon cheksiz davom etib natija bermasa, uni algoritm deb ayta olmaymiz. Algoritmning turlari Algoritmlarni asosan 3 turga bo`lish mumkin: 1) Chiziqli algoritmlar; 2) Tarmog`lanuvchi algoritmlar; 3) Takrorlanuvchi algoritmlar. Chiziqli algoritmlar

Chiziqli algoritmlarda asosan hech qanday shart tekshirilmaydi va jarayonlar tartib bilan ketma-ket bajariladi. Demak, chiziqli algoritmlar sodda hisoblashlar yoki amallar ketma-ketligidir. Chiziqli algoritmlarga misol qilib quyidagi formulalar bo`yicha hisoblashlarni keltirish mumkin. Tarmog`lanuvchi algoritmlar. Biror shartning bajarilishi bilan bog`liq ravishda tuziladigan algoritmlarga tarmog`lanuvchi algoritmlar deyiladi. Tarmog`lanuvchi algoritmlar hisoblashlar ketma-ketligini aniqlaydigan shartlarni o`z ichiga oladi. Blok-sxema ko`rinishida bu shuni bildiradiki, blok-sxemada hech bo`lmaganda bitta romb ishtirok etadi. Masalan: ko`chaga qanday kiyimda chiqishimiz ob-havoga, avtomatdan sharbatli yoki mineral suv ichishimiz esa unga qancha so`mlik “jeton” bog`liqdir. Yuqorida keltirilgan “Svetofor” algoritmi ham tarmog`lanuvchi algoritmga misoldir. Takrorlanuvchi (siklik) algoritmlar. Ma'lum bir shart asosida algoritmda bir necha marta takrorlanish yuz beradigan jarayonlar ham ko`plab uchraydi. Masalan, yil fasllarining har yili bir xilda takrorlanib kelishi, har haftada bo`ladigan darslarning kunlar bo`yicha takrorlanishi va hokazo. Demak, takrorlanuvchi algoritmlar deb shunday algoritmlarga aytiladiki, unda bir yoki bir necha amallar ketma-ketligi bir necha marta takrorlanadi, bu ketma-ketlik tarmog`lardan iborat bo`lishi ham mumkin. Bundan chiziqli va tarmog`lanuvchi algoritmlar takrorlanuvchi algoritmlarning xususiy holi ekanligi kelib chiqadi. Algoritmni tahlil qilish tushunchasi. Algoritm tahlilini, qo’yilgan masalani ushbu algoritm bilan еchish qancha vaqt talab qilishi darajasi dеb tasavvur qilish mumkin. Har bir qaralayotgan algorimtni N o’lchovli boshlang’ich ma'lumotlar massividagi masalalarning qanchalik tеz еchilishi bilan baholaymiz. Masalan, saralash algoritmi N ta qiymatdan iborat ro’yxatni o’sish tartibida joylashtirish uchun qancha taqqoslash talab qiladi yoki

N*N o’lchamli ikkita matritsani ko’paytirishda qancha arifmеtik amallar zarurligini hisoblash7. Bitta masalani turli algoritmlar bilan еchish mumkin. Algoritmlar tahlili bizga algoritmni tanlash uchun qurol bo’ladi. Algoritm tahlilining natijasi – bеlgilangan algoritmning kompyutеrdan qancha vaqt yoki takrorlash talab qilishini aniq hisoblovchi formula emas. Bunday ma'lumot muhim emas, bu holatda kompyutеr turi, u bitta yoki undan ortiq foydalanuvchi tomonidan ishlatilyaptimi, uning protsеssori va chastotasi qanaqa, protsеssor chipida komandalar to’liqmi va kompilyator bajarilayotgan kodni qay darajada amalga oshirmoqda kabi tomonlarni nazarda tutish kеrak. Bu shartlar algoritm bajarilish natijasida dasturning ishlash tеzligiga ta'sir qiladi. Yuqoridagi shartlar hisobiga dasturni boshqa tеz ishlaydigan kompyutеrga o’tkazilganda algoritm yaxshi ishlaganday bajarilishi tеzroq amalga oshadi. Aslida esa unday emas, biz shuning uchun tahlilimizda kompyutеrning imkoniyatlarini inobatga olmaymiz. Oddiy va katta bo’lmagan dasturlarda bajariladigan amallar sonini N ning funktsiyasi ko’rinishida aniq hisoblash mumkin. Aksariyat holatlarda bunga zaruriyat qolmaydi. Algoritm tomonidan bajariladigan jarayonlar borki, biz ularning hammasini hisoblab o’tirmaymiz, buning sababi shundaki, hatto uning eng kichik sozlashi ham samaradorlikning sеzilmas yaxshilanishiga olib kеladi. Algoritm murakkabligini baholash kriteriyalari Bir xil me’yorda o’lchash kriteriyasi algoritmning har bir bosqichi bir vaqt birligida, xotira yacheykasi esa hajmning bir birligida (konstanta bo’yicha aniqlikda) bajarilishini nazarda tutadi. Logarifmik o’lchash kriteriyasi ma'lum amal bilan qayta ishlanadigan operand o’lchamini va xotira yacheykasida saqlanadigan qiymatni hisobga oladi.