Космическая сложность memoized кода Фибоначчи

Question

void allFib(int n) { 
    int[] memo = new int[n + 1]; 
    for(int i = 0; i < n; i++){ 
     System.out.println(i + ": "+ fib(i, memo)); 
    } 
} 

int fib(int n, int[] memo) { 
    if (n <= 0) return 0; 
    else if (n == 1) return 1; 
    else if (memo[n] > 0) return memo[n]; 
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo); 
    return memo[n]; 
} 

В приведенном выше коде memoized напечатать первые п чисел Фибоначчи, что сложность пространства из-за рекурсивных вызовов в методе Фибо (memo[n]= fib(n - 1, memo) + fib(n - 2, memo);)? Несмотря на то, что они выглядят как рекурсивные вызовы, все, что они на самом деле делают, это memo [n - 1] и memo [n - 2], поскольку они, как гарантируется, уже были вычислены. Но поскольку они находятся в этой форме и устанавливают свой собственный стек в памяти, должен ли каждый из этих вызовов иметь память? Если да, то?

Если бы я должен был заменить эту линию на memo[n] = memo[n - 1] + memo[n - 2], то сложность пространства, предоставляемая этой линией, была бы уменьшена до O (1) вправо?

Я знаю, что общая сложность пространства, по крайней мере O (п) из памятки массив размера п + 1.

Answer 1

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

Действительно, каждый новый вызов в fib в цикле дает ровно два вызова (ну, кроме i = 0 и i = 1, где никаких дополнительных вызовов не производится). Для каждого вызова требуется постоянное пространство. Глубина рекурсии ограничена 2, поэтому общее дополнительное количество требуемого пространства является постоянным.

Если вы замените его на петлю суммированием memo[n] = memo[n - 1] + memo[n - 2], дополнительная космическая сложность останется O(1), поэтому она не будет уменьшена.