【面试经典150 | 数学】Pow(x, n)

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【快速幂】

题目来源

50. Pow(x, n)

题目解读

计算一个数的整数次幂。

解题思路

计算一个数的整数次幂有朴素的方法和二分的方法，朴素的方法就是一个一个的乘起来，时间复杂度为 $O(n)$，$n$ 指的是幂指数。接下来要介绍的是二分法，即快速幂，有递归和迭代两种解法。建议读者掌握快速幂的方法，该方法是一些题目计算的一个重要工具。

方法一：快速幂-递归

写递归代码的一个重要思想，坚信自己写的递归就是对的，可以直接调用。用快速幂求解一个数的整数次幂是一种二分的递归，比如我们要计算 $x^n$ 时：

• 我们可以先递归的计算 $y=x^{\lfloor n/2\rfloor }$；
• 如果 n 是偶数，那么 $x^n=y^2$；如果 $n$ 是奇数，那么 $x^n=y^2\times x$;
• 递归的边界（递归出口）为 n = 0，因为任意数的 0 次方均为 1。

实现代码

class Solution {
public:
    double quickMul(double x, long long N) {
        if (N == 0) return 1.0;
        double y = quickMul(x, N/2);
        return N & 1 ? y * y * x : y * y;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};

复杂度分析

时间复杂度：$O(logn)$，$n$ 为幂指数。因为每次递归都会使指数减少一半，因此递归的层数为 $O(logn)$，时间复杂度也为 $O(logn)$。

空间复杂度：$O(logn)$。

方法二：快速幂-迭代

在完全理解了递归的思想后，会发现递归真简单，但是完全理解递归之前还是觉得迭代简单容易理解。现在就来看看迭代解法。

我们依旧是使用二分来计算幂：

• 如果指数为奇数，则累乘答案，即 res *= x；
• 然后更新 x *= x；
• 最后返回 res 即可。

实现代码

class Solution {
public:
    double quickMul(double x, long long n) {
        double res = 1.0;
        for (; n; n /= 2) {
            if (n & 1) {
                res *= x;
            }
            x *= x;
        }
        return res;
    }
		
    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};

复杂度分析

时间复杂度：$O(logn)$，$n$ 为幂指数。

空间复杂度：$O(1)$。

其他语言

python3

在 Python 中，可以使用内置的 pow 函数来进行快速幂的计算。pow 函数的签名如下：

pow(x, y, z=None, /)

其中，x 为底数，y 为指数，z 为模数（如果指定了模数，则返回 x**y % z）。这个函数的时间复杂度较低，因为它采用了快速幂的算法。

以下是一个示例：

# 计算 2 的 10 次方
result = pow(2, 10)

# 输出结果
print(result)

上述代码会输出 1024，即 2 的 10 次方的结果。在这个例子中，pow 函数的参数分别为底数、指数，没有指定模数。

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。