Сложность пространства рекурсивной функции

Учитывая следующую функцию:

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

Я знаю, что сложность времени Big O O(2^N), потому что каждый вызов вызывает функцию дважды.

Я не понимаю, почему сложность пространства/памяти O(N)?

Ответы

Ответ 1

Полезный способ решения проблем такого типа - подумать о дереве рекурсии. Две функции рекурсивной функции для идентификации:

  1. Глубина дерева (сколько всего операторов возврата будет выполнено до базового варианта)
  2. Ширина дерева (сколько всего будет выполнено рекурсивных вызовов функции)

Наше рекуррентное соотношение для этого случая T(n) = 2T(n-1). Как вы правильно заметили, временная сложность составляет O(2^n), но давайте посмотрим на нее в связи с нашим деревом повторений.

      C
     / \         
    /   \      
T(n-1)  T(n-1)

            C
       ____/ \____
      /           \
    C              C   
   /  \           /  \
  /    \         /    \
T(n-2) T(n-2) T(n-2)  T(n-2)

Этот шаблон будет действовать до нашего базового варианта, который будет выглядеть следующим образом.

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

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