描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0。不得使用库函数,同时不需要考虑大数问题,也不用考虑小数点后面0的位数。
实际上就是实现一个计算 a ^ b 的函数。
朴素算法
让 exponent 个 base 相乘,时间复杂度是 O(exponent)。
// c++
class Solution {
public:
double Power(double base, int exponent) {
double res = 1;
if (exponent < 0) base = 1 / base, exponent = -exponent; // 注意指数为负,底数变成 1/base
while (exponent--)
res *= base;
return res;
}
};
# python3
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
res = 1
if exponent < 0: base, exponent = 1/base, -exponent
for _ in range(exponent):
res *= base
return res
快速幂
将 exponent 看成二进制,例如:
a ^ (0b1011)
= a ^ (0b1000 + 0b0000 + 0b0010 + 0b0001)
= a^(0b1000) * a^(0b0000) * a^(0b0010) * a^(0b0001)
= (1 * a^(2^3)) * (0 * a^(2^2)) * (1 * a^(2^1)) * (1 * a^(2^0))
可以看出规律,exponent 每一位是否为 1 决定了是否乘 base 的某次方,而 base 的某次方可以通过循环累乘得到,这样就把算法的时间复杂度降为了 O(log(exponent))。这个方法也叫快速幂。
// c++
class Solution {
public:
double Power(double base, int exponent) {
double res = 1;
if (exponent < 0) base = 1 / base, exponent = -exponent;
while (exponent) {
if (exponent & 1) res *= base;
base *= base;
exponent >>= 1;
}
return res;
}
};
# python3
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
res = 1
if exponent < 0: base, exponent = 1/base, -exponent
while exponent:
if exponent & 1: res *= base
base, exponent = base ** 2, exponent // 2
return res