y*****o
发帖数: 36 | 1 看到facebook的面经里这道题出现好几次。
我能想到的做法就是根据Newton's method
http://en.wikipedia.org/wiki/Newton's_method
Public static double squareroot(double num)
{
double number;
number =num/2;
do{
number=(number+num/number)/2；
}while (number*number-num >0.00001)
return number;
}
可是如果这样的话，那time complexity是多少呢？？ |
y*****o
发帖数: 36 | |
w******g
发帖数: 67 | 3 你这个是 binary search 吧？
～O(logn)? |
l**p
发帖数: 328 | 4 泰勒展开先
【在 y*****o 的大作中提到】
: 看到facebook的面经里这道题出现好几次。
: 我能想到的做法就是根据Newton's method
: http://en.wikipedia.org/wiki/Newton's_method
: Public static double squareroot(double num)
: {
: double number;
: number =num/2;
: do{
: number=(number+num/number)/2；
: }while (number*number-num >0.00001)
|
A********l
发帖数: 184 | 5 牛顿法解方程
x^2 - c = 0
【在 y*****o 的大作中提到】
: 看到facebook的面经里这道题出现好几次。
: 我能想到的做法就是根据Newton's method
: http://en.wikipedia.org/wiki/Newton's_method
: Public static double squareroot(double num)
: {
: double number;
: number =num/2;
: do{
: number=(number+num/number)/2；
: }while (number*number-num >0.00001)
|
A***J
发帖数: 478 | |
t****a
发帖数: 1212 | |
q**r
发帖数: 611 | 8 Sqrt(x) = ?
Find a, b, s.t., a^2 < x < b^2.
Then Bisection between a & b. |
y*****o
发帖数: 36 | 9 对，用的是牛顿法，可是对于return type是double的，也就只能通过epsilon返回近似
值。对吗？ |
A********l
发帖数: 184 | 10 是的。
【在 y*****o 的大作中提到】
: 对，用的是牛顿法，可是对于return type是double的，也就只能通过epsilon返回近似
: 值。对吗？
|
s***e
发帖数: 793 | 11 it is a well-studied problem
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
【在 y*****o 的大作中提到】
: 看到facebook的面经里这道题出现好几次。
: 我能想到的做法就是根据Newton's method
: http://en.wikipedia.org/wiki/Newton's_method
: Public static double squareroot(double num)
: {
: double number;
: number =num/2;
: do{
: number=(number+num/number)/2；
: }while (number*number-num >0.00001)
|
y*****o
发帖数: 36 | 12 哦，原来有这么多方法啊，谢谢分享！！
【在 s***e 的大作中提到】
: it is a well-studied problem
: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
|
