要求 , 其中 , . 先不妨假设 , 基本想法是
很容易写出时间复杂度 的递归算法, 而要写迭代算法需要再想一想.
迭代
用二进制表示指数 , 其中 , 则 .
以 10 为例, 把它转化成二进制数.
由于 10 是偶数, 所以 .
由于 10/2 是奇数, 所以 .
由于 (5-1)/2 是偶数, 所以 .
由于 2/2 是奇数, 所以 .
由此
class Solution:
def myPow(self, a: float, n: int) -> float:
if n>= 0:
res = 1
while n:
if n % 2:
res *= a
n //= 2
a *= a
return res
else:
return 1/self.myPow(a, -n)
另外, Python 对小整数乘法有优化 (见 这里). 就 3.7 版本来说, 下面前两句时间一样, 后两句时间一样, 所以没有必要强行把代码写成位运算.
for _ in range(int(1e8)):
7777777 >> 1
for _ in range(int(1e8)):
7777777 // 2
for _ in range(int(1e8)):
7777777 & 1
for _ in range(int(1e8)):
7777777 % 1
取模
若
考虑 , , 其中 立即可以看出.
由此易知 对 取模的算法.
No comments:
Post a Comment