LeetCode--Pow(x, n)

发布时间:2017-3-8 8:47:14
来源:分享查询网

Question

Implement pow(x, n).

解题思路

问题如此简单,第一反应求指数也就是求多个数的乘积,那么直接for循环走起,结果一提交发现超时了。

那么我们就来分析一下,如果用以上方法,那么时间复杂度为O(n), O(n)都超时了,说明时间复杂度还应该更低,多少呢?这个时候可以考虑log(n)了,什么样的算法可以达到log(n)呢?

那就是分治算法!if (n%2 == 0), x^n = x(n/2) * x(n/2); if (n%2 != 0), x^n = x(n/2) * x * x(n/2);

实现代码

#include <iostream>using namespace std;class Solution {public:    double power(double x, int n){        if(n==0)            return 1;        double v = power(x,n/2);        if(n%2 == 0)            return v *v;        else            return v* v* x;    }    double pow(double x, int n) {        if(n<0)            return 1.0 / power(x,-n);        else            return power(x,n);    }};int main() {    Solution* solution = new Solution();    cout << solution->pow(2, 4) << endl;    return 0;

返回顶部
查看电脑版