Динамическое программирование: рекурсия + мемоизация vs цикл + список

В документации для @functools.lru_cache приведен пример вычисления чисел Фибоначчи с использованием кеш для реализации метода динамического программирования:

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

Я видел, как этот подход используется для решения различных задач программирования. Имеет ли он ту же временную / пространственную сложность, что и «стандартный» итеративный подход динамического программирования, например:

def fib(n):
    if n < 2:
        return n
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(2 , n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Кроме того, есть ли недостатки в использовании рекурсивного подхода?


python recursion memoization dynamic-programming
person Eugene Yarmash    schedule 12.12.2018    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Он должен иметь такую ​​же сложность, как мемоизация (сверху вниз) динамического программирования.

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

Эта разница не важна для примеров фиббоначчи или факториала, но может иметь место для задач с разреженной таблицей подзадач (когда трудно предсказать, какие записи будут использоваться позже)

person MBo    schedule 12.12.2018
comment
поэтому, если мемоизированное пространство мало, итерация должна быть хуже, чем нисходящая. - person Will Ness; 12.12.2018

arrow_upward
0
arrow_downward

Ниже приводится сравнение показанных вами функций. В общем, эти наблюдения не обязательно справедливы для любого рекурсивного или итеративного подхода к вычислению чисел Фибоначчи, а относятся только к реализациям, которые вы показали в вопросе.

Временная сложность:

Первый звонок

  • Рекурсивный подход: O (n)
  • Итерационный подход: O (n)

Последующие звонки

  • Рекурсивный подход: O (1)
  • Итерационный подход: O (n)

Постоянные факторы

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

Сложность памяти:

Оба требуют O (n) дополнительной памяти, однако рекурсивный подход сохранит память (так что она будет выделена постоянно), в то время как итеративный подход освободит память после завершения функции.

Прочие отличия

Предел рекурсии Python. Когда время становится слишком большим и кеш не заполняется, рекурсивный подход не работает из-за этого ограничения, например fib(500). Для индексации списков такого ограничения (кроме случаев, когда у вас заканчивается память) нет.

person MSeifert    schedule 12.12.2018