O(n) 和 O(log n) 时间内的立方根算法

Question

我将如何计算 O(n) 时间和 O(log n) 时间的立方根？时间复杂度为 O(log n) 的算法我会使用二进制搜索（我猜）？任何想法将不胜感激。

Answer 1

对于 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;
}

Answer 2

使用 Newton–Raphson method 怎么样？如果您正在寻找 N 的立方根，那么您实际上是在寻找 f(x) = x^3 - N 的根。牛顿法的收敛性是时间的二次方，复杂度为 O(log(n)).

编辑：更准确地说，如 here 所述，它具有 O(log(n)F(n)) 的复杂性，其中 F(n) 是使用 n 计算 "update" 的成本- 数字精度。

O(n) 和 O(log n) 时间内的立方根算法

Cubic Root Algorithm in O(n) and O(log n) time

c++

algorithm

discrete-mathematics