题目

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

思考

Power(a, n)，如果直接计算，需要计算n-1次乘法。时间复杂度为O(n)。

考虑pow(a, n) = pow(a, n//2) * pow(a, n//2)，那么只需要计算一半的乘法，因为两边一样的，只用考虑一边。（暂时忽略n奇偶）。

二分法。时间复杂度O(logn)

代码

  1. class Solution:
  2.     def myPow(self, x: float, n: int) -> float:
  3.         if n < 0:
  4.             return 1/self.myPow(x, abs(n))
  5.         if n == 0:
  6.             return 1
  7.         if n == 1:
  8.             return x
  10.         result = self.myPow(x, n >> 1)
  11.         result *= result
  12.         # print(result)
  13.         if (n & 1) == 1:
  14.             result *= x
  16.         return result