Как вы находите пространственную сложность рекурсивных функций, таких как эта?

Question

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

Предположим, что мы сделали f (4). Я думал, что это будет O (2^n), так как тогда для нахождения f (n-1) + f (n-1) нам нужно было бы нажать f (n-1) = f (3) на стек вызовов дважды, а затем f (2) четыре раза стек вызовов и т. д. Однако книга, которую я получил, говорит, что это O (n). Почему это так?

Answer 1

Давайте представим себе оценку этого для f (4) (пример, который вы считаете). Вот как это будет. Стек начинается похожий

I need to compute f(4) 

Тогда расчет е (4) рецидивирует в `е (3), и стек выглядит

I need to compute f(4), so 
I need to compute f(3) 

Тогда мы продолжаем идти вниз, и мы в конечном итоге получить до

I need to compute f(4), so 
I need to compute f(3), so 
    I need to compute f(2), so 
    I need to compute f(1), so 
    I need to compute f(0) 

Затем мы можем вычислить f (0) как 1, и последний вызов будет возвращен. Предпоследний вызов (один для вычисления F (1)), то хочет, чтобы вычислить вторую копию F (0), а стек идет в:

I need to compute f(4), so 
I need to compute f(3), so 
    I need to compute f(2), so 
    I need to compute f(1), and although I've already computed the first f(0)=1, I still need to compute the second occurrence of f(0), so 
    I need to compute f(0) (again) 

Тогда что возвращает, и поэтому вычисление F (1) может вернуться, и мы получаем

I need to compute f(4), so 
I need to compute f(3), so 
    I need to compute f(2), and although I've already computed the first f(1)=2, I still need to compute the second occurrence of f(0) 

и оттуда стек становится:

I need to compute f(4), so 
I need to compute f(3), so 
    I need to compute f(2), and although I've already computed the first f(1)=2, I still need to compute the second occurrence of f(0), so... 
    I need to compute f(1) 

, и он будет продолжать вычисления F (1), как и раньше.

Дело в том, что стек только когда-либо достигает глубины n, хотя (в конечном счете) будут выполняться 2^n операции. Таким образом, временная сложность O (2^n), но сложность пространства - это только O (n).