题目

实现 pow(x, n)，即计算 x 的 n 次幂函数。

示例 1:

  1. 输入: 2.00000, 10
  2. 输出: 1024.00000

示例 2:

  1. 输入: 2.00000, -2
  2. 输出: 0.25000

方案一（暴力法）

  1. func myPow(x float64, n int) float64 {
  2.     if n < 0 {
  3.         n = -n
  4.         x = 1 / x
  5.     }
  7.     res := 1.0
  8.     for i := 0; i < n; i++ {
  9.         res = res * x
  10.     }
  12.     return res
  13. }
  • 超时
  • 时间复杂度 Pow(x, n) - 图1
  • 空间复杂度 Pow(x, n) - 图2

方案二（迭代）

  1. func myPow(x float64, n int) float64 {
  2.     if n < 0 {
  3.         n = -n
  4.         x = 1 / x
  5.     }
  7.     ans := 1.0
  8.     current_product := x
  9.     for n != 0 {
  10.         if n % 2 == 1 {
  11.             ans = ans * current_product
  12.         }
  13.         n = n / 2
  14.         current_product = current_product * current_product
  15.     }
  17.     return ans
  18. }
  • 时间复杂度 Pow(x, n) - 图3
  • 空间复杂度 Pow(x, n) - 图4

    方案三（递归）

  1. func myPow(x float64, n int) float64 {
  2.     if n == 0 {
  3.         return 1.0
  4.     }
  5.     if n < 0 {
  6.         n = -n
  7.         x = 1 / x
  8.     }
  9.     if n % 2 == 1 {
  10.         return x * myPow(x * x, n / 2)
  11.     }
  12.     return myPow(x * x, n / 2)
  13. }
  • 二分，或者叫分治
  • 时间复杂度 Pow(x, n) - 图5

    原文

https://leetcode-cn.com/explore/featured/card/recursion-i/259/complexity-analysis/1227/