Какова пространственная сложность рекурсивного алгоритма фибоначчи?

Это рекурсивная реализация последовательности Фибоначчи от Cracking the Coding Interview (5th Edition)

int fibonacci(int i) {
       if(i == 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i-1) + fibonaci(i-2);
}

После просмотра видеоролика о сложности времени этого алгоритма Fibonacci Time Complexity, я теперь понимаю, почему этот алгоритм работает в O (2 ⁿ). Однако я борюсь с анализом космической сложности.

Я посмотрел онлайн и задал вопрос.

В этом потоке Quora автор утверждает, что "В вашем случае у вас есть n стековых фреймов f (n), f (n-1), f (n-2),..., f (1) и O (1)". Разве у вас нет двухфазных кадров? Скажем, для f (n-2) Один кадр будет для фактического вызова f (n-2), но не будет также вызова f (n-2) из f (n-1)?

Ответ 1

Если кто-то еще запутался, обязательно просмотрите это видео Youtube, в котором обсуждается пространственная сложность генерации последовательности Фибоначчи. Космическая сложность Фибоначчи

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

Ответ 2

Вот подсказка. Измените код с помощью оператора печати, как показано в следующем примере:

int fibonacci(int i, int stack) {
    printf("Fib: %d, %d\n", i, stack);
    if (i == 0) return 0;
    if (i == 1) return 1;
    return fibonacci(i - 1, stack + 1) + fibonacci(i - 2, stack + 1);
}

Теперь выполните эту строку в основном:

Fibonacci(6,1);

Какое самое высокое значение для "стека", которое распечатывается. Вы увидите, что это "6". Попробуйте другие значения для "i", и вы увидите, что напечатанное значение "стек" никогда не поднимается выше исходного значения "i".

Так как Fib (i-1) оценивается полностью до Fib (i-2), уровней рекурсии не будет больше i.

Следовательно, O (N).

Ответ 3

Как я вижу, процесс будет только спускаться по одной из рекурсий за раз. Первый (f (i-1)) создаст N кадров стека, другой (f (i-2)) создаст N/2. Таким образом, наибольшим является N. Другая рекурсивная ветвь не будет использовать больше пространства.

Итак, я бы сказал, что сложность пространства равна N.

Это тот факт, что за один раз оценивается только одна рекурсия, которая позволяет игнорировать f (i-2), поскольку она меньше пространства f (i-1).