Python每日一练-----python实现Pow(x,y)
☀(day48:P45)
目录
📝题目:
🚩题目分析:
💡解题思路:
🌟解法一:快速幂+递归
🌈代码实现
✏代码注释
🌟解法二:快速幂 + 迭代
🌈代码实现
✏代码注释
📝题目:
实现 pow(x, n) ,即计算 x
的 n
次幂函数(即,xn
)。
⭐示例 1:
输入:x = 2.00000, n = 10
输出:1024.00000
⭐示例 2:
输入:x = 2.10000, n = 3
输出:9.26100
⭐示例 3:
输入:x = 2.00000, n = -2
输出:0.25000
解释说明:2-2 = 1/22 = 1/4 = 0.25
🚩题目分析:
对于C语言中的pow(x,y),表示x的y次方。我们当然可以使用python的次方算法,x ** y,也表示x的y次方。下面我们介绍其他计算x的y次方的两种方法。
💡解题思路:
🌟解法一:快速幂+递归
快速幂算法的本质是分治算法。
举个例子,如果我们要计算,我们可以按照:
x→→→→→x→的方式计算
再如计算次方,我们可以按照:
x→→→→→→
(2*2 = 4, 4*2 = 8, 9*2 = 18, 19*2 = 38,38*2 = 76)
的方式计算
在的计算过程中,我们直到x的幂不都是以2倍增长,有些情况下需要额外乘一个x。
那么我们怎么直到什么时候乘上一个额外的x?
所以该方法实现起来是比较困难的。
所以我们可以先使用递归计算出 ,"//"表示整除,令y = 。
接着判断n是奇数还是偶数
如果n是偶数,那么n/2为整数, = y *y= *
如果n是奇数,那么n/2不可整除, = y*y*x= * * x
既然使用递归,那么我们判断递归的边界条件,我们很容易看出递归边界条件为1,我们使用递归时,给递归函数传入的参数为n,当n等于0时,计算结果为1,任何数的0次方都=1.
🌈代码实现
def myPow(x, n): 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)
✏代码注释
def myPow(x, n): def quickMul(N): if N == 0: # 递归边界条件 return 1.0 y = quickMul(N // 2) # 用递归计算 y = x^(n//2) return y * y if N % 2 == 0 else y * y * x # 实际上y的值在这里计算 # 如果时负次幂则转换成正幂,再将结果用分式计算得到正确答案 return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)
时间复杂度:O(logn),即为递归的层数。
空间复杂度:O(logn),即为递归的层数。这是由于递归的函数调用会使用栈空间。
🌟解法二:快速幂 + 迭代
我们分析的计算过程
x→→→→→→
我们从右往左看
第一个乘额外的x在 →这一步,这个额外乘的x在中占有x
第二个 乘额外的x在 → 这一步,这个额外乘的x再经过后面x^19到x^38和x^38到x^77 两步计算中进行了两次平方,所以这个额外乘的x在中占有(x^2)^2 = x^4
第三个 乘额外的x在 → 这一步,这个额外乘的x再经过后面,x^8到x^19, x^19到x^38 和 x^38到x^77 三步计算中进行了两次平方,所以这个额外乘的x在中占有((x^2)^2)^2 = x^8
最初的 x 在之后被平方了 6 次,因此在 x^77中占有x^64。
我们将这也额外乘的x在x^77所占的部分相乘。x * x^4 * x^8 * x^64 = x^77.
它们都是 2 的幂次,这是因为每个额外乘的 x 在之后都会被平方若干次。而这些指数 1,4,8 和 64,恰好就对应了 77的二进制表示 1001101中的每个 1!
1 0 0 1 1 0 1
x^64 x^32 x^16 x^8 x^4 x^2 x^1那么我们怎么获取n对应二进制的1位数?
其实我们不必
🌈代码实现
def myPow(x, n): def quickMul(x, n): to_square = x ans = 1 while n > 0: if n % 2 == 1: ans *= to_square to_square *= to_square n //= 2 return ans return quickMul(x, n) if n >= 0 else 1 / quickMul(x, -n)
✏代码注释
def myPow(x, n): def quickMul(x, n): to_square = x # x所占的初始值为 x ans = 1 while n > 0: if n % 2 == 1: # 判断最低位是否为1 ans *= to_square # 因为下面我们不断舍弃最低为,则下一个最地位对应上一个to_square的平方 # 所以我们将to_square不断地平方 to_square *= to_square # 使用整除舍弃 n 二进制表示的最低位,这样我们每次只要判断最低位即可 n //= 2 return ans return quickMul(x, n) if n >= 0 else 1 / quickMul(x, -n)
时间复杂度:O(log n),即为对 n 进行二进制拆分的时间复杂度。
空间复杂度:O(1)。
今天就到这,明天见。🚀
❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄