我正在寻找一种计算数字功效的算法.(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);
}

PS谢谢你funkymushroom帮助我的英语不好:)

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)减半.