int f(int n) { if (n <= 1) { return 1; } return f(n - 1) + f(n - 1); }
我知道时间复杂度是O(2 ^ n),我明白为什么.
但是我不明白为什么空间复杂度是O(n).我被告知,这是因为在任何给定的时间只有n个节点,但对我来说没有意义.
所以它在递归中永远不会超过n个级别,这是空间复杂性的唯一贡献者.
