Нужно объяснить, почему эта линия делает все быстрее в моем калькуляторе Фибоначчи.(Python)

Question

Может кто-нибудь объяснить, почему эта строка fibValue[n] = result делает все намного быстрее?Для того, чтобы загрузить что-то более чем 30, требуется всего лишь более 30 лет.Заранее спасибо!

fibValue = { 0: 0, 1: 1}

def fib(n):
    if n in fibValue.keys():
        return fibValue[n]
    else:
        result = fib(n-1) + fib(n-2)
        fibValue[n] = result
        return result

result = fib(int(input("Enter number: ")))
print(result)

Answer 1

Метод, который вы использовали здесь для вычисления рядов Фибоначчи, называется методом динамического программирования.

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

Эти результаты используются для решения других подзадач.Так что это делает алгоритм быстрее.

Answer 2

Правильно, что существует метод, называемый динамическое программирование (он же памятка), с помощью которого вы сохраняете и повторно используете вычисленные результаты.Это значительно упрощает поиск и вычисления.

Когда вы удаляете fibValue[n] = result, вы не сохраняете результат, и, не сохраняя результат, вам необходимо пересчитать Фибоначчи для этого конкретного числа n.

Рассмотрим вычисления fib(6).При первом вызове функции вы получаете

fib(6) = fib(5) + fib(4)

По рекурсии это дает

fib(6) =                       fib(4)               +            fib(3)        +             fib(3)       +     fib(2)

fib(6) =            fib(3)        +     fib(2)      +     fib(2)      + fib(1) +      fib(2)     + fib(1) + fib(1) + fib(0)

fib(6) =      fib(2)     + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0)

fib(6) = fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0)

fib(6) =    1   +    1   +    1   +    1   +    1   +    1   +    1   +    1   +   1   +    1   +    1   +    1   +    1

fib(6) =    13

Вы могли видеть, что fib(3) и fib(2) вычислялись по крайней мере 3 раза каждый. Теперь рассмотрите, будет ли ваш ввод намного больше (скажем, 1000).Вы будете вычислять fib(3), fib(100), fib(200) и т. Д. Несколько раз. Это тратит огромное количество времени. Таким образом, чтобы сэкономить время (так как мы программисты, мы очень хорошо понимаем время), мы торгуем пробелом (т. Е. Памятью) длякэшируйте предыдущие вычисления и, таким образом ... экономьте время, выполняя поиск в кэше.

Сложность времени выполнения поиска в словаре Python составляет (в среднем) O(1), это занимает постоянное время и составляет лучшее вещь, которую программист может пожелать в алгоритме.Сравните это с громоздкой временной сложностью вычисления fib(n) с нуля.(Обратите внимание, что, как прокомментировал brunodesthuilliers , ваша функция в настоящее время выполняет поиск, перебирая объект dict.keys(), что приведет к (* в худшем случае) O(n) сложности времени для поиска. Простое изменениеif n in fibValue.keys() до if n in fibValue может привести к более быстрому вычислению.)

Как подсказывает @ PatrickArtner , если вы находите только одиночное значение Фибоначчи, выможет сделать ваш калькулятор Фибоначчи более эффективным во времени и пространстве, сохраняя только два значения (то есть самые последние значения fib) вместо кэширования каждого результата.