Urganch davlat universiteti axborot texnologiyalari kafedrasi

 

while b.

0 

do begin 

  c;=a mod b; a;=b; b:=c 

end;

 

Sikl  tanasining  ikki  marta  bajarilgandan  keyin  sonlardan  kichigi  ikki  martadan  ko‘proq 

kamayishiga osongina ishonish mumkin, shuning uchun sikl O(loga) marta bajariladi. Kamchilik 

holati  –  bo‘lishdan  qoldiqni  hisoblash.  Ustunchdan  m-raqamli  sonlarning  birgacha  ma`lum 

bo‘linish algoritmi O(m

2

) ga murakkablikka ega , shunung uchun a b da EKUB(a,b)ni hisoblash 

O(log

3

a) murakkablikning polinominal bahosiga ega bo‘ladi. 

1.2.5. Binar algoritm 

---

Bo‘lishlarni  talab  qilmaydigan  EKUB  ni  izlashning  effektiv  algoritmini  qarab  chiqamiz. 

Uni quyidagi formulalar bilan yozish mumkin: 

  

(a) EKUB(2a,2b)=2EKUB(a,b) , 

(b1) EKUB(a,b)=EKUB(b,a) , agar a

(b2) EKUB(2a,b)=EKUB(a,b) , agar b toq son, 

(b3) EKUB(a,2b)=2EKUB(a,b) , agar a toq son,                                                   (1.1) 

(c) EKUB(a,b)=EKUB(a-b,b) , agar a>b, 

(d) EKUB(a,b)=a 

(e) EKUB(a,1)=1. 

 

(b1),(d)va (e) formulalar ma`lumdirlar. (c) formula Yevklid algoritmining “klassik  versiyasi”da 

ishlatiladi.  (a)  korrektlik  EKUBni  ko‘paytuvchilarga  yoyish  orqali  izlash  korrektligidan  kelib 

chiqadi:  agar  2-2a  va  2b  ning  umumiy  ko‘paytuvchisi  bo‘lsa,  u  holda  barcha  umumiy 

ko‘paytuvchilarni tanlashda u EKUB(2a,2b)ga ham tushadi; bunda aynan ushbu 2 EKUB(a,b)ga 

tushmaydi.  Nihoyat,(b2)  va  (b3)  formulalar:  agar  sonlarda  biri  toq  bo‘lsa,  u  holda  EKUB  ham 

toq va 2 ko‘paytuvchini tashlab yuborish boshqa sonda hech nimani o‘zgartirmaydi.  

Ushbu  formulalarni  qo‘llashning  ketma-ketligini  qarab  chiqamiz.  Avvalo  (d)  va  (e) 

chiqish  shartlarini  tekshiramiz.  Ular  ishlamasligi  aniqroq  shuning  uchun  (c)  formuladan 

boshlaymiz.  U  mumkin  bo‘lgunicha  qo‘llaymiz,  bu  2*2*2*…*2=2

k 

ko‘paytmani  darhol 

tuzmaymiz,  balki  faqat  ushbu  formulani  qo‘llash  k  miqdorini  eslab  qolamiz.  (a)  formulani 

qo‘llash  mumkin  bo‘lmay  qolganida,  uni  keyinchalik  qo‘llash  mumkinmasligini  kafolatlaydi, 

chunki (b) va (c) formulalar sonlardan bittasini toq qoldiradi. Keyin esa mumkin bo‘lganiga (b) 

formulani qo‘llaymiz. Agar ular yaroqli bo‘lmasa a va b ning har ikkala qiymatlari  –  toqdirlar. 

Unda, agar  (d)  va  (c)  chiqish  shartlari  bajarilmasa,  (c)  formulani  bir  marta qo1laymiz,  juft  a-b 

farqni  olamiz  va  yana  (b)  formulani  qo‘llab  boshlaymiz.  Nihoyat, (d)  yoki  (c)  chiqish  shartiga 

yetib  kelib,  MOD  ning  olingan  qiymati  k  marta  2  ga  ko‘paytiramiz.  (k-(a)  formulani  qo‘llash 

miqdori).  

Funksiyalarni  qo‘llash  qadamlari  miqdorini  baholaymiz,  (a)  formula  a*b  ni  to‘rt  marta, 

(b2)  va  (b3)  formulalar esa  ikki marta kamaytiradi. Shuning uchun ushbu formulalarni qo‘llash 

miqdori  log

2

ab=O(n)  dan  ko‘p  emas,  bu  yerda  n-a  va  b  ning  boshlang‘ich  qiymatlaridagi 

raqamlarning summalar miqdori. Yevklid algoritmi “klassik versiyasi”ning koeffitsiyentligining 

sababi bo‘lgan  (c)  formula  a-b  ning  juftligi  tufayli  (b2)  va  (b3) dan,  ya`ni  O(n)  martadan  katta 

bo‘lmagan  marta  qo‘llaniladi.  (b1)  formula  a  qiymatni  kamaytiruvchi  (b2)  va  (c)  formulalarga 

qaraganda  uncha  ko‘p  bo‘lmagan  marta  qo‘llaniladi.  Har  bir  qadamdagi  elementar  harakatlar 

miqdori o‘z-o‘zidan ayonki O(n) ga teng, chunki faqat juflikni tekshirish (O(1) har bir hisoblash 

sistemasining juft asosidagi), 1 konstanta bilan taqqoslash (O(1)), sonlarni taqqoslash va ayirish, 

hamda 2 konstantaga bo‘lish va ko‘paytirish (barchasi O(n)bo‘yicha) kerak. Shunday qilib, bitta 

mod  operatsiyasidan  katta  bo‘lmagan  harakatlarning  umumiy  miqdorining  bahosi  O(n

2

)ga  ega 

bo‘lamiz.