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

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). Почему это правда?


recursion algorithm time-complexity big-o space-complexity
person kubernetes    schedule 08.11.2015    source источник
comment
в вашем примере O(1), так как вы никогда не выделяете память. а f(n) это просто 2^n   -  person Paul    schedule 08.11.2015
comment
Глубина рекурсии n   -  person throwit    schedule 08.11.2015

Ответы (1)


arrow_upward
28
arrow_downward

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

I need to compute f(4)

Тогда вычисление f(4) возвращается к `f(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).

person circular-ruin    schedule 08.11.2015
comment
@ cirular-ruin, что, если каждый вызов функции выделял другую, скажем, N ^ 2 памяти (не постоянную, как здесь)? Можем ли мы сказать, что пространственная сложность равна O(N * N^2) = O(N^3)? - person Jjang; 23.04.2019
comment
Должно быть, я думаю. Правильно @circular-ruin? - person mk2683; 23.05.2020