目前，我最大的努力导致了复杂度为O（日志[N] ^ 2）：

Currently, my best effort has resulted in complexity 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 感谢您funkymushroom帮助我与我的英语不好：）

P.S Thank you funkymushroom for helping me with my bad English :)

推荐答案

背后实施这一操作对数时间的想法是使用下面的（数学），等价（这里N / 2表示整数除法）：

The idea behind implementing this operation in logarithmic time is to use the following (mathematical) equivalences (here n/2 denotes integer division):

X ^ 0 = 1

x^0 = 1

X ^ N =（X N / 2 ） 2 ，如果n％2 == 0

x^n = (xn/2)2, if n % 2 == 0

X ^ N = X *（X N / 2 ） 2 ，如果n％2 == 1

x^n = x*(xn/2)2, if n % 2 == 1

这可以很容易地递归根据实现的：

This can easily be implemented recursively according to:

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）被减半在递归的每个步骤。

An implementation such as this will yield a O[log(n)] complexity since the input (the variable n) is halved in each step of the recursion.