Временная сложность перечисления всех путей вниз по лестнице? - PullRequest
Новая
       9

Временная сложность перечисления всех путей вниз по лестнице?

1 голос
/ 16 марта 2020

Я не могу определить временную сложность решения о возврате для проблемы подъема по лестнице, которая гласит:

Вы поднимаетесь по лестнице. Чтобы добраться до вершины, нужно n шагов.

Каждый раз вы можете подняться на 1 или 2 шага. Во сколько разных способов вы можете подняться на вершину?

Примечание: Дано n будет положительным целым числом.

Ввод: 2

Выход: 2

Объяснение: Есть два способа подняться на вершину.

  1. 1 шаг + 1 шаг
  2. 2 шага

Мой алгоритм: 

input = [1, 2]
output = set()
n = 4
def helper(temp):
    if sum(temp) == n:
        output.add(tuple(temp))
    elif sum(temp) > n:
        return
    else:
        for i in input:
            helper(temp + [i])
helper([])

print(output)

Выход для n = 4: 

{(1, 2, 1), (2, 1, 1), (1, 1, 2), (2, 2), (1, 1, 1, 1)}

1 Ответ

0 голосов
/ 16 марта 2020

Время выполнения этой функции необычно Θ (n · φ n ), где φ - это золотое сечение , (1 + √5) / 2.

Чтобы понять, почему это так, давайте поговорим о том, как анализировать код, который вы написали. Представьте себе дерево рекурсии для этого кода. (Это дерево с одним узлом для каждого выполненного рекурсивного вызова). Обратите внимание, что каждый рекурсивный вызов ветвится - есть один вызов для подзадачи размера n - 1 и один подзвук к проблеме размера n - 2. В любом дереве, где каждый внутренний узел разветвляется, общее количество узлов в два раза больше количество листьев. И в вашем случае, для каждого найденного решения есть один лист плюс несколько дополнительных листов для случаев, когда рекурсия выходит за пределы значения n. (На данный момент мы проигнорируем эту вторую группу, но поговорим о том, почему это произойдет позже.) Это означает, что общее количество рекурсивных вызовов (с учётом предыдущего предостережения позже) не более чем в два раза превышает количество путей. вниз по лестнице.

Итак, сколько существует решений этой проблемы? Оказывается, число решений для лестницы высотой n точно равно n-му числу Фибоначчи , а n-е число Фибоначчи равно Θ (φ n ). Таким образом, это означает, что всего было сделано Θ (φ n ) рекурсивных вызовов.

Итак, сколько работы занимают эти рекурсивные вызовы? Мы можем консервативно ограничить верхнюю часть работы каждого рекурсивного вызова на O (n), так как в худшем случае суммирование списка складывается 1 + 1 + 1 + ... + 1 n раз. Но мы также можем ограничить работу, выполненную на листьях, где работа является наибольшей, на Ω (n), потому что в лучшем случае мы складываем 2 + 2 + ... + 2 всего n / 2 раза.

В целом, у нас есть Θ (φ n ) вызовов, из которых нижние Θ (n) работают каждый, в общей сложности Θ (n · φ n ) работа.

Еще одна деталь, на которую следует обратить внимание - как насчет рекурсивных вызовов, которые «пересекаются» и складываются в нечто большее, чем n? Оказывается, есть также O (φ n ) из них. Один из способов убедиться в этом состоит в том, что число способов перерегулирования для попадания n + 1 - это самое большее количество решений для перечисления всех путей размера n + 1, и есть O (φ n ) из этих , Поэтому добавление их обратно ничего не меняет.

Надеюсь, это поможет!

...