Сравнение рекурсивного Фибоначчи с рекурсивным факториалом - PullRequest
Новая
       114

Сравнение рекурсивного Фибоначчи с рекурсивным факториалом

0 голосов
/ 19 июня 2020

Это упражнение 2.3.2 из книги Компьютерные науки. Междисциплинарный подход Седжвика и Уэйна:

Напишите рекурсивную функцию, которая принимает целое число n в качестве аргумента и возвращает ln (n!).

Я написал рекурсивный метод в Java следующим образом: 

public static double lnFactorial(int n)
{
    if (n == 1) return 0;
    return Math.log(n) + lnFactorial(n-1);
}

, и он отлично работает с n примерно до 10000. Но такой же рекурсивный вид Метод (ниже) для вычисления n-го числа Фибонначи занимает вечность, например, для вычисления 50-го числа Фибонначи. 

public static  long fibonacci(int n)
{
    if (n == 1) return 1;
    if (n == 2) return 1;
    return fibonacci(n-1)+fibonacci(n-2);
}

Почему такая огромная разница? Это потому, что рекурсивный метод Фибоначчи вызывает себя два раза на каждой итерации? Все равно не могу понять разницы!

Ответы [ 2 ]

1 голос
/ 19 июня 2020

Первый метод вызывает себя рекурсивно один раз , поэтому сложность составляет O (n) . Второй метод вызывает себя рекурсивно два раза , поэтому на глубину рекурсии количество вызовов удваивается, что делает метод O (2 n ) .

Разница между O (n) и O (2 n ) - это гиганти c, что делает второй метод более медленным.

Для вычисления 50-го числа вторым методом требуется 2 50 = 1125899906842624 рекурсивных вызовов. Для использования первого метода требуется всего 50 рекурсивных вызовов. ( Примечание: Эти числа не должны быть точными. Я только что добавил их, чтобы проиллюстрировать величины линейного и экспоненциального подходов.)

Здесь важно понимать, что Второй метод вычисляет число Фибоначчи одного и того же n s несколько раз. Посмотрите на исходный вызов, который вызывает себя рекурсивно с помощью n - 1 и n - 2 . Когда вы смотрите на вызов с n - 1 , вы видите, что он вызывает сам себя с n - 2 и n - 3 . Вы заметили проблему? Метод был вызван с n - 2 уже два раза. Он даже дважды вызвал себя с помощью n - 3 , когда вы посмотрите на первый вызов с помощью n - 2 . Это будет становиться все хуже и хуже по мере увеличения глубины рекурсии.

Обратите внимание, что первый метод не вызывает себя два раза с одним и тем же значением.

0 голосов
/ 19 июня 2020

Ваш метод Фибоначчи имеет временную сложность O (2 n ) (см. это объяснение), в то время как ваш факторный метод имеет временную сложность О (п) .

Пример , чтобы понять временную сложность:

Представьте себе класс из 100 учеников, в котором вы дали ручку одному человеку. Теперь тебе нужна ручка. Вот несколько способов найти ручку и порядок O.

O (n 2 ) : вы go и спрашиваете первого лица класс, если у него есть ручка. Кроме того, вы спрашиваете этого человека о других 99 человек в классе, есть ли у них ручка и т. Д. Это то, что мы называем O (n 2 ) .

O (n) : Идти и спрашивать каждого ученика индивидуально - это O (n) . ( источник )

Изменить: Пример O (n 2 ) не то же самое, что O (2 п ) . Это просто пример того, что означает временная сложность.

...