leetcode50. Pow(x, n)，快速幂算法
leetcode50. Pow(x, n)，快速幂算法
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
目录
- leetcode50. Pow(x, n)，快速幂算法
- 总体思维导图
- 快速幂算法详解
- 算法背景
- 算法原理
- 算法步骤
- 算法优势
- 应用场景
- 流程图
- 具体代码
- 算法分析
- 相似题目
总体思维导图
快速幂算法详解
算法背景
快速幂算法是一种高效计算 x n x^n xn 的方法，特别适用于 n n n 非常大的情况。它基于幂的性质和二进制表示。
算法原理
- 二进制表示：任何整数 n n n 都可以用二进制表示。例如， 13 13 13 的二进制表示是 1101 1101 1101。
- 幂的性质： x n x^n xn 可以分解为 x 2 0 × x 2 1 × x 2 2 × … x^{2^0} \times x^{2^1} \times x^{2^2} \times \ldots x20×x21×x22×… 的形式。例如， x 13 x^{13} x13 可以分解为 x 1 × x 4 × x 8 x^{1} \times x^{4} \times x^{8} x1×x4×x8。
- 位操作：通过检查 n n n 的二进制表示中的每一位，我们可以确定是否需要将对应的 x 2 k x^{2^k} x2k 乘入结果中。
算法步骤
-
初始化：
- 设置结果
res为 1。 - 将指数 n n n 转换为长整型
nn以避免在负数时的整数溢出。
- 设置结果
-
特殊情况处理：
- 如果 x = 1 x = 1 x=1，直接返回 x x x。
- 如果 x = − 1 x = -1 x=−1，根据 n n n 的奇偶性返回 x x x 或 − x -x −x。
- 如果 n < 0 n < 0 n<0，将 n n nn nn 设为正数，并将 x x x 设为其倒数。
-
快速幂计算：
- 使用 while 循环，当 n n > 0 nn > 0 nn>0 时执行。
- 如果 n n nn nn 的当前最低位为 1（
nn & 1），则将 r e s res res 乘以 x x x。 - 将 n n nn nn 右移一位（
nn >>= 1），即除以 2。 - 将 x x x 平方（
x = x * x）。
-
返回结果：
- 当 n n nn nn 变为 0 时，返回
res。
- 当 n n nn nn 变为 0 时，返回
算法优势
- 时间复杂度降低：传统的幂运算需要 O ( n ) O(n) O(n) 的时间复杂度，而快速幂算法只需要 O ( log n ) O(\log n) O(logn)。
- 减少乘法操作：通过跳过不必要的乘法，算法减少了计算量。
应用场景
快速幂算法常用于需要高效率幂运算的场合，例如密码学、大数运算等。
这个算法的关键在于利用了二进制的性质和位操作，从而将一个复杂的幂运算问题转化为一系列更简单的乘法和位移操作。
流程图
具体代码
class Solution {
public:double myPow(double x, int n) {double res=1;long long nn=(long long)n;if(x==1.00000){return x;}if(x==-1.00000){if(nn%2==1) return x;else return -x;}if(nn<0) {nn=-nn;x=1/x;}while(nn){if(nn&1) res*=x;nn>>=1;x=x*x;}return res;}
};
算法分析
- 时间复杂度： O ( log n ) O(\log n) O(logn)，因为每次循环 n n n 都至少减少一半。
- 空间复杂度： O ( 1 ) O(1) O(1)，只使用了常数空间。
- 易错点：处理负指数和 x = − 1 x = -1 x=−1 的情况时容易出错。
- 注意点：使用
long long类型处理大指数，防止整数溢出。
相似题目
下面是一些与快速幂算法相关的题目，您可能会感兴趣：
| 题目 | 链接 |
|---|---|
| Pow(x, n) | LeetCode |
| Super Pow | LeetCode |
| Pow(x, n) II | LintCode |
这些题目都可以使用快速幂算法来解决。