возведение в степень по квадрату сложности времени

Question

возведение в степень по квадрату сложности времени

Я не понимаю, как возведение в степень путем возведения в квадрат приводит к умножениям O (log n).

Мне кажется, что вы в конечном итоге делаете больше, чем log n умножений (где n — размер показателя степени).

Пример:

              power(2,8)
/                       \
pow(2,4)        *          pow(2,4)
/        \                 /        \
pow(2,2) * pow(2,2)          pow(2,2) * pow(2,2)
/               \             /              \
p(2,1)*p(2,1) p(2,1)*p(2,1)  p(2,1)*p(2,1)    p(2,1)*p(2,1)

Это семь умножений, так же, как регулярное возведение в степень.

Вот 3 метода, которые я попробовал:

long pow(int base, int exp)
{
if(exp == 1)
return base;
else
return base * pow(base, exp-1);
}

long pow2(int base, int exp)
{
if(exp == 1)
return base;
else if(exp == 0)
return 1;
else
if(exp % 2 == 0)
return pow2(base * base, exp/2);
else
return base * pow2(base * base, exp/2) ;
}

long pow3(int base, int exp)
{
if(exp == 1)
return base;
int x = pow2(base,exp/2);
if(exp%2 == 0)
return x*x;
else
return base*x*x;
}

Кажется, что когда рекурсия заканчивается, выполняется то же количество умножений …

2

algorithm big-o c++

Решение

Другие решения

Вы показываете бинарное дерево, но ваша рекурсивная функция не вызывает себя дважды, только один раз, поэтому она пересекает только один путь logN.

Кроме того, рекурсия глупа (медленная, сложная, хрупкая) для этого алгоритма.
Просто зациклите биты экспоненты:

long pow(long base, int exp) {
long result = 1;
while (exp > 0) {
if (exp & 1) result *= base;
exp >>= 1;
base *= base;
}
return result;
}

2

Давайте посмотрим на ваш пример 2 ^ 8. На первом шаге вы должны вычислить 2 ^ 4. Когда у вас есть результат, просто умножьте его на себя. Вам не нужно вычислять все дерево, потому что вы уже знаете результат. Давайте посмотрим на ваше дерево примеров. В этом случае вам нужно рассчитать только самое левое дерево. Это означает только 2 ^ 4, 2 ^ 2, 2 ^ 1, а затем использовать результаты, чтобы получить 2 ^ 8.

Также ваша функция должна выглядеть примерно так:

int power(int base, int power) {
if (power == 0)
return 1;
if (power == 1)
return base;
int result = power(base, power / 2);
result *= result;
if (power % 2 == 1)
result *= base;
return result;
}

1

Источник

Accepted Answer

Вы должны учитывать только одну ветвь, так как вы сохраняете результат и не пересчитываете ветки. На самом деле выполняются только следующие умножения:

              power(2,8)
/                       \
pow(2,4)        [*]        pow(2,4)
/        \                 /        \
pow(2,2) [*] pow(2,2)        pow(2,2) * pow(2,2)
/               \             /              \
p(2,1)[*]p(2,1) p(2,1)*p(2,1)  p(2,1)*p(2,1)    p(2,1)*p(2,1)

3