F一题：double sqrt如何优化# JobHunting - 待字闺中
S*n
1 楼
binary search的话复杂度是log(nm), e= 10^-m;这个有办法优化吗？不知道面试官要
什么样的答案
什么样的答案
s*s
2 楼
newton法不能用在double上？
r*h
3 楼
double sqrt是说输入输出都要是double吗？
那应该用牛顿法比较好吧？
【在 S******n 的大作中提到】
: binary search的话复杂度是log(nm), e= 10^-m;这个有办法优化吗？不知道面试官要
: 什么样的答案
那应该用牛顿法比较好吧？
【在 S******n 的大作中提到】
: binary search的话复杂度是log(nm), e= 10^-m;这个有办法优化吗？不知道面试官要
: 什么样的答案
S*n
4 楼
就一直问我怎样优化，没说要用牛顿法啊，他就说如果x很大或者很小的情况下，应该
如何处理
如何处理
c*p
5 楼
还能再优化么？我想想。。。
c*y
6 楼
很小的时候，1/sqrt(1/x) 等价于很大
x很大的时候，可以把初始值猜得小一点。 肯定排除二分，起码newton-raphson
【在 S******n 的大作中提到】
: 就一直问我怎样优化，没说要用牛顿法啊，他就说如果x很大或者很小的情况下，应该
: 如何处理
x很大的时候，可以把初始值猜得小一点。 肯定排除二分，起码newton-raphson
【在 S******n 的大作中提到】
: 就一直问我怎样优化，没说要用牛顿法啊，他就说如果x很大或者很小的情况下，应该
: 如何处理
c*a
7 楼
newton就是优化。你画一画就明白了，比2分缩得还快。
在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。
在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。
r*h
8 楼
嗯，如果不用牛顿法，至少也要gradient descent
【在 c******a 的大作中提到】
: newton就是优化。你画一画就明白了，比2分缩得还快。
: 在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。
【在 c******a 的大作中提到】
: newton就是优化。你画一画就明白了，比2分缩得还快。
: 在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。
x*0
9 楼
mark
g*s
10 楼
不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
【在 c******a 的大作中提到】
: newton就是优化。你画一画就明白了，比2分缩得还快。
: 在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。
【在 c******a 的大作中提到】
: newton就是优化。你画一画就明白了，比2分缩得还快。
: 在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。
l*t
11 楼
牛顿本质上就是线性逼近
理解这个现场推公式还是不难的
【在 g*******s 的大作中提到】
: 不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
理解这个现场推公式还是不难的
【在 g*******s 的大作中提到】
: 不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
c*a
12 楼
只要以前看过一遍，一辈子都记住了吧。。。。。
【在 g*******s 的大作中提到】
: 不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
【在 g*******s 的大作中提到】
: 不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
s*s
13 楼
//agree. 我碰到过求三次方的，楞了一下，然后就推出来了。interviewer很高兴。
【在 c******a 的大作中提到】
: 只要以前看过一遍，一辈子都记住了吧。。。。。
【在 c******a 的大作中提到】
: 只要以前看过一遍，一辈子都记住了吧。。。。。
c*p
14 楼
先mark
r*h
15 楼
记住
x_1 = x_0 - f(x_0)/f'(x_0) 就可以啦
【在 g*******s 的大作中提到】
: 不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
x_1 = x_0 - f(x_0)/f'(x_0) 就可以啦
【在 g*******s 的大作中提到】
: 不过牛顿这东西不可能现场推出来吧？只能靠死记公式了～
p*e
16 楼
加上这个？
double power = 1.;
while(x < 1.){
power /= 10.;
x *= 100;
}
while(x > 100.){
power *= 10.;
x /= 100.;
}
.....
return ret*power;
【在 S******n 的大作中提到】
: 就一直问我怎样优化，没说要用牛顿法啊，他就说如果x很大或者很小的情况下，应该
: 如何处理
double power = 1.;
while(x < 1.){
power /= 10.;
x *= 100;
}
while(x > 100.){
power *= 10.;
x /= 100.;
}
.....
return ret*power;
【在 S******n 的大作中提到】
: 就一直问我怎样优化，没说要用牛顿法啊，他就说如果x很大或者很小的情况下，应该
: 如何处理
相关阅读
测试转开发要注意些什么？聪明的给帮忙解道题，实习offer选择的问题leetcode的strstr要怎么才能过large？今年就业形势 好像 不如去年啊四月办H1B，OPT 五月过期， 需要extend么intel的资深HR周六下午3点电话讲座和答疑马上要毕业了，还没有工作请大家说说用leetcode的经验第一次面试一般电面的过程是怎么样的？请问pre-opt换成post-opt需要多长时间？环境工程找工作经验Combination Sum II哪里做错了OPT期间转身份问题unrestricted work authorization to work in the USInternship openings at MERL (Boston area)有那种在线编译而且随时保存的网页不？农学PHD的OPT 能去工业界找统计之类的工作吗？终于得到理想的职位了