algorithm
Приложения динамического программирования

Вступление

замечания

Числа Фибоначчи

Числа Фибоначчи являются основным объектом динамического программирования, поскольку традиционный рекурсивный подход делает много повторных вычислений. В этих примерах я буду использовать базовый случай f(0) = f(1) = 1 .

Вот пример рекурсивного дерева для fibonacci(4) , обратите внимание на повторные вычисления:

Нединамическое программирование O(2^n) Сложность выполнения, O(n) Степень стека

def fibonacci(n):
    if n < 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

Это самый интуитивный способ написать проблему. В лучшем случае пространство стека будет O(n) когда вы опускаете первую рекурсивную ветвь, делающую вызовы fibonacci(n-1) пока не нажмете базовый случай n < 2 .

Доказательство сложности выполнения O(2^n) которое можно увидеть здесь: Вычислительная сложность последовательности Фибоначчи . Основной момент следует отметить, что время выполнения является экспоненциальным, что означает, что время выполнения для этого будет удвоено для каждого последующего термина, fibonacci(15) будут в два раза длиннее fibonacci(14) .

Memoized O(n) Сложность выполнения, O(n) Сложность пространства, O(n) Сложность стека

memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1

def fibonacci(n):
    if len(memo) > n:
        return memo[n]

    result = fibonacci(n-1) + fibonacci(n-2)
    memo.append(result) # f(n) = f(n-1) + f(n-2)
    return result

С мемуаризованным подходом мы вводим массив, который можно рассматривать как все предыдущие вызовы функций. Местоположение memo[n] является результатом функции fibonacci(n) . Это позволяет нам торговать пространственной сложностью O(n) для времени выполнения O(n) поскольку нам больше не нужно вычислять дублированные вызовы функций.

Итеративное динамическое программирование O(n) Сложность выполнения, O(n) Сложность пространства, Нет рекурсивного стека

def fibonacci(n):
    memo = [1,1] # f(0) = 1, f(1) = 1

    for i in range(2, n+1):
         memo.append(memo[i-1] + memo[i-2])

    return memo[n]

Если мы разложим проблему на ее основные элементы, вы заметите, что для вычисления fibonacci(n) нам нужны fibonacci(n-1) и fibonacci(n-2) . Также мы можем заметить, что наш базовый случай появится в конце этого рекурсивного дерева, как показано выше.

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

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

Расширенное итеративное динамическое программирование O(n) Сложность выполнения, O(1) Сложность пространства, Без рекурсивного стека

def fibonacci(n):
    memo = [1,1] # f(1) = 1, f(2) = 1

    for i in range (2, n):
        memo[i%2] = memo[0] + memo[1]

    return memo[n%2]

Как отмечалось выше, итеративный подход к динамическому программированию начинается с базовых случаев и работает до конечного результата. Главное наблюдение, которое нужно сделать для того, чтобы добраться до сложности пространства до O(1) (константа), - это то же самое наблюдение, которое мы сделали для рекурсивного стека - нам нужны только fibonacci(n-1) и fibonacci(n-2) для построения fibonacci(n) . Это означает, что нам нужно сохранить результаты для fibonacci(n-1) и fibonacci(n-2) в какой бы то ни было точке нашей итерации.

Чтобы сохранить эти последние 2 результата, я использую массив размером 2 и просто переворачиваю индекс, который я назначаю, используя i % 2 который будет чередоваться следующим образом: 0, 1, 0, 1, 0, 1, ..., i % 2 .

Я добавляю оба индекса массива вместе, потому что мы знаем, что сложение является коммутативным ( 5 + 6 = 11 и 6 + 5 == 11 ). Затем результат присваивается старшему из двух точек (обозначается i % 2 ). Окончательный результат затем сохраняется в позиции n%2

Заметки

• Важно отметить, что иногда бывает лучше придумать итеративное memoized решение для функций, которые многократно выполняют большие вычисления, поскольку вы создадите кеш ответа на вызовы функций, а последующие вызовы могут быть O(1) if он уже был вычислен.