Urganch davlat universiteti axborot texnologiyalari kafedrasi

Summalar qoidasi: Algoritmni umumiy harakatlarga ega bo‘lmagan qismlarga ajratish mumkin 

deb taxmin qilamiz. Agar algoritm bir qismining murakkabligi θ(f(n)), boshqasiniki esa θ (g(n)) 

bo‘lsa, u holda ularning summaviy murakkabligi θ(max{f(n),g(n)}) 

Ko‘paytmalar  qoidasi:  Agar  algoritm  qismning  murakkabligi  θ(f(n))  bo‘lib,  va  θ(g(n))  marta 

bajarilsa,  u  holda  bajarilishi  umumiy  murakkablik  θ(f(n))xg(n))  ga  teng  bo‘ladi.  Masalan: 

oddiylikni aniqlash haqidagi masalada o‘lcham n sifatida n sonning o‘zini olamiz. Agar n-oddiy 

son bo‘lsa, isPrime funksiyasidagi sikl θ (√n) marta bajariladi. Siklning har bir takrorlanishi o(1) 

harakatni talab etadi, shuning uchun ushbu algoritmning murakkabligi (tanlangan “n” “o‘lcham” 

da) θ ( √n) yoki θ (n

2 

) bo‘ladi. Biroq, haqiqatda o‘lcham bo‘lib son emas, balki uning ikkilangan 

taqdimoti  (uzunligi)ning  bitlar  soni  hisoblanadi.  n  sonini  taqdim  qilish  uchun  m=[log

2

n]+1  bit 

ya’ni  n=  θ(2

m

)  zarur  va  keltirilgan  algoritmning  murakkabligi  haqiqatan  ham  θ  (2

m/2

)  bo‘ladi. 

Analogik tarzda yuqorida keltirilgan faktorlash algoritmida k<=t takrorlanish shartli sikl oddiy n 

da [√  n]  marta  bajariladi  ya’ni  ushbu  algoritm  murakkabligi  ham  θ(n

1/2

)  yoki  haqiqatan  θ(2

m/2

) 

bahoga  ega  bo‘ladi.  Oddiylikni  va  faktorlashni  aniqlash  masalalari  ochiq  kalitli  shifrlashda 

asosiylardan  biri  hisoblanadi.  Kalitlar  o‘lchamlari  yuzlab  va  minglab  bitlar  bilan  hisoblanadi. 

Shuning uchun oddiylikni va faktorlashni tekshirishning keltirilgan algoritmlari to‘g‘ri kelmaydi. 

Ushbu  masalalarni  yechishda  prinsipial  jihatdan  boshqa  algoritmlar  qo‘llanilmoqda  (masalan 

[22] ga qarang)