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

Question

Документация для @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]

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

Answer 1

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

Сложность времени:

Первый вызов

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

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

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

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

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

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

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

Другие различия

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

Answer 2

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

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

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