https://leetcode-cn.com/problems/powx-n/
public double MyPow(double x, int n) { if (x == 1 || n == 0) { return 1; } if (n == 1) { return x; } double dReturn = x; int num = n; if (n < 0) { dReturn = 1 / x; num = n * -1; } else { dReturn = dReturn * dReturn; } for (int i = 2; i <= num;) { if (i * 2 > num) { if (n > 0) { dReturn = dReturn * x; } else { dReturn = dReturn / x; } i = i + 1; } else { dReturn = dReturn * dReturn; i = i * 2; } } return dReturn; }
public double MyPow(double x, int n) { long N = n; return N >= 0 ? QuickMul(x, N) : 1.0 / QuickMul(x, -N); } public double QuickMul(double x, long N) { if (N == 0) { return 1.0; } double y = QuickMul(x, N / 2); return N % 2 == 0 ? y * y : y * y * x; }
复杂度分析
时间复杂度:O(\log n)O(logn),即为递归的层数。
空间复杂度:O(\log n)O(logn),即为递归的层数。这是由于递归的函数调用会使用栈空间。
public double MyPow(double x, int n) { long N = n; return N >= 0 ? QuickMul(x, N) : 1.0 / QuickMul(x, -N); } public double QuickMul(double x, long N) { double ans = 1.0; // 贡献的初始值为 x double x_contribute = x; // 在对 N 进行二进制拆分的同时计算答案 while (N > 0) { if (N % 2 == 1) { // 如果 N 二进制表示的最低位为 1,那么需要计入贡献 ans *= x_contribute; } // 将贡献不断地平方 x_contribute *= x_contribute; // 舍弃 N 二进制表示的最低位,这样我们每次只要判断最低位即可 N /= 2; } return ans; }
复杂度分析
时间复杂度:O(\log n)O(logn),即为对 nn 进行二进制拆分的时间复杂度。
空间复杂度:O(1)O(1)。