Это рекурсивная реализация последовательности Фибоначчи от 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 n). Однако я борюсь с анализом космической сложности.
Я посмотрел онлайн и задал вопрос.
В этом потоке 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)?
Если кто-то еще запутался, обязательно просмотрите это видео Youtube, в котором обсуждается пространственная сложность генерации последовательности Фибоначчи. Космическая сложность Фибоначчи
Ведущий ясно дал понять, почему сложность пространства была O (n), высота рекурсивного дерева равна n.
Вот подсказка. Измените код с помощью оператора печати, как показано в следующем примере:
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).
Как я вижу, процесс будет только спускаться по одной из рекурсий за раз. Первый (f (i-1)) создаст N кадров стека, другой (f (i-2)) создаст N/2. Таким образом, наибольшим является N. Другая рекурсивная ветвь не будет использовать больше пространства.
Итак, я бы сказал, что сложность пространства равна N.
Это тот факт, что за один раз оценивается только одна рекурсия, которая позволяет игнорировать f (i-2), поскольку она меньше пространства f (i-1).