Поиск чисел в последовательности Фибоначчи с помощью рекурсии - как сделать это быстрее? - PullRequest
Новая
       34

Поиск чисел в последовательности Фибоначчи с помощью рекурсии - как сделать это быстрее?

1 голос
/ 19 января 2020

Мой код для поиска чисел в последовательности Фибоначчи работает правильно, но на самом деле это неаккуратно. (Найти число больше n = 55 практически невозможно). Где я допустил ошибку? 

public static void main(String[] args) {

    for (; ; ) {
        System.out.println("The value of the fibonacci sequence ");
        Scanner numer = new Scanner(System.in);
        long n = numer.nextLong();
        long result = Fib(n);
        System.out.println(result);

    }
}


private static long Fib(long n) {
    if (n <= 0) { System.out.println("Error"); return 0;}
    else if (n == 1 | n == 2) return 1;
    else return Fib(n-1)+ Fib(n-2) ;

}

Ответы [ 2 ]

3 голосов
/ 19 января 2020

Вы понимаете, сколько раз вы вычисляете fib (k) для каждого k? Если вы хотите, чтобы ваша программа работала быстро, не используйте рекурсию так слепо, вместо этого используйте l oop: 

private static long Fib(long n) {
    long prev = 1;
    long current = 1;
    if (n <= 0) { System.out.println("Error"); return 0;}
    if (n == 1 | n == 2) return 1;
    for (int i = 3; i <= n; i++) {
        long next = prev + current;
        prev = current;
        current = next;
    }
    return current;

}

Если вы хотите решить эту проблему только рекурсией, то вам нужно сохранить уже вычисленные результаты. Это можно сделать либо с помощью заметок, либо с помощью ленивого программирования Dynami c, и это намного сложнее, чем просто с помощью l oop.

0 голосов
/ 19 января 2020

Даже с учетом предложенных улучшений @Jason, это все еще алгоритм с экспоненциальным временем сложностью O (2 ^ N).

Чтобы уменьшить сложность времени до O (N ), также называемый линейное время , я предлагаю следующий подход (называемый " memoization ", поскольку мы сохраняем каждое вычисляемое нами значение и напрямую возвращаем его в течение времени O (1) всякий раз, когда оно спросил, следовательно, количество кадров стека будет намного меньше и будет увеличиваться максимально линейно со значением «n»). 

public static void main(String[] args) {
    // receive customer input
    HashMap<Long, Long> map = new HashMap<>();
    long result = Fib(n, map);
}

private long Fib(long n, HashMap<Long, Long> map) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (map.containsKey(n)) {
        return map.get(n);
    } else {
        map.put(n, Fib(n - 1, map) + Fib(n - 2, map));
        return map.get(n);
    }

}

Вы можете сравнить два решения, отправив их в упражнении Фибоначчи в Leetcode .

Кроме того, оба подхода (ваш и аналогичный мне подход к запоминанию) объясняются на вкладке «Решение» в ссылке выше, где вы можете узнать больше о сложностях времени.

...