Пространственная сложность рекурсивной функции
Учитывая функцию ниже:
int f(int n) {
if (n <= 1) {
return 1;
}
return f(n - 1) + f(n - 1);
}
Я знаю, что сложность времени Big O O(2^N)потому что каждый вызов вызывает функцию дважды.
Я не понимаю, почему сложность пространства / памяти O(N)?
6 ответов
Полезным способом решения этих типов проблем является размышление о дереве рекурсии. Две функции рекурсивной функции для идентификации:
- Глубина дерева (сколько операторов полного возврата будет выполнено до базового случая)
- Ширина дерева (сколько всего будет выполнено рекурсивных вызовов функций)
Наше рекуррентное соотношение для этого случая T(n) = 2T(n-1), Как вы правильно отметили временную сложность, если O(2^n) но давайте посмотрим на это относительно нашего дерева повторения.
C
/ \
/ \
T(n-1) T(n-1)
C
____/ \____
/ \
C C
/ \ / \
/ \ / \
T(n-2) T(n-2) T(n-2) T(n-2)
Этот шаблон будет продолжаться до нашего базового варианта, который будет выглядеть следующим образом.
С каждым последующим уровнем дерева наше n уменьшается на 1. Таким образом, наше дерево будет иметь глубину n, прежде чем оно достигнет базового случая. Так как каждый узел имеет 2 ветви и у нас есть n общих уровней, наше общее количество узлов 2^n делая наше время сложным O(2^n),
Сложность нашей памяти определяется количеством операторов возврата, потому что каждый вызов функции будет храниться в программном стеке. Обобщая, сложность памяти рекурсивной функции O(recursion depth), Как предполагает наша глубина дерева, у нас будет n операторов возврата, и, следовательно, сложность памяти O(n),
Вот как я об этом думаю:
- Есть соблазн сказать, что сложность пространства также будет O(2^N), потому что, в конце концов, память должна выделяться для каждого из рекурсивных вызовов O(2^N), верно? (не правильно)
- На самом деле значения складываются / сворачиваются при каждом вызове, и, таким образом, необходимое пространство будет просто результатом каждого вызова, начиная с базового варианта и далее, образуя массив [f(1), f(2), f(3) ... f(n)], другими словами просто O(n) память
Я нахожу четкий ответ в двух статьях.
Первый
В этой статье мне рассказали, почему космическая сложность
O(n).
но я также не понимаю, почему
the stack frames иметь только
f(5) -> f(4) -> f(3) -> f(2) -> f(1) но без
f(5) -> f(4) -> f(3) -> f(2) -> f(0) и другие одновременно.
The Fibonacci tree изображение:
то я наконец нахожу ответ во второй статье, это меня сбивает с толку.
Второй
В этой статье это полезно. вы можете увидеть подробности здесь.
The stack frames изображение: 
Спасибо.
Это можно лучше объяснить, рассмотрев другую функцию:
f (n) = f(n-1) + f(n-2)
f (0) =0, f (1) = 1.
что приведет к следующему дереву вычислений для f (4)
е (4)
е (3) е (2)
е (2) е (1) е (1) е (0)
е (1) е (0)
Система может обрабатывать вычисления с дублированным стеком хранения, равным глубине (единица хранения для f (0), f (1), f (2), f(3) и f (4)). В то время как среда выполнения должна учитывать все операции на каждом узле (оператор сложения или возврата) - следовательно, это не фактор ни на одном из узлов.
Каждый вызов добавляет уровень в стек.
f(4)
е(3) е(2) е(1) е(0)
Каждый из этих вызовов добавляется в стек вызовов и занимает реальную память. Однако то, что у вас всего n вызовов, не означает, что требуется O (n). Так что это займет O (n) места.
Проблема рекурсии мы можем думать так, как будто мы реализуем ее со стеком, поэтому, если первая функция вызывает себя, вторую функцию приостанавливает, и она проходит через конец и добавляется в стек один за другим, а после завершения она возвращается и один за другим удаляется из самого верхнего stack, а затем вторая функция возобновляется и проходит через конец и добавляется в самый верх стека, а при возврате времени удаляется. Но он использует тот же стек, и он займет не более n места в одном стеке, поэтому сложность пространства используется O(n).