#time-complexity #complexity-theory #space-complexity
Вопрос:
На стр. 44 Интервью по взлому кода есть следующий алгоритм:
int f(int n) {
if (n <= 1) {
return 1;
}
return f(n - 1) f(n - 1);
}
В книге говорится, что это имеет временную сложность O(2^n) и пространственную сложность O(n). Я получаю часть сложности по времени, так как создано O(2^n) узлов. Я не понимаю, почему сложность пространства-это не то же самое. В книге говорится, потому что это потому, что в любой момент времени существует только O(n) узлов.
Как такое может быть? Разве в стеке вызовов не было бы всех 2^n вызовов, когда мы находимся на нижнем уровне f(1)? Что я упускаю?
Пожалуйста, дайте мне знать, если я смогу предоставить более подробную информацию.
Спасибо,
Комментарии:
1. Нет, стек вызовов достигает определенного уровня
nвызовов только до остановки рекурсии. На каждой глубинеnна один меньше, поэтому ни один из рекурсивных вызовов не может повлиять на максимальную глубину вызова.2. Второй вызов
f(n-1)не состоится до тех пор, пока не вернется первый. Они не занимают место в стеке одновременно. И то же самое на всех остальных уровнях.3. Спасибо вам обоим! Это было полезно, особенно @Нейт Элдридж. Если вы хотите обозначить в качестве ответа, я приму его!
Ответ №1:
Нет. Второй вызов f(n-1) не выполняется до тех пор, пока не вернется первый, поэтому они не занимают место в стеке одновременно. Когда возвращается первый, его место в стеке освобождается и может быть повторно использовано для второго вызова.
То же самое относится и к каждому уровню рекурсии. Используемая память пропорциональна максимальной глубине дерева вызовов, а не общему количеству узлов.