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

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

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(真实值)，直到得到你需要的精度。

这里得用到**牛顿迭代公式**求解方程的根，这里简单讲下原理。

对待求方程y=f(x)，设f(x)=0的根为a，所以点A（a,0)先假设x₀为解
然后以B（x₀，y₀）为点做切线y-y₀=y₀'(x-x₀)。//y'₀是（x₀,y₀）的斜率
切线与x轴交点C(x₁,0)。因为|x₁-a|<|x₀-a|，所以x1更接近a
然后把x1求出，把（x₁,0)带入切线得x₁=x₀-y₀/y'₀
重复上述步骤得x（n+1）=x（n）-y（n）/y（n)

以求 ³√t 为例:
① y=x³-t（t为待求值），假设x₀为方程解（任意值）
过点（x₀,y₀)的切线方程为 y-y₀=y'(x-x₀)
②x₁=x₀-y₀/y'₀，化简得x₁=2/3.0x₀-t/3x²₀
③重复迭代得到某个x（n+1)-x(n)<err（精确度)

算法实现网上找就行了

用牛顿迭代法试试呗。
https://blog.csdn.net/a19990412/article/details/80816264
https://blog.csdn.net/a19990412/article/details/80816876
上面是我写了关于牛顿迭代的东西。（没错，楼上说的就是牛顿迭代法）

当然啦，你可以选择调整使用不同的递减方式啦~（主要是f(x)的那个系数问题而已）

下面的代码是我用python写的。你也可以用C++改写一下，主要是python用sympy的话，就像数学表达式一样了。
下面函数是用来求12的立根号

from sympy import *

x = symbols('x ')
y = x ** 3 - 12  # 原函数
y2 = 3 * (x ** 2)  # 导数

x0 = 1.0
x1 = x0 - y.subs(x, x0) / y2.subs(x, x0)

while abs(x1 - x0) > 1e-6:
    x0 = x1
    x1 = x0 - y.subs(x, x0) / y2.subs(x, x0)

print(x1)