Cubi c Root Алгоритм за O (n) и O (log n) времени

Question

Как мне go вычислить куби c root за O (n) и O (log n)? Алгоритм, который имеет временную сложность O (log n), я бы бинарный поиск (я предполагаю)? Любые идеи будут высоко оценены.

Answer 1

Как насчет использования метода Ньютона-Рафсона ? Если вы ищете куби c root из N, тогда вы по сути смотрите root из f(x) = x^3 - N. Сходимость метода Ньютона является квадратичной c во времени, и сложность будет O(log(n)).

РЕДАКТИРОВАТЬ: Точнее, как описано здесь , он имеет сложность O(log(n)F(n)), где F(n) - это стоимость вычисления «обновления» с точностью n -di git.

Answer 2

Для O (n) вы можете просто выполнить итерацию от 0 до n, проверяя, является ли число куби c root, которое вы ищете. (Это работает только с целыми числами)

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