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. class Solution {
  5. public:
  6.     double myPow(double x, int n) {
  7.         if (n < 0) return 1.0 / power(x, -n);
  8.         else return power(x, n);
  9.     }
  10. private:
  11.     double power(double x, int n) {
  12.         if (n == 0) return 1;
  13.         double v = power(x, n / 2);
  14.         if (n % 2 == 0) return v * v;
  15.         else return v * v * x;
  16.     }
  17. };

相关题目

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