Почему пространственная сложность рекурсивного метода, который создает двоичное дерево вызовов O(h)?

Question

Учитывая этот метод:

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

Создает стек стека / двоичное дерево следующим образом:

      n
     /  \
   n-1   n-1
 /   \  /   \
n-2 n-2 n-2 n-2 etc

например. n = 3

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

2 ^ (n + 1) - 1 => 15 узлов / вызовов. Сложность времени O(2^n)

Мой вопрос: почему сложность пространства = O(h), h представляет высоту дерева, которая в примере равна 3? Другими словами, если каждый вызов метода имеет 1 пространство памяти для входной переменной n, то мы можем сказать, что для каждого вызова метода есть 1 пространство памяти. Если есть вызовы методов O(2^n), то почему пространство не равно O(2^n)? Моя ссылка говорит, что "только O(N) существует в любой момент времени", что не имело смысла для меня.

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

Answer 1

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

Если мы переписаем алгоритм так, это может сделать его более очевидным:

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

  int temp1 = f(n - 1);
  int temp2 = f(n - 1);
  return temp1 + temp2;
}

Так что звонки на первый f(n - 1) а второй f(n - 1) не происходят одновременно.

Это означает, что в любой момент времени у нас есть линейный стек вызовов, подобный этому:

      f(3)
     / 
    f(2)   
   /  
  f(1) 
 /
f(0)

На данный момент у нас есть стек вызовов размером 4. Когда f(0) вычисляется, последний элемент элемента извлекается из стека, и у нас будет стек вызовов размером 3:

      f(3)
     / 
    f(2)   
   /  
  f(1)

В этот момент алгоритм оценивает второй вызов f(1) (правильное поддерево f(1)):

      f(3)
     / 
    f(2)   
   /  
  f(1)
  \
   f(0)

У нас снова есть стек вызовов размером 4. На следующих нескольких шагах стек вызовов преобразуется в:

      f(3)
     / 
    f(2)   
   /  
  f(1)

а потом:

      f(3)
     / 
    f(2)   

а потом:

      f(3)
     / 
    f(2)
    \
     f(1)

а потом:

      f(3)
     / 
    f(2)
    \
     f(1)
    /
   f(0)

а потом:

      f(3)
     / 
    f(2)
    \
     f(1)

а потом:

      f(3)
     / 
    f(2)
    \
     f(1)
      \
       f(0)

и этот процесс продолжается, пока алгоритм не закончится.

Следовательно, можно сделать вывод, что сложность пространства для алгоритма равна O (h).