给出一个时间复杂度为O（n的立方根）的求立方根的算法并解释算法原理

Question

给出一个时间复杂度为O（n的立方根）的求立方根的算法并解释算法原理

Answer 1

double cube_root(double a)
{
return cube_root(a, 1.0);
}

double cube_root(double a,double x0)
{

double x1,y;
x1=(2*x0+a/(x0*x0))/3.0;
if(fabs(x1-x0)>=0.00001)
y=cube_root(a,x1);
else
y=x1;
return y;
}

 简单说下，这里x0是猜测值
然后算出这一点的切线和x轴的焦点x1
则有x(真实值)<x1<x0，也就是算出了一个比x0更精确的猜测值
重复以上过程，结果越来越逼近x(真实值)，直到得到你需要的精度。