Urganch davlat universiteti axborot texnologiyalari kafedrasi

1.2.3. Murakkablikning o‘sish xarakteri 

Faraz  qilaylik,  qandaydir  masala  mavjud bo‘lsin  va  uning  yechimining  T

1

(n)=  θ(n

2

)  va 

T

2

(n)=  θ(n)  baholarga  ega  ikkita  dastur  mavjud bo‘lsin.  Ayonki,T

2

(n)=  θ(T

1

(n))  lar  ya’ni  T

2

(n) 

tartib  T

1

(n)  tartibga  nisbatan  kichik.  Ushbu  baholarda  turli  xil  konstantalar  bo‘lishi  mumkin. 

Faraz qilaylik, T

1

(n)=n

2

 T

2

(n)=100*n  ya’ni T

1

(n)|T

2

(n)=n|100 bo‘lsin.  N<100 da birinchi dastur 

ikkinchiga  qaraganda  tezroq  biroq 10

6

  tartibidagi  n  da 10 000 marta  sekinroq  ishlaydi.  Bunday 

o‘lchamdagi masalani yechish uchun ikkinchi dastur yaxshi ekanligi o‘z-o‘zidan ayon. 

Kichik  darajali  murakkablikni  dasturni  tanlashning  boshqa  sababi  maqbul  vaqt  ichida 

yechiladigan  masala  ekzemplyarlarning  maksimal  o‘lchami  bilan  bog‘langan.  ”Maqbul  vaqt” 

tushunchasi  bir  ma’noli  emas,  shunday  bo‘lsada,  istalgan  konkret  masala  uchun  u  yechilishi 

mumkin  bo‘lgan  vaqt  oralig‘ini  belgilash  mumkin.  Mana  shu  yerdan  u  yoki  bu  algoritm 

yordamida  yechiladigan  hollarning  maksimal  o‘lchamini  aniqlaydilar.  Algoritm  murakkablik 

darajasi qancha kichik bo‘lsa, yechiladigan masalalar maksimal o‘lchami shuncha katta bo‘lishi 

o‘z-o‘zidan  ayon.  Katta  murakkablik  darajalarida  maksimal  o‘lchamlar  kompyuterlarning 

tezkorligi  o‘sishi  bilan  kam  oshishi  ham  zarur.  Illiyustratsiya  uchun  2  kompyuter  mavjud  deb 

taxmin qilamiz. Bittasi 1 sekund ichida 10

6

 elementar harakatni 2 chisi esa 10

8

 ni bajaradi, ya’ni 

100  marta  tezroq  ishlaydi.  Maqbul  vaqtni  10  s  deb  olamiz.  Ushbu  murakkablik  darajasidagi 

dasturlarni  bajarishda  kompyuterlarda  olinishi  mumkin  bo‘lgan  masalaning  maksimal 

o‘lchamlarini M

1

  va M

2 

orqali belgilaymiz.  O‘lchamlarning va ularning ortish xarakteri (M

2

|M

1

 

nisbat) larning tezkorlik o‘sishiga bog‘likligi 1.1-jadvalda keltirilgan. 

1.1 -jadval. Murakkablik darajasi va masalaning maksimal o‘lchamlari. 

Murakkab tartib 

M

1 

M

2 

M

2

/M

1 

n 

10

7 

10

9 

100 

n

2 

-3000 

-30000 

-10 

n

3 

-220 

1000 

-5 

2

n 

21 

27 

-1,3 

n! 

10 

12 

1,2 

---

 

Ko‘rinib turibdiki, ishni 100 marta tezlashtirish  yechimi n darajadagi murakkablikka ega 

bo‘lgan masalaning maksimal o‘lchamini ham 100 marta, murakkabligi N

2 

bo‘lgan yechimli 

masala uchun esa 10 marta oshirishga imkon beradi. Katta darajada (2

n

 va n!) murakkablikda 

yechiladigan masalalar o‘lchamlari sezilarli o‘smaydi.  

Algoritmlar  va  ularning  n

k

  darajadagi,  bu  yerda  k-natural  son,  murakkabliklari  –  polenominal, 

algoritmlar va ularning k

n

 darajadagi murakkabliklari – eksponentsial deyiladi. 

1.1-jadvaldan  ko‘rinib  turibdiki  eksponentsial  algoritmlar  o‘lchamlari  bir  necha  o‘nga  teng 

bo‘lgan  masalalarni  yechishdayoq  juda  uzoq  ishlaydi.  Ta’kidlash  kerakki  ishni  100  marta 

tezlashtirish  –  ko‘plab  amaliy  masalalarda  bu  juda  ko‘p.  Biroq,  agar  to‘liq  real  o‘lchamli 

ma’lumotlarning  eksponentsial  algoritmini  bajarish  uchun  minglab  va  millionlab  yillar  kerak 

bo‘lsa,  juda  kamdir.  Yana  bir  tushunchani  qarab  chiqamiz.  Oddiylik  va  faktorlash  ta’rifi 

algoritmlarining  murakkabligini  baholashda  o‘lcham  sifatida  n  sonining  ikkilangan 

taqdimotining  log  n  uzunligini  emas  balki  uning  o‘zini  olgandik.  Shunday  tarzda  bir  vaqtning 

o‘zida O(n

1

) bo‘lgan murakkablik  

  bahosi, ya’ni polinominal singari olingan. 

Kiruvchi  son  qiymatlari  terminlarida  algoritmlarining  murakkabligi  ikkilangan  taqdimoti 

o‘lchamlarini emas , balki polinominal bahoga ega bo‘lsa ular psevdopotensiallar deyiladi.