Pow有没有比log(n)更好点的解法? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Pow有没有比log(n)更好点的解法?

Pow有没有比log(n)更好点的解法?# JobHunting - 待字闺中

l*h2013-01-11 08:01

1 楼

比如下面这个log(n)的, 很容易实现，为什么喜欢考这个题？
public double pow(double x, int n) {
if (n == 0) return 1;
if (x == 0) return 0;
boolean positive = true;
if (n < 0) {
positive = false;
n = -n;
}

double tmp = pow(x, n/2);
double ret;
if (n%2 == 0) {
ret = tmp*tmp;
}
else {
ret = x*tmp*tmp;
}
return positive ? ret : 1.0/ret;
}

t*h2013-01-11 08:01

2 楼

pow(1,12323243243)?

【在 l**h 的大作中提到】

: 比如下面这个log(n)的, 很容易实现，为什么喜欢考这个题？
: public double pow(double x, int n) {
: if (n == 0) return 1;
: if (x == 0) return 0;
: boolean positive = true;
: if (n < 0) {
: positive = false;
: n = -n;
: }
:

b*h2013-01-11 08:01

3 楼

就算容易实现也不是都可以实现的好从实现上也能看出功底比如说这个递归可以更
简洁甚至不用递归

j*n2013-01-11 08:01

4 楼

agreed. theres definitely room for improvement, not necessarily in terms of
complexity but implementation.

【在 b*********h 的大作中提到】

: 就算容易实现也不是都可以实现的好从实现上也能看出功底比如说这个递归可以更
: 简洁甚至不用递归

l*h2013-01-11 08:01

5 楼

找到一个号称constant time解决的，还没看懂，最后一种解法：
http://blog.unieagle.net/2012/08/23/leetcode%E9%A2%98%E7%9B%AE%

【在 l**h 的大作中提到】

c*t2013-01-11 08:01

6 楼

最后一种解法貌似也是lgn的。按n的binary走的，本质与n/2应该一样
pow(double, double)应该怎么做？

【在 l**h 的大作中提到】

: 找到一个号称constant time解决的，还没看懂，最后一种解法：
: http://blog.unieagle.net/2012/08/23/leetcode%E9%A2%98%E7%9B%AE%

r*e2013-01-11 08:01

7 楼

为啥叫constant time? 那个实现就是logN (based on 2)的解法啊。

【在 l**h 的大作中提到】

: 找到一个号称constant time解决的，还没看懂，最后一种解法：
: http://blog.unieagle.net/2012/08/23/leetcode%E9%A2%98%E7%9B%AE%

w*o2013-01-11 08:01

8 楼

好像不是Constant time。任然是O（lgn）。而且还可以简化：
public class Solution {
public double pow(double x, int n) {
boolean isNeg = n < 0;
if(n < 0)
n = -n;

double ret = 1.0;
while(n>0) {
if((n&1) >0)
ret *= x;
x *= x;
n >>= 1;
}

return isNeg? 1.0/ret : ret;
}
}

【在 l**h 的大作中提到】

: 找到一个号称constant time解决的，还没看懂，最后一种解法：
: http://blog.unieagle.net/2012/08/23/leetcode%E9%A2%98%E7%9B%AE%