c***f 发帖数: 40 | 1 Implement int sqrt(int x).
Compute and return the square root of x.
这个问题的复杂度是多少呢,
both recursive way and Newton Raphson way |
b*******l 发帖数: 590 | |
k****e 发帖数: 116 | 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*****e 发帖数: 2992 | 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***f 发帖数: 40 | 5 这道题的 返回值是不是要满足:
Min(r^2 - X) 其中r*r <= X ?
比如 sqrt(8) 返回2 而不是3? |
g*********e 发帖数: 14401 | 6 Quake3 developer: constant |
b*******l 发帖数: 590 | 7 Right.
【在 c***f 的大作中提到】 : 这道题的 返回值是不是要满足: : Min(r^2 - X) 其中r*r <= X ? : 比如 sqrt(8) 返回2 而不是3?
|
y****n 发帖数: 743 | 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*****a 发帖数: 14598 | 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****n 发帖数: 743 | 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****e 发帖数: 3548 | 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**k 发帖数: 222 | 12 觉得 yishan 的方法大体对。 会终止吗? 运行过吗? 需要回到实数吗?
一般牛顿法的收敛似乎并不是那么好做的。 这个可以。 |
x****7 发帖数: 86 | 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*********g 发帖数: 170 | 14 如果我没有记错,牛顿迭代法好像每做一次其精度增加一倍。
fatalme的log(1/\epsilon)对不对我不知道,不过似乎应该跟精度有关。
My 2 cents. |
d*******y 发帖数: 27 | 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));
}
} |
j********x 发帖数: 2330 | 16 newton好像是log(log(n))
每次迭代后满足精度的数字翻倍 |