50 pow(x,n) 二分.md

---

---

Implement pow(x, n), which calculates x raised to the power n (xn).

题目

暴力

循环或者递归连乘n次，非常耗时间，不推荐

快速幂（乘方分解x）

假定我们已经得到了 xn/2x^{n/2}xn/2的结果，并且我们现在想得到 xnx^nxn的结果。我们令 A 是 xn/2x ^ {n / 2}xn/2的结果，我们可以根据 n 的奇偶性来分别讨论 xnx ^ nxn的值:

1. 如果n是偶数，xnx ^ nxn = (xn/2)2(x^{n/2})^2(xn/2)2
2. 如果n是奇数，xnx ^ nxn = (xn//2)2(x^{n//2})^2(xn//2)2*x (python中n//2是地板除)
   用递归的方法求解

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1/x
            n = -n
        def fastPow(x,n):
            if n == 0:  return 1
            halfPow = fastPow(x,n//2)
            if n%2:#odd
                return halfPow*halfPow*x
            else:#even
                return halfPow*halfPow
        return fastPow(x,n)

快速幂（用某个进制分解n）

目的就是把n用某种进制分解，使得分解出来的组分中，后一个可以用前一个表示，从而降低复杂度，最常用的是二进制或者十进制，这里用二进制为例，详细算法请见这里

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1/x
            n = -n
        x_2t = x#从x^(2^0)开始
        res = 1
        while n:
            if n%2: res *= x_2t#b_t只可能是0或者1，这个分支说明b_t是1，最终结果需要乘上x^(2^t)
            x_2t *= x_2t#每次x^(2^t-1)平方得到x^(2^t)
            n//=2
        return res

如果不理解，就把式子列出来，然后用xa+bx^{a+b}xa+b=xax^axa*xbx^bxb来拆开