16. 数值的整数次方.md

解题思路

直接相乘的 O(n) 时间复杂度的算法我们就不提了，这里给出效率更高的二次幂题解

1. 二次幂

当 n 为正数时：

• n 为偶数时：x^n^ = x^n/2^ * x^n/2^
• n 为奇数时：x^n^ = x^n/2^ * x^n/2^ * n

当 n 为负数时候：提前取 x 的倒数和 n 的相反数

func myPow(x float64, n int) float64 {
    if n < 0 {
        x = 1/x
        n *= -1
    }
    return pow(x, n)
}

func pow(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    if n == 1 {
        return x
    }
    sum := pow(x, n/2)
    if n % 2 == 1 {
        return sum * sum * x
    }
    return sum * sum
}