Sqrt(X) 的time complexity 是多少呢 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Sqrt(X) 的time complexity 是多少呢

Sqrt(X) 的time complexity 是多少呢# JobHunting - 待字闺中

c*f2013-03-27 07:03

1 楼

Implement int sqrt(int x).
Compute and return the square root of x.
这个问题的复杂度是多少呢，
both recursive way and Newton Raphson way

b*l2013-03-27 07:03

2 楼

Binary search, log(n)?

k*e2013-03-27 07:03

3 楼

要返回int么？binary search, 复杂度log(n)吧

【在 c***f 的大作中提到】

: Implement int sqrt(int x).
: Compute and return the square root of x.
: 这个问题的复杂度是多少呢，
: both recursive way and Newton Raphson way

f*e2013-03-27 07:03

4 楼

所有这类题的答案都是log(1/\epsilon)，\eplison是你所要的精度比如10^-5啥的。

【在 c***f 的大作中提到】

: Implement int sqrt(int x).
: Compute and return the square root of x.
: 这个问题的复杂度是多少呢，
: both recursive way and Newton Raphson way

c*f2013-03-27 07:03

5 楼

这道题的返回值是不是要满足：
Min(r^2 - X) 其中r＊r <= X ?
比如 sqrt(8) 返回2 而不是3？

g*e2013-03-27 07:03

6 楼

Quake3 developer: constant

b*l2013-03-27 07:03

7 楼

Right.

【在 c***f 的大作中提到】

: 这道题的返回值是不是要满足：
: Min(r^2 - X) 其中r＊r <= X ?
: 比如 sqrt(8) 返回2 而不是3？

y*n2013-03-27 07:03

8 楼

牛顿迭代的算法要远好于Binary Search的O(lgn)。
贴个Sqrt(double)的算法。
static double Sqrt(double num)
{
double root = 1;
double diff = num - root * root;
double oldDiff = double.MaxValue;
int loop = 0;
while ((loop < 2) || (Math.Abs(diff) < Math.Abs(oldDiff)))
{
root = root + diff / root / 2;
oldDiff = diff;
diff = num - root * root;
loop++;
}
return root;
}

l*a2013-03-27 07:03

9 楼

这道题的考点是什么？
看你知不知道知名算法？知道了证明你知识渊博？

【在 y****n 的大作中提到】

: 牛顿迭代的算法要远好于Binary Search的O(lgn)。
: 贴个Sqrt(double)的算法。
: static double Sqrt(double num)
: {
: double root = 1;
: double diff = num - root * root;
: double oldDiff = double.MaxValue;
: int loop = 0;
: while ((loop < 2) || (Math.Abs(diff) < Math.Abs(oldDiff)))
: {

y*n2013-03-27 07:03

10 楼

改编成整数开方。算法复杂度说不清楚，远好于O(lgN)。
我只假设是O(lg(lgN))。
static Int64 SqrtInt(Int64 num)
{
Int64 maxRoot = (Int64)1 << 31;
Int64 root = 1;
Int64 oldDiff = Int64.MaxValue;
Int64 diff = num - root * root;
int loop = 0;
while ((loop < 2) || (Math.Abs((double)diff) < Math.Abs((double)oldDiff)
))
{
root = Math.Min(maxRoot, root + diff / root / 2);
oldDiff = diff;
diff = num - root * root;
loop++;
}
return (diff < 0) ? root - 1 : root;
}

p*e2013-03-27 07:03

11 楼

N是哪个数？
如果是这样的话，算多少
class Solution {
public:
int sqrt(int x) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(x < 0) return -1;
if(x == 0) return 0;
stack ss;
while(x > 0){
ss.push(x%100);
x = x/100;
}
int result = 0, t;
int residue = 0;
while(!ss.empty()){
int base = 20 * result;
t = ss.top() + residue*100;
ss.pop();
if(t == 0){
result = result * 10;
continue;
}
int a = 9;
residue = t - (base + a)*a;
while(residue < 0){
--a;
residue = t - (base + a)*a;
}
result = result * 10 + a;
}
return result;
}
};

y*k2013-03-27 07:03

12 楼

觉得 yishan 的方法大体对。会终止吗？运行过吗？需要回到实数吗？
一般牛顿法的收敛似乎并不是那么好做的。这个可以。

x*72013-03-27 07:03

13 楼

eg. find square root of 622
take a guess x = 10, take an error = 0.01
while( abs(x*x - num >= error) )
x = x - (x*x - num)/(2*x)
complexity 不知道怎么算了，还给老师了。。

m*g2013-03-27 07:03

14 楼

如果我没有记错，牛顿迭代法好像每做一次其精度增加一倍。
fatalme的log(1/\epsilon)对不对我不知道，不过似乎应该跟精度有关。
My 2 cents.

d*y2013-03-27 07:03

15 楼

牛顿迭代法的时间复杂度很不好算，可以看看这个http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity
binary search应该是O(log n e)吧，n是待求数字，e是精度。不是很确定。
写了一下这两个程序：
public class FloatSqrt {
public static double error = 0.000001;
public static double getFloatSqrt(double x) {
if (x <= 0) {
return -1;
}
double y = x;
double z;
while (true) {
z = (y + x / y) / 2;
if (Math.abs(z - y) < error) {
break;
} else {
y = z;
}
}
return y;
}
public static double getFloatSqrtRecursion(double x, double y) {
double z = (y + x / y) / 2;
if (Math.abs(z - y) < error) {
return y;
} else {
return getFloatSqrtRecursion(x, z);
}
}
public static double getFloatSqrtBS(double x, double l, double h) {
double v = (l + h) / 2;
double diff = v * v - x;
if (Math.abs(diff) < error) {
return v;
} else if (diff < 0) {
return getFloatSqrtBS(x, v + 1, h);
} else {
return getFloatSqrtBS(x, l, v - 1);
}
}
public static void main(String[] args) {
System.out.println(getFloatSqrt(2));
System.out.println(getFloatSqrtRecursion(2, 2));
System.out.println(getFloatSqrtBS(2, 0, 2));
}
}