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

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

0 голосов
/ 21 октября 2018

Для данного метода: 

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) существует в любой момент времени", что не имело смысла для меня.

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

1 Ответ

0 голосов
/ 21 октября 2018

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

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

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)

и т. Д.ru: 

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

, а затем: 

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

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

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

...