题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即， $x^n$ ）。不得使用库函数，同时不需要考虑大数问题。

https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

题解

求幂运算可以使用迭代或递归，该题以 O(n) 算法的迭代会时间超限，递归会溢出栈内存地址。
所以只能使用快速幂以 O(logn) 的时间解决。

快速幂：递归

class Solution {
    double quickMul(double x, long n) {
        if (n == 0) return 1.0;
        double y = myPow(x, n >> 1);
        return n & 1 ? y * y * x : y * y;
    }
public:
    double myPow(double x, int n) {
        return n >= 0 ? quickMul(x, n) : 1.0 / quickMul(x, -(long)n);     // -n会溢出int
    }
};

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

快速幂：迭代

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