Pow(x, n)

作者: 小王子特洛伊 | 来源:发表于2020-05-20 07:21 被阅读0次

    实现 pow(x, n) ,即计算 x 的 n 次幂函数。
    示例 1:
    输入: 2.00000, 10
    输出: 1024.00000
    示例 2:
    输入: 2.10000, 3
    输出: 9.26100
    示例 3:
    输入: 2.00000, -2
    输出: 0.25000
    解释: 2^{-2} = 1/2^2 = 1/4 = 0.25
    说明:
    -100.0 < x < 100.0
    n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

    解法 1

    暴力法,x 的 n 次幂就是 n 个 x 相乘,注意处理 n 为负数的情况,需要将 x 变为 x 的倒数,再将 n 变为正数

    def my_pow(x, n):
        if n < 0:
            x = 1 / x
            n = -n
        ans = 1
        for i in range(n):
            ans = ans * x
        return ans
    

    执行用时:超出时间限制

    时间复杂度:O(n),我们需要将 x 累乘 n 次。
    空间复杂度:O(1),我们只需要一个变量来保存最终 x 的累乘结果。

    解法 2

    利用递归实现分治法,我们可以根据幂的奇偶来将公式拆解,使得运算数值尽可能小,从而提升运算速度,若为偶数 x^n=(x\cdot x)^{\frac{n}{2}},若为奇数 x^n=x^{n-1}x,注意若 n 为负数,x^n=\frac{1}{x^{-n}}。当 n 为 1 时返回 x,这是递归的出口。另外,需要注意 x = 0 或 1,n = 0 或 1,n < 0 等情况。

    def my_pow(x, n):
        if n == 0:
            return 1.0
        if n == 1:
            return x
        if n < 0:
            return 1 / my_pow(x, -n)
        if n % 2:
            return x * my_pow(x, n - 1)
        return my_pow(x * x, n / 2)
    

    执行用时 :40 ms
    内存消耗 :13.7 MB

    时间复杂度:O(log n),每一次我们使用公式 x^n=(x\cdot x)^{\frac{n}{2}},n 都变为原来的一半。因此我们需要最多 O(log n) 次操作来得到结果。

    空间复杂度:O(log n),每一次计算,我们需要存储 x ^ {\frac{n }{2}} 的结果。 我们需要计算 O(log n) 次,所以空间复杂度为 O(log n) 。

    解法 3

    利用迭代实现二进制拆分,由于递归需要使用额外的栈空间,我们可以将递归转写为迭代。我们观察一下 n 的二进制表示,假设 n = 77,二进制表示为 1001101,将其包含 1 的部分拆分为 1000000 0001000 0000100 0000001。其中,1000000 的十进制表示为 64,0001000 的十进制表示为 8,0000100 的十进制表示为 4,0000001 的十进制表示为 1,而一个数 x^{77} 恰好等于 x^{64}\times x^8\times x^4\times x^1。那么,如果计算一个数 x 的 n 次幂,就可以从 x 开始不断地进行平方,得到 x^2, x^4, x^8, x^{16},\cdots 如果 n 的第 k 个(从右往左,从 0 开始计数)二进制位为 1,那么我们就将 x^{2^k} 计入结果,注意是从 0 开始计数,如果 n 的二进制第 0 位为 1,则将 x^{2^0} 计入结果,并全部累乘得到最终结果。

    def my_pow(x, n):
        if n < 0:
            x = 1 / x
            n = -n
        ans = 1
        while n > 0:
            if n & 1:
                ans *= x
            x *= x
            n >>= 1
        return ans
    

    执行用时 :44 ms
    内存消耗 :13.8 MB

    时间复杂度:O(log n),对 n 进行二进制拆分的时间复杂度。
    空间复杂度:O(1)

    参考

    https://leetcode-cn.com/problems/powx-n/

    相关文章

      网友评论

          本文标题:Pow(x, n)

          本文链接:https://www.haomeiwen.com/subject/yxfmvctx.html