题目描述

实现函数double Power(double base, int exponent)，求base的 exponent次方。

不得使用库函数，同时不需要考虑大数问题。

注意：

• 不会出现底数和指数同为0的情况
• 当底数为0时，指数一定为正

样例 1

输入：10 ，2

输出：100

样例 2

输入：10 ，-2  

输出：0.01

算法

(模拟，快速幂) $O(logn)$

首先需要判断指数是正数还是负数，如果是负数计算结果需要求倒数
注意：

1. 如果指数是负数的话，取绝对值会超 int 的最大范围，所以这题需要用 long long
2. 当指数比较大（无穷大）时如果普通迭代处理会超时，需要用快速幂

时间复杂度

假设指数为 n，则快速幂代码一共会循环 $logn$ 次，时间复杂度为 $O(logn)$

C++ 代码

class Solution {
public:
    double Power(double base, int exponent) {
        typedef long long LL;

        double res = 1;
        bool is_minus = exponent < 0;

        for (LL k = abs((LL)exponent); k; k >>= 1)
        {
            if (k & 1) res *= base;
            base *= base;
        }
        if (is_minus) res = 1 / res;
        return res;
    }
};