快速幂

本题要求x的n次方，n很大，所以O(n)的解法肯定不行，只能考虑O(logn)复杂度的解法。我们可以想到，若 n n 为偶数，xn=(x2)n/2xn=(x2)n/2，若 n n 为奇数，则xn=x⋅x(n−1)/2xn=x·x(n−1)/2,由此可以想到由递归方式来解决。代码： class Solution { public: double myPow(double x, int n) { if (n == 0) return 1; else { long long t = (long long)n; if (n<0) t = -(long long)n; if (t % 2 == 0) { x = myPow(x*x, t / 2); } else { x = myPow(x, t - 1)*x; } if (n<0) x = 1 / x; return x; } } };