Как вернуть время, которое потребуется, чтобы метод закончил свою работу?

Question

У меня есть простой рекурсивный алгоритм, который возвращает числа Фибоначчи:

private static double fib_recursive(int n){
    if(n <= 2) return 1;
    else return fib_recursive(n-1) + fib_recursive(n-2);
}

Теперь моя задача - вернуть время, которое этот метод будет требовать для вычисления 400-го числа Фибоначчи на данном компьютере, например. fib_recursive (400). «Будет» выделено жирным шрифтом, потому что я не могу запустить функцию, так как это займет много времени, чтобы этот метод дал ответ.

Как это лучше всего сделать?

Answer 1

Рассчитайте, сколько времени нужно сделать для каждого рекурсивного вызова, выясните, сколько рекурсивных вызовов, и у вас есть ответ.

Существуют более быстрые способы сделать это, используя более интеллектуальный алгоритм рекурсии, но для вашего алгоритмапросто введите некоторую временную информацию.

Answer 2

Время определяется путем взятия разностей System.currenTimeMillis() или System.nanoTime() до и после того, что вы хотите измерить.

Answer 3

У меня, вероятно, не лучшее решение, но вот что я получил (может быть, это поможет кому-то в будущем):

1) Я измерил время, в котором нуждается рекурсивный методдля вычисления 42-го (например) числа Фибоначчи.

2) Используя итерационный метод, я подсчитал, сколько строк программы выполняется при вычислении 42-го числа Фибоначчи с помощью рекурсивного метода.(Rows = 3 * fib_iterative (42) -2)

3) Деление 2. на 1. Я получил среднее число строк, выполненных за 1 миллисекунду.

4) Использование итерационного методаЯ подсчитал, сколько строк программы было выполнено при вычислении 400-го числа Фибоначчи с помощью рекурсивного метода.(Rows = 3 * fib_iterative (400) -2)

5) Деление 4. на 3. Я получил расчетное время, проведенное fib_recursive (400).

// Recursive algorithm, calculates Fibonacci number (slow)
private static double fib_recursive(int n){
    if( n <= 2) return 1;
    else return fib_recursive(n-1) + fib_recursive(n-2);
}

// Iterative algorithm, calculates Fibonacci number (fast)
private static double fib_iterative(int n){
    double a = 1, b = 1;
    for (int i = 2; i <= n; i++){
        b = a + b;
        a = b - a;
    }
    return a;
}

// Get time, which fib_recursive(int) needs to calculate the 400th Fibonacci number
private static long testRecursiveFor400(){
    int elapsedTime = 0;
    int start = (int) System.currentTimeMillis();
    fib_recursive(42);
    elapsedTime = (int) (System.currentTimeMillis() - start);
    return (3 * (long) fib_iterative(400) - 2) / ((3 * (int) fib_iterative(42) - 2) / elapsedTime);
}