Algoritmlash p65. p65

Samaradorlik va  murakkablik
Biz turli algoritmlarning samaradorligini muhokama qilib o‘tdik. 
Algoritmni bajarilish qadami — bu Ijrochi tomonidan bitta ko‘rsat- 
maning bajarilishidir.  Bir masalani  hal  etuvchi  ikkita  algoritmdan 
kam  qadam  talab  qilinayotgani  samaraliroqdir.  Samaradorlik 
o‘lchovi  — bu  bor-yo‘g‘i  qadamlar  sonidir.
Lekin  chuqurroq  e’tibor  berib  qarasak,  bu  ta ’rifdagi  mujmal 
tomonlarni aniqlaymiz.  Ba’zan avval uchragan algoritmlardagidan 
ko‘ra  vaziyat  murakkabroq bo ‘ladi.  Hozircha bu  masala  chuqur- 
lashib  o ‘tirmaymiz  va  chuqurroq  bilim   to ‘plam aguncha  uni 
muhokamasini  keyinga  qoldiramiz.
Algoritmlar  murakkabligi  bilan  ham  farqlanishi  mumkin. 
Algoritmning  murakkabligini  uning  matnidagi  satrlar  soni  bilan 
o‘lchaymiz.  Shu  bilan  birga  quyidagi  ikki  satrni  bir  tuzilmaning 
ikki  qismi bo‘lgani  uchun bittaga  hisoblaymiz:
TAKRORLANSIN   MARTA 
TAMOM
M ana,  masalan,  quyidagi  algoritmda:
1  ni  qo‘sh
TAKRORLANSIN 6  MARTA
66

---

2  ga ko‘paytir 
1  ni  qo‘sh 
TAMOM
faqat  4  ta  satr:
1  ni  qo‘sh
TAKRORLANSIN 6  MARTA 
TAMOM
2  ga ko‘paytir 
1  ni  qo‘sh
bor.  Bu  uning  murakkabligi  4  ekanligini bildiradi.
Shuni  aytib  o ‘tish joizki,  II  bobdagi barcha  algoritmlarning 
barchasini  murakkabligi  va  samaradorligi  o ‘zaro  tengdir.  Ma- 
salan,  b o ‘ri,  echki  va  karam ni  daryodan  o ‘tkazish  algoritmi 
ham  7  satrdan  iborat  ham  u  7  qadamda  bajariladi.  Bu  kabilar 
shu  bobning  barcha  algoritmlari  uchun  ham   o ‘rinli.  Bizda  shu 
vaqtgacha algoritm matnidagi satrlarini qisqartirish uchun vosita 
yo‘q  edi.  Bizdan  algoritm  ko‘rsatmasini  bajarish  talab  etilgan 
b o ‘lsa,  biz  ko‘rsatmani  algoritm  matniga joylashtirishga majbur 
edik.  Masalan,  Oshiruvchi  tom onidan  17  sonini  hosil  qilish 
algoritmiga  qarang:  17  m arta  bajarilish  algoritm  matnining  17 
satriga  aylandi.
Endi  esa bizni  kerakli vositamiz bor:  bu  TAKRORLANSIN  - 
MARTA tuzilmasi.  Shuning uchun Oshiruvchi tomonidan 17 sonini 
hosil  qilish  algoritmi  3  satrdan  iborat  bo‘ladi  (eslatamiz:  tuzilma 
1  ta  satr  deb  hisoblanadi):
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 4.6 - 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  b o ‘lishidan  qat’iy  nazar,  5  ga  teng  bo‘ladi!
67

---