非递归求幂

发表于: 2015-03-01分类于:算法

求解一个数的 N 次幂,通常使用 pow 函数。要求 a^N,最最显而易见的方法是用 N 个 a 连续做乘法,幸运的是,我们有更快的算法。

最常见的一种方法是采用递归的求解方式,如下:

递归解法:

long int pow(int x, unsigned int N){
    if (N == 0){
        return 1;
    }
    if (N == 1){
        return x;
    }
    if (N & 1 == 0){
        return pow(x * x, N / 2);
    } else {
        return pow(x * x, N / 2) * x;
    }
}

这个算法的复杂度无疑是 O(logN) 的。

下面不采用递归来求解:

非递归解法:

long int pow(int x, unsigned int N){
    int ans, n;
    ans = 1;
    n = x;
    while (N != 0){
        if (N & 1 == 1){
            ans = ans * n;
        }
        n = n * n;
        N >> 1;
    }
    return ans;
}

下面来分析一下以上算法的原理:

先举个例子,假如希望求 5^62,也就是 5 的 62 次方。为了算法高效,一个原则就是不做重复的计算。

5^62 = 5^(32+16+8+4+2) = 5^32 * 5^16 * 5^8 * 5^4 * 5^2

不管指数是多少,都可以将其分解为 2 的倍数的和,因为任何整数都能够写成 2 进制的形式,比如 62 = 00111110B

以上算法中,随着迭代 n 会变成 x, x^2, x^4, x^8,…,我们只需要在合适的时候让它和 ans 相乘即可。合适的时刻就是 N 的二进制表示的相应位上为 1 的时候,这里使用了右移,只需要判断最低位是不是 1 就好了。

这个算法也是 O(logN) 的,但是没有使用递归。