Какова пространственная сложность этого кода?

Question

int f(int n) 
{ 
    if (n <= 1) 
    { 
     return 1; 
    } 
    return f(n - 1) + f(n - 1); 
} 

Я знаю, что временная сложность O(2^n), и я понимаю, почему.

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

Answer 1

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

Таким образом, он никогда не получает более глубоких уровней рекурсии уровней n, и это единственный вклад в пространственную сложность.

Answer 2

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

Answer 3

Нарисуйте дерево экспоненциальной временной сложности, а длина пути любого листа от корня дерева будет линейной. Этот линейный путь представляет собой пространственную сложность алгоритма. Алгоритм будет пересекать каждый из этих путей для решения проблемы, но в любой момент максимальное количество рекурсивных вызовов, хранящихся в стеке, будет линейным. Пример: для f(3)

  3 
    / \ 
    2  2 
    /\ /\ 
    1 1 1 1 

Максимальная длина от корня до листа равно O(n). Таким образом, сложность пространства также составляет O(n).