Я реализовал эту функцию power(), которая принимает два аргумента a и b и вычисляет a b.
typedef long long int LL;
LL power(int a,int b)
{
int i = 1;
LL pow = 1;
for( ; i <= b ; ++i )
pow *= a;
return pow;
}
Учитывая: a b попадает в диапазон long long int.
Проблема: Как уменьшить временную сложность моего алгоритма?
Экспоненциальность по квадрату.
Нерекурсивная реализация
LL power(int a, int b)
{
LL pow = 1;
while ( b )
{
if ( b & 1 )
{
pow = pow * a;
--b;
}
a = a*a;
b = b/2;
}
return pow;
}
Для этого алгоритма требуются log 2 b squarings и не более log 2 b.
Время работы O (log b)
Используйте Экспоненциальность возведения в квадрат
Я бы предложил: используйте функцию pow(), если вам действительно нужна более быстрая функция (с длинным двойным) или подумайте о своей домашней работе для себя.
Для произвольной точности: см. раздел GMP lib http://gmplib.org/manual/Integer-Exponentiation.html#Integer-Exponentiation
Экспоненциация по квадрату не дает минимального числа умножений во всех случаях. Ищите "цепи добавок", "цепи Брауэра", "цепи Хансена" и "гипотезу Шольца".
Используйте возведение в степень по квадратам. То есть, если нам нужно a ^ b, мы проверяем, является ли b четным, если b четно, мы находим (a^2)^(b/2), иначе находим a*((a^2)^(b/2)). Это может быть не лучший алгоритм, но он лучше, чем линейный алгоритм.
int Power(int a, int b)
{
if (b>0)
{
if (b==0)
return 1;
if (a==0)
return 0;
if (b%2==0) {
return Power(a*a, b/2);
}
else if (b%2==1)
{
return a*Power(a*a,b/2);
}
}
return 0;
}
Вот рекурсивная реализация кода Java для 2 до степени n с ошибкой O (log n) с использованием Экспоненциальное возведение в квадрат
int ans=1;
public int myTwoPower(int n){
if(n<=0)
return 1;
if(n%2 !=0){
return myTwoPower(n-1)*2;
}
else{
ans = myTwoPower(n/2);
return ans * ans;
}
}
