Ajiniyoz nomidagi nukus davlat pedagogika

7.2. Kiruvchi berilganlar sinfi 
Algoritmlarning tahlilida kiruvchi ma’lumotlarning roli yuqori, chunki algoritm harakatlarining 
ketma-ketligi  kiruvchi  ma’lumotlar  bilan  belgilanadi.  Masalan, 
N
  ta  elementdan  tashkil  topgan 
rо‘yxatning eng katta elementini topish uchun quyidagi algoritmdan foydalanish mumkin: 

---

largest = list   [l] 
for i = 2 to N do 
if   (list   [i]   > largest)  then 
 largest = list[i] 
end if  
end for 
Agar  rо‘yxat  kamayish  tartibida  bо‘lsa,  u  holda  sikl  boshlanishidan  avval  bitta 
о‘zlashtirish  bajariladi,  sikl  tanasida  esa  о‘zlashtirish  bо‘lmaydi.  Agar  rо’yxat  о‘sish  tartibida 
bо‘lsa, u holda 
N
 ta о‘zlashtirish bajariladi (sikl boshlanishidan avval bitta va 
N-
1 ta siklda). Biz 
tahlil  qilish  davomida  kiruvchi  qiymatlar  tо‘plamining  turli  imkoniyatlarini  kо‘rib  chiqishimiz 
kerak,  agar  bitta  tо‘plam  bilan  chegaralansak,  bu  yechim  eng  tez  (yoki  eng  sekin)  bо‘lgan 
tо‘plam  bо‘lib  chiqishi  mumkin.  Natijada  biz  algoritm  haqidagi  yolg‘on  tasavvurga  ega 
bо‘lamiz. Buning о‘rniga kiruvchi tо‘plamlar turining barchasini kо‘rib chiqamiz.  
Biz  kiruvchi  tо‘plamlarni  har  bir  tо‘plamdagi  algoritm  holatiga  bog‘liq  holda  sinflarga 
bо‘lib  chiqamiz.  Bunday  bо‘linish  kо‘rib  chiqilayotgan  tо‘plamlar  miqdorini  kamaytirish 
imkonini  beradi.  Masalan,  10  ta  sondan  iborat  rо‘yxat  uchun  eng  katta  elementni  topish 
algoritmini  qо‘llaymiz.  Birinchi  soni  eng  katta  bо‘lgan  362 880  kiruvchi  tо‘plamlar  mavjud, 
ularni  bitta  sinfga  joylashtirish  mumkin.  Agar  qiymati  bо‘yicha  eng  katta  son  ikkinchi  о‘rinda 
turgan  bо‘lsa,  u  holda  algoritm  ikkita  о‘zlashtirishni  amalga  oshiradi.  Eng  kata  son  ikkinchi 
о‘rinda turgan tо‘plam 362 880. Ularni boshqa sinfga kiritish mumkin. 1 dan 
N 
gacha  bо‘lgan 
sonlar  orasida  eng  katta  sonning  о‘zgarish  holida  о‘zlashtirishlar  sonining  qanday  о‘zgarishini 
kо‘rishimiz mumkin
. 
 
Shunday qilib, barcha kiruvchi tо‘plamlarni bajarilgan о‘zlashtirishlar soni bо‘yicha 
N
 ta 
turli sinfga bо‘lish kerak. Kо‘rib turganingizdek, har bir sinfda joylashgan tо‘plamlarni birma-bir 
yozish yoki yozib olish shart emas. Faqatgina har bir tо’plamdagi sinflar miqdori va ish hajmini 
bilish yetarli. 
Kiruvchi  berilganlarning  mumkin  bо‘lgan  tо‘plami 
N
  kattalashganda  judayam  katta 
bо‘lishi mumkin.
 
Masalan, 10 ta turli soni rо‘yxatda 3 628 800 usulda joylashtirish mumkin. Bu 
usullarning barchasini kо‘rib chiqishning imkoni yо‘q. Biz buning о‘rniga algoritm bajarilishiga 
kо‘ra  rо‘yxatni  sinflarga  bо‘lamiz.  Yuqorida  kо‘rsatilgan  algoritm  uchun  bо‘linish  eng  katta 
qiymatning joylashishi о‘rniga asoslanadi. Natijada 10 ta turli sinf hosil bо‘ladi. Boshqa algoritm 
uchun,  masalan,  eng  katta  va  eng  kichik  sonni  topish  algoritmida  bо’linish  eng  katta  va  eng 
kichik  sonning  joylashuviga  asoslanadi.  Bunday  bо‘linishda  90  ta  sinf  bо‘ladi.  Sinflarni  ajratib 
bо‘lgach, har bir sinfdan bitta tо‘plamda algoritm  holatini kо‘rish  mumkin.  Agar sinflar tо’g’ri 

---

tanlangan bо‘lsa, u holda bir sinfdagi kiruvchi berilganlar tо‘plamida algoritm bir xil miqdordagi 
amallarni bajaradi, boshqa sinfning tо‘plamlari uchun esa amallar miqdori boshqacha bо‘ladi.