Urganch davlat universiteti axborot texnologiyalari kafedrasi

1.2.6. Masala murakkabligi tushunchasi. 

Masala turli  xil murakkablikdagi  yechish algoritmlariga ega bo‘lishi mumkin.  Noformal 

jihatdan  masalaning  murakkabligi  tushunchasi  sifatida  uning  yechimi  murakkabliklardan  eng 

kichigi tushuniladi. 

---

Masala  G(n)  darajadagi  murakkablikka  ega,  agarda  uning  G(n)  murakkablikdagi  yechim 

algoritmi mavjud bo‘lsa va O(G(n)) murakkablikdagi algoritmlar mavjud bo‘lmasa. 

Ikki  natural  sonning  EKUBini  hisoblash  masalasini  qaraymiz  (oldingi  bo‘limlarni 

qarang).  O‘lcham  n  sifatida  sonlarning  dastlabki  qiymatlaridagi  raqamlarning  summalar 

miqdorini  qabul  qilamiz.  Bunda  Yevklid  algoritmining  zamonaviy  versiyasi  O(n

3

) 

murakkablikka,  binar  algoritm  esa  -  O(n

2

)  murakkablikka  ega  bo‘ladi.  Shuning  uchun  masala 

murakkabligi  ustidan  O(n

2

)  bahoga  ega  bo‘ladi.  Biroq  bu  bilan  kichik  baholi  algoritm  yo‘q 

degani emas.  1.2-masalada o‘lchash sifatida N  sonni qabul qilamiz  va  har bir  arifmetik  harakat 

O(1)  “bo‘ladi”  deb  hisoblaymiz.  Masalada  N

2 

sonni  chiqarish  kerak,  shuning  uchun  uni 

yechimining  hohlagan  algoritmining  murakkabligi  pastdan

2

)  bahoga  ega.  Biroq  taklif 

qilingan  algoritm 

2

)  murakkablik  bahosiga  ega,  ya’ni  uni  ushbu  masalaning  murakkablik 

bahosi  deb  hisoblash  mumkin.  Odatda,  masala  murakkabligini,  algoritmlar  murakkabligini 

baholashdan  ko‘ra  ancha  qiyindir.  Murakkabligi  hozirgacha  ham  noma’lum  bo‘lgan  masalalar 

juda ko‘p, masalan, yuqorida keltirilgan natural sonning oddiyligi va yoyilishi haqidagi masala.