如果递归解决方案最终连续调用自身约 N 次，然后再返回一个级别，则空间效率最多为 O(N)，因为 N 次调用中的每一个都占用了一定数量的堆栈空间。
这是否也意味着时间效率充其量也是 O(N)，因为递归函数内部的代码类似于运行 ~N 次的内部循环代码？
问问题
175 次
3 回答
2
除了@Ben 的回答之外，还有“尾递归”的情况，其中当前堆栈帧被删除并替换为被调用者的堆栈帧，但仅当调用者的最后一个动作是返回被调用者的结果时。当以完全函数式语言实现时，这可能导致 O(n) 时间函数具有 O(1) 空间。
于 2012-07-07T22:53:42.257 回答
1
不，但你的观察有一些道理——基本上，如果你知道任何算法（递归或其他算法，因为我们不区分两者；并且没有任何东西可以真正区分它们，这更多是风格问题) 对于给定的问题至少具有空间复杂度f(n)，它也必须至少具有时间复杂度f(n)。
于 2012-07-07T23:06:46.123 回答
0
不，因为递归算法的每一步都可能比 O(1) 花费更长的时间。如果每一步都取 O(n)，那么总时间复杂度是 O(n^2)。
于 2012-07-07T22:51:14.463 回答