每日一道算法之--Pow(x, n)

位运算快速幂

Word count: 507Reading time: 2 min

 2020/05/11   Share

快速幂

快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)，与朴素的O(N)相比效率有了极大的提高。

一篇关于快速幂的好文章.

作者：jyd
链接：https://leetcode-cn.com/problems/powx-n/solution/50-powx-n-kuai-su-mi-qing-xi-tu-jie-by-jyd/

关于快速幂的题目

Pow(x, n)

力扣第50题: https://leetcode-cn.com/problems/powx-n/

实现 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/22 = 1/4 = 0.25

说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
通过次数88,769提交次数249,427

1. 快速幂解法(迭代解法)

如果读懂了文章(主要是读懂分治思想理解快速幂), 这道题就很简单了.

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0.0:
            return 0.0
        res = 1
        if n < 0:
            x, n = 1/x, -n
        while n:
            if n & 1:
                res *= x
            x *= x
            n = n >> 1
        return res

复杂度分析

时间复杂度：O(logn)，即为对 n 进行二进制拆分的时间复杂度。

空间复杂度：O(1)。

2. 快速幂解法(递归解法)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(N):
            if N == 0:
                return 1.0
            y = quickMul(N // 2)
            return y * y if N % 2 == 0 else y * y * x

        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

复杂度分析

时间复杂度：O(logn)，即为递归的层数。

空间复杂度：O(logn)，即为递归的层数。这是由于递归的函数调用会使用栈空间。

3. 还有一种我之前看别人的解法,挺有趣的

class Solution:
    def myPow(self, x: float, n: int) -> float:
        res, base = 1, x
        if n < 0:
            base = 1 / x
            n = -n
        while n > 0:
            tmp, i = base, 1
            # 注意，这里是大于等于0
            while n - i >= 0:
                res *= tmp
                n -= i
                tmp *= tmp
                i = i << 1
        return res

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/05/11/algorithm-50/

发表日期：May 11th 2020, 10:33:27 pm

更新日期：May 11th 2020, 10:34:22 pm

Next Post

每日一道算法之--求众数II
Previous Post

每日一道算法之--在 D 天内送达包裹的能力

CATALOG

1. 快速幂
1. 1.1. 关于快速幂的题目

