幂次方的四种快速取法（不使用pow函数）

Pow(x, n)

方法一：暴力法
方法二：递归快速幂算法
方法三：迭代快速幂算法
方法四：位运算法

方法一：暴力法

思路

只需模拟将 x 相乘 n 次的过程。

如果 $n < 0$，我们可以直接用 $\dfrac{1}{x}$, $-n$ 来替换 $x , n$ 以保证 $n \ge 0$。该限制可以简化我们的进一步讨论。

但我们需要注意极端情况，尤其是负整数和正整数的不同范围限制。

算法

我们可以用一个简单的循环来计算结果。

class Solution {

public:

    double myPow(double x, int n) {

        long long N = n;

        if (N < 0) {

            x = 1 / x;

            N = -N;

        }

        double ans = 1;

        for (long long i = 0; i < N; i++)

            ans = ans * x;

        return ans;

    }

};

复杂度分析

时间复杂度：$O(n)$。我们将 x 相乘 n 次。
空间复杂度：$O(1)$。我们需要一个变量来存储 x 的最终结果。

方法二：递归快速幂算法

class Solution {

public:

    double fastPow(double x, long long n) {

        if (n == 0) {

            return 1.0;

        }

        double half = fastPow(x, n / 2);

        if (n % 2 == 0) {

            return half * half;

        } else {

            return half * half * x;

        }

    }

    double myPow(double x, int n) {

        long long N = n;

        if (N < 0) {

            x = 1 / x;

            N = -N;

        }

        return fastPow(x, N);

    }

};

复杂度分析

时间复杂度：O(log(n))O(log(n))。每次我们应用公式$ (x ^ n) ^ 2 = x ^ {2 * n}$，$n$ 就减少一半。因此，我们最多需要 $O(log(n))$次计算来得到结果。
空间复杂度：$O(log(n))$。每次计算，我们都需要存储 $x ^ {n / 2}$ 的结果。我们需要计算 $O(log(n))$次，因此空间复杂度为 $O(log(n))$。

方法三：迭代快速幂算法

递归或迭代的快速幂实际上是实现同一目标的不同方式。

class Solution {

public:

    double myPow(double x, int n) {

        long long N = n;

        if (N < 0) {

            x = 1 / x;

            N = -N;

        }

        double ans = 1;

        double current_product = x;

        for (long long i = N; i ; i /= 2) {

            if ((i % 2) == 1) {

                ans = ans * current_product;

            }

            current_product = current_product * current_product;

        }

        return ans;

    }

};

复杂度分析

时间复杂度：$O(log(n))$。对于 n 的每个二进制位，我们最多只能乘一次。所以总的时间复杂度为 $O(log(n))$。
空间复杂度：$O(1)$。我们只需要两个变量来存储 x 的当前乘积和最终结果。

位运算实现pow(x,n)

根据暴力法的思路来看特别简单，但通过位运算呢？

位运算技巧

我举个例子吧，例如 n = 13，则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:

$m^{1101} = m^{0001} * m^{0100} * m^{1000}$。

我们可以通过 & 1和 >>1 来逐位读取 1101，为1时将该位代表的乘数累乘到最终结果。直接看代码吧，反而容易理解：

int pow(int n){

    int sum = 1;

    int tmp = m;

    while(n != 0){

        if(n & 1 == 1){

            sum *= tmp;

        }

        tmp *= tmp;

        n = n >> 1;

    }

    return sum;

}

时间复杂度近为 $O(logn)$，而且看起来很牛逼

巴特西

幂次方的四种快速取法（不使用pow函数）

方法一：暴力法

方法二：递归快速幂算法

方法三：迭代快速幂算法

位运算实现pow(x,n)

最新文章

热门文章