Sonni ikkilik darajaga oshirish

“The most fundamental problem in software development is complexity. There is only one basic way of dealing with complexity: divide and conquer “— Bjarne Stroustrup

Bugungi darsimiz aslida Sonlar nazariyasi bo’limiga kirmasa ham lekin bu mavzu juda ko’p ishlatilgani va keyingi darslarda kerak bo’lgani uchun unga to’xtalib o’tishga qaror qildik.

Sonning biror darajaga ko’tarish uchun uni o’ziga shuncha marta ko’paytirish kerak bo’ladi. Bu oddiy algoritm murakkabligi: O(n) (n — daraja).

Ikkilik darajaga oshirish yordamida sonni butun darajaga oshirishni O(logn) murakkablikkacha tezlashtirish mumkin.

Ikkilik darajaga oshirish algoritmi g’oyasi. pow(a, n)

  1. n = 0 holatda javob birga teng.
  2. n toq bo’lgan holatda javob a ni pow(a, n/2) ning kvadratiga ko’paytirilganiga teng. (butun son)
  3. juft bo’lganda javob pow(a, n/2) ni kvadratiga teng.

Yuqoridan ko’rinib turibdiki biz har bir qadamimizda n ni ikki baravarga kamaytirib boryapmiz. Aynan, shu narsa algoritm tez ishlashiga xizmat qiladi.

Yechimga o’tishdan oldin, albatta, uni o’zingiz implementatsiya qilishga harakat qilib ko’ring!

Ikkilik darajaga oshirish algoritmi implementatsiyasi

Algoritm g’oyasidan ko’rinib turibdiki implementatsiyamiz rekursiv ko’rinishga ega bo’ladi.

Lekin, sonning darajasi juda tez o’sganligi sababli javobni 10⁹+7 ga qoldig’ini hisoblab ketsak ham bo’ladi.

Birinchi yechimga ozgina o’zgartirish kiritish orqali uni manfiy daraja (n < 0) va haqiqiy son bo’lgan holatga moslasak bo’ladi.

Maqolani foydali deb hisoblasangiz uni do’stlaringizga ham ulashing!

Manba: @AlgorithmUz telegram kanali

YouTube kanalimiz: Algorithms Uzbekistan