O(n)和O(logn)时间的三次根算法

Question

如何计算O(n(时间和O(log n(时间中的三次根？时间复杂度为O(logn(的算法我会进行二进制搜索(我猜(？任何想法都将不胜感激。

Answer 1

使用牛顿-拉斐逊方法怎么样？如果你在寻找N的三次根，那么你本质上是在寻找f(x) = x^3 - N的根。牛顿方法的收敛性在时间上是二次的，复杂度为O(log(n))。

编辑：更准确地说，正如这里所描述的，它具有O(log(n)F(n))的复杂性，其中F(n)是以n位精度计算"更新"的成本。

Answer 2

对于O(n(，您可以从0到n进行迭代，检查数字是否为您要查找的三次根。(这只适用于整数(

int cubic(int n){
for(int i=0;i<=n;i++)
if(i*i*i==n)
return i;
return -1; // cubic root doesn't exist.
}

对于O(logn(，您可以进行从0到n:的二进制搜索

double error=0.00000001;
double cubic(double n){
double l=0, r=n, m=(r+l)/2;
while (abs(n-m*m*m)>error){ // if difference between m^3 and n is not satisfactory
m=(r+l)/2;
if(m*m*m<n) // if m^3 < n, then the root is definitely greater then m, so we move the left border
l=m;
else // otherwise, move the right border
r=m;
}
return m;
}