Pow(x,n)

描述

Implement pow(x, n).

分析

二分法，xn=xn/2×xn/2×xn%2x^n = x^{n/2} \times x^{n/2} \times x^{n\%2}

代码

  1. // Pow(x, n)
  2. // 二分法，$x^n = x^{n/2} * x^{n/2} * x^{n\%2}$
  3. // 时间复杂度O(logn)，空间复杂度O(1)
  4. public class Solution {
  5.     public double myPow(double x, int n) {
  6.         if (n < 0) return 1.0 / power(x, -n);
  7.         else return power(x, n);
  8.     }
  9.     private static double power(double x, int n) {
  10.         if (n == 0) return 1;
  11.         double v = power(x, n / 2);
  12.         if (n % 2 == 0) return v * v;
  13.         else return v * v * x;
  14.     }
  15. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/divide-and-conquer/pow.html