Я ищу алгоритм, который рассчитывает мощность числа. (x ^ y), x и y являются целыми числами. Это должно быть сложности O (log [n]))

Question

В настоящее время мои лучшие усилия привели к сложности O (log [n] ^ 2):

int power(x,n)
{
  int mult=1, temp=x, i=1, j=1;
  while (n>1)
  {
    mult=mult*x;
    x=temp;
    for (i=1;i<=log[n];i++)
    {
      x=x*x;
      j=j*2;
    }
    n=n-j;
    i=1;
    j=1;
  }
  if (n==1)
    return (mult*temp);
  return (mult);
}

P.S Спасибо, фанкишум, за то, что помог мне с моим плохим английским:)

Answer 1

Идея реализации этой операции в логарифмическом времени заключается в использовании следующих (математических) эквивалентностей (здесь n / 2 обозначает целочисленное деление):

x ^ 0 = 1

x ^ n = (x ^{n / 2} ) ² , если n% 2 == 0

x ^ n = x * (x ^{n/ 2} ) ² , если n% 2 == 1

Это может быть легко реализовано рекурсивно согласно:

int power(int x, int n) {
    if (n == 0) {
        return 1;
    } else {
        int r = power(x, n / 2);
        if (n % 2 == 0) {
            return r * r;
        } else {
            return x * r * r;
        }
    }
}

Реализациятакой как это приведет к сложности O [log (n)], поскольку вход (переменная n) уменьшается вдвое на каждом этапе рекурсии.

Answer 2

Вам нужно использовать повторный квадрат. Проверьте это