Фибоначчи, запоминание, порядок исполнения

Question

Следующий код представляет собой последовательность Фибоначчи, используя памятку.Но я не понимаю порядок выполнения в алгоритме.Если мы сделаем dynamic_fib (4), он вычислит dynamic_fib (3) + dynamic_fib (2).И сначала вызывается левая сторона, затем вычисляется dynamic_fib (2) + dynamic_fib (1).Но при вычислении dynamic_fib (3), как кэшированный ответ dynamic_fib (2) распространяется до повторного использования, когда мы не сохраняем результат в адрес памяти словаря, как & dic [n] в C.

Я думаю, что должно произойти, ответ на dynamic_fib (2) пропал, потому что он существовал только в этом стеке.Таким образом, вы должны снова вычислить dynamic_fib (2) при вычислении dynamic_fib (4)

Я что-то упустил?

def dynamic_fib(n):
    return fibonacci(n, {})

def fibonacci(n, dic):
    if n == 0 or n == 1:
        return n

    if not dic.get(n, False):
        dic[n] = fibonacci(n-1, dic) + fibonacci(n-2, dic)

    return dic[n]

Answer 1

Функция dynamic_fib (вызывается один раз) просто делегирует работу fibonacci, где выполняется настоящая работа.В fibonacci имеется словарь dic, который используется для сохранения значений функции после ее вычисления.Таким образом, для каждого из значений (2-n), когда вы вызываете функцию fibonacci в первый раз, он вычисляет результат, но также сохраняет его в словаре, поэтому, когда мы в следующий раз запрашиваем его,у нас уже есть это, и нам не нужно снова путешествовать по всему дереву.Так что сложность линейная, O(n).