Пространственная сложность для рекурсивных Фибоначчи с запоминанием?

Question

У меня есть два способа найти ряд Фибоначчи для заданного числа 'n'. Один использует памятку.

Я хотел бы знать, как отличается сложность пространства для этих двух методов:

    public static int fib(int n, int[] mem){

    if(n ==0 || n ==1 ){
        return n;
    }

    if(mem[n] > 0 ) {
        return mem[n]);
    }

    mem[n] = fib(n-1,mem) + fib(n-2,mem);

    return mem[n]; 

}

без напоминания:

public static int fib(int n){

    if(n ==0 || n ==1 ){
        return n;
    }

   return fib(n-1) + fib(n-2);


}

Answer 1

Прямое использование памяти самоочевидно - при использовании памятки каждое значение в fib будет вычисляться только один раз, поэтому сложность пространства будет o (n), где n - это входное число в fib (массив памятки будет содержать n чисел).).

Без запоминания - дополнительная память не требуется (недостатком является много избыточных вычислений).

- это массив запоминания, который передается каждому из рекурсивных вызововтот же массив .. или копия этого массива?В случае передачи копии массива ... сложность пространства будет> O (n).

Вы передаете ту же ссылку на массив для своих рекурсивных вызовов.

Это означает, что сложность вашего пространства равна o (n)Если вы создадите новый массив и передадите его, ваше запоминание не будет работать, поскольку вам придется объединить результаты обновленного нового массива с предыдущим / с.