快速幂算法（Fast Power / Exponentiation by Squaring）——分治思想实现

---

🎯 问题描述：

给定一个浮点数 base 和一个整数 exponent，请你计算 base^exponent 的值。

例如：

输入：base = 2.0, exponent = 10
输出：1024.0

输入：base = 2.0, exponent = -2
输出：0.25

---

🧩 思路分析：

直接循环相乘效率低（O(n)），尤其当指数很大时会超时。我们使用 分治法（快速幂） 可以将时间复杂度优化到 O(log n)。

分治策略：

• 如果 n 是偶数：$a^n = (a^{n/2})^2$
• 如果 n 是奇数：$a^n = a \cdot (a^{(n-1)/2})^2$

这种递归方式将问题规模每次减半，非常适合用递归来实现。

---

💻 C++代码实现 + 注释：

#include <iostream>

using namespace std;

// 快速幂函数（支持负指数）
double fastPower(double base, int exponent) {
    // 边界条件
    if (exponent == 0)
        return 1.0;

    // 处理负指数
    long long exp = (long long)exponent; // 防止INT_MIN取反溢出
    if (exp < 0) {
        base = 1 / base;
        exp = -exp; // 转为正指数
    }

    // 分治递归函数
    return fastPowerHelper(base, exp);
}

// 实际递归函数
double fastPowerHelper(double base, long long exponent) {
    if (exponent == 1)
        return base;
    if (exponent == 0)
        return 1;

    double half = fastPowerHelper(base, exponent / 2);

    if (exponent % 2 == 0) {
        return half * half; // 偶数：直接平方
    } else {
        return half * half * base; // 奇数：平方后乘 base
    }
}

int main() {
    double base;
    int exponent;

    cout << "请输入底数 base：";
    cin >> base;
    cout << "请输入指数 exponent：";
    cin >> exponent;

    double result = fastPower(base, exponent);

    cout.precision(10); // 设置输出精度
    cout << "结果为：" << fixed << result << endl;

    return 0;
}

---

✅ 示例运行：

输入：

请输入底数 base：2
请输入指数 exponent：10

输出：

结果为：1024.0000000000

---

输入：

请输入底数 base：2
请输入指数 exponent：-2

输出：

结果为：0.2500000000

---

⏱️ 时间复杂度分析：

• 每次将指数除以2，递归深度为 $O(\log n)$
• 每层只做常数次运算
• 所以总时间复杂度为：O(log n)

---

📌 进阶建议练习：

1. LeetCode 50. Pow(x, n)
2. 使用迭代方式实现快速幂（非递归）
3. 在模运算下求幂（用于加密算法中）

---

🔁 附加：非递归版本的快速幂（推荐进阶学习）

double fastPowerIterative(double x, int n) {
    long long exponent = n;
    if (exponent < 0) {
        x = 1 / x;
        exponent = -exponent;
    }

    double result = 1.0;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result *= x;
        }
        x *= x;
        exponent /= 2;
    }

    return result;
}

---

如果你还想了解如何在模运算中使用快速幂（如求 (a^b) % mod），或者想练习矩阵快速幂（用于斐波那契等动态规划问题），我也可以为你详细讲解 😊

---