求某数n次方的算法（高效）

该算法求某个数的n次方的时间复杂度只有logN,我们平时使用的循环求时间复杂度为o(n)

int power(int x,int n)
{
    int m=0;
    m=n;
    int t=1;
    while(m>0)
    {
        m/=2;
        t*=2;
    }
    m=n;
    int y=1;
    while(t>1)
    {
        t/=2;
        y*=y;

        if (m>=t)
        {
                y*=x;
                m-=t;
        }
    }
    return y;
}

原理

一般的对于 a ^{(2x + b)} = a^2x * a ^b

所以就有

(b = 0时 ) : a ^{2x + b} = (a^x)²     ;

(b = 1时): a ^{2x + b} = (a ^x)² * a ;