Urganch davlat universiteti axborot texnologiyalari kafedrasi

1.2.7. Nima tanlash kerak? 

Murakkablikning minimal tartibi  –  bu algoritmlarni tanlashning  yagona  kriteriyasi emas 

va  hamma  vaqt  ham  ulardan  eng  samaralisi  zarur  emas.  Istalgan holda  tanlov  ongli  bo‘lganligi 

zarur.  Oddatda,  effektiv  algoritmlar  baholashda  katta  konstantalarga  ega  va  faqat  masalaning 

katta  o‘lchamlarida  yaxshi  natijalar  beradilar.  Shuning  uchun  o‘lchamlari  boyicha  uncha  katta 

bo‘lmagan  masalalar  uchun  noeffektiv  algoritmlar  effektivlariga  qaraganda  tezroq  bo‘lishi 

mumkin. Odatda, eng effektiv algoritmlar murakkab va ularni amalga oshirish uchun noeffektiv, 

biroq  oddiy  algoritmlarga  nisbatan  ko‘proq  vaqt  talab  etadi.  Agar  dastur  bir  necha  marta 

bajarilsa, effektivlikni e’tiborga olmasa ham bo‘ladi, chunki dasturni ishlab chiqish vaqti uning 

bajarilishining  summar  vaqtidan  ortib  ketishi  mumkin.  Bundan  tashqari  qiyin  dasturni  zarur 

bo‘lganda  o‘zgartirish  ham  mushkul,  shuning  uchun  oddiy  va  “shaffof”  algoritmlardan 

foydalanish  dasturlash  vaqtini  sezilarli  darajada  kamaytiradi.  Biroq  masala  dastur  bajarilishida 

ko‘p  marta  yechilsa,  effektivlikni  e`tiborga  olish  zarur.  Yuqorida  kiritilgan  algoritm 

murakkabligi tushunchasi eng yomon holatning murakkabligi bilan bog‘langan bo‘lib, u berilgan 

o‘lchamning  barcha  holatlari  uchun  eng  ko‘p  harakat  miqdori  singari  aniqlanadi.  Ko‘plab  real 

masalalarda o‘rtacha algoritm murakkabligi zaruriy bo‘lib qoladi va u ushbu o‘lchamning barcha 

hollari bo‘yicha harakatlar sonini o‘rtachalash va baholash kabi aniqlanadi. Masalan, massivlarni 

saralash  algoritmlaridan  biri  o‘rtacha  O(nlogn),  eng  yomon  holda  esa  O(n

2

)  murakkablik 

bahosiga  ega.  Shunday  bo‘lsada  uni  boshqalarga  nisbatan  ko‘proq  ishlatadilar,  chunki  u,  eng 

yomon  hol  uchun  O(nlogn)  murakkablik  bahosiga  ega  bo‘lgan  algoritmlarga  nisbatan,  deyarli 

hamma vaqt tezroq ishlaydi.